본문 바로가기
728x90
반응형

Algorithm

 (66)
[ 백준 / 14500 ] 테트로미노 ( 자바 ) www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 구현과 DFS라는 생각을 했지만 정작 어떻게 구현해야하는지 굉장히 머리가 아팠다. 생각해 볼만한 있는 중요한 점이 몇 개 있었다. (0,0)에서 시작하여서 그냥 끝내야 할까? 각 점에서 시작하여서 계산해야 할까? 일반적인 DFS를 사용해야 할까? => 그렇다면 ㅗ 모양을 출력하지 못한다. 따라서 일반적인 DFS가 아닌 추가적인 방법이 필요하다. 그래서 BFS를 생각했고 Queue를 사용해봤는데, 백트래킹과 BF..
[ 백준 / 3780] 네트워크 연결 ( JAVA ) www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net Union-Find를 통해서 해결이 가능하다. 처음에 문제를 이해하는데 오래 걸렸다. 이 문제의 특징은 단순히 union으로 관계를 설정하고, find를 통해서 관계를 발견하는 것이 끝이 아니다. 거리가 존재하기 때문에, 이를 계속 업데이트 해주어야 한다. 따라서 parent 배열 이외에도 dis 배열을 하나 만들어서 계속 거리 값을 최신화했다. 처음에 단순히 부모의 값만 저장하여 계..
[ 백준 / 10775 ] 공항 ( 자바 ) www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제는 2가지로 풀이가 가능하다. Greedy를 통해서 푸는 방법, Union-Find로 푸는 방법이 있다. 1. Greedy 1초에 1억번 연산이 가능하다는 것에 근거하여, Greedy로 풀어서 최악의 경우가 되어도 시간초과가 되지 않는다. 2. Union-Find union과 find에서 어떠한 연산을 해주어야 하나? union에서는 부모를 찾은 후, 부모보다 1 작은 값은..
[ 백준 / 3665 ] 최종 순위 ( 자바 ) www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬문제인데 기존 문제보다 조금 복잡하다. 왜냐하면 보통의 위상정렬은 A가 B보다 앞에있다! 이런식으로 단순하게 하나씩만 관계를 설정하면 된다. 하지만 이번 문제는 순서가 미리 정해져 있으며, 순위의 선후관계가 바뀌는 경우다. 따라서 순위에 따라서 모든 관계를 추가해주어야 한다. 예를 들어, 5 4 3 2 1의 순위가 있다면 5의 경우는 4 3 2 1을 List[]에 저장하고 inDegree는 0이다..
[ 백준 / 1107 ] 리모컨 ( 자바 ) www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 여러가지 경우의 수를 고려해야 한다. * 방법1 v1. 내가 고려했던 것은, 100에서 +,-를 이용해서 이동하기 자릿수에 따라서 모든 경우의 숫자를 만들고 +,-를 이용해서 이동하기 v2. + 0을 누르고 이동하기 + 자릿수가 하나 적을 때 + 자릿수가 하나 많을 때 ================================================================ * 방법2 ..
[ 프로그래머스 / 멀리뛰기] (자바) programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 계단을 오른다.... (1칸, 2칸) or 멀리뛰기를 한다... (1칸, 2칸) 등은 모두 dp를 사용한다. 전형적인 문제이다. 반복적인 조합을 이용해서 최선의 결과를 찾아야 하는 것이다. 여기서는 1칸,2칸만 사용이 가능하다. 따라서 1칸과 2칸만을 이용한다. 가장 먼저 초기화를 해준다. dp[1]과 dp[2]를 해준..
[백준 / 2252] 줄 세우기 ( 자바 ) www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상정렬 문제이다. 학교 수업의 커리큘럼을 짜거나 순서를 정할 때 유용하다. A가 B보다 앞선다고 할 때 어떻게 코드로 표현할 것인가? inDegree라는 배열을 만들어서 B에게 +1을 한다. 그렇다면 B앞에 1개가 있다고 선언하는 것이다. 그렇다면 B앞에 무엇이 있는 것인가? 이것은 List[] 에 관리한다. 리스트 배열에서 A의 리스트에 B를 추가한다. 이전 문제에서..
[ 백준 / 1406 ] 에디터 ( 자바 ) www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 에디터 문제를 처음보고 구현으로 생각했다. 그래서 케이스를 나눠서 substring을 이용했다. 커서의 위치는 index를 이용하였다. 하지만 그렇게 문제를 풀면 시간초과가 났다. package bj; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { B..
728x90
반응형

티스토리툴바