알고리즘

문제 https://www.acmicpc.net/problem/1052 풀이 > 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다. 이 문제는 10진수를 2진수로 바꿔서 푸는 문제이다. 문제의 예제 입력을 보면 물병의 개수가 3개일 때 이를 1개로...

문제 https://www.acmicpc.net/problem/1011 풀이 이 문제는 처음과 마지막의 거리가 1로 제한되는 조건이 있다. 이 조건을 만족하며 주어진 거리를 최소한의 횟수로 가는 것이 문제인데 이는 다음과 같이 해결할 수 있다. 위 그림에서 주어진 거리(Distance)는 Count로 갈 수 있는 최대의 거리를 나타내고 있다. 이 문제를...

문제 https://www.acmicpc.net/problem/1074 풀이 이 문제는 재귀를 이용하여 해결했다. (N = 3일때 예시) N을 입력으로 받은 후에 counting 메서드를 만들어서 2^(N-1)을 기준으로 입력받은 r과 c의 값을 1,2,3,4분면 중 하나로 범위를 줄일 수 있다. (N = 3일때 r과 c의 값이 1사분면에 있다고 가...

문제 https://www.acmicpc.net/problem/1105 풀이 이 문제를 풀 떄는 주어지는 값인 L과 R의 길이가 같을 떄만 생각하면 된다. L과 R의 길이가 다르면 8이 포함되지 않는 숫자가 존재하게 된다. if문으로 L과 R의 길이가 같을 때만 값을 비교하도록 코드를 짜고 L과 R의 각 자리수 비교는 charAt()메서드를 사용해서 비...

문제 https://www.acmicpc.net/problem/1149 풀이 > 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다 처음에는 그리디 알고리즘으로 문제를 풀어보았지만 오답이었다. 매순간 가장 최선...

Tree Tree는 Array, LinkedList, Stack, Queue처럼 일직선 구조가 아니라 부모 자식 관계를 가지는 구조이다. 그래서 Tree는 계층이 있고 그룹이 있다.(계층과 그룹이 있는 이유는 각 노드가 하나 이상의 자식노드를 가지기 때문이다.) 더이상 자식이 없는 마지막 노드를 leaf라고 부른다. Binary Tree(이진트리) 노...

문제 https://www.acmicpc.net/problem/1189 풀이 이 문제는 DFS 방법으로 풀어야한다. 출발 지점이 왼쪽 하단이고 도착 지점이 오른쪽 상단이므로 입력값으로 받는 R, C로 시작점을 (R-1, 0) 도착점을 (0, C-1)로 하여 문제를 풀었다. 모든 배열의 값은 시작점을 제외하고 0으로 시작하고 시작점은 1로 시작하게 하고...

문제 https://www.acmicpc.net/problem/1005 풀이 이 문제는 방향은 있으며 사이클이 없는 그래프 문제이다.(DAG 알고리즘 문제) 그래서 위상 정렬을 사용하여 문제를 해결하였다. 간선이 0인 번호의 빌딩은 먼저 지어져야 하는 빌딩이 없다는 것을 의미하므로 해당 빌딩까지 걸리는 시간은 그 빌딩이 걸리는 시간과 같다. >time...

문제 https://www.acmicpc.net/problem/2477 풀이 문제에서 육각형의 방향과 길이를 입력받는다. 이 문제를 입력받은 방향을 이용하지 않고 문제를 풀었다. 이용하지 않고 풀 수 있는 이유는 다음과 같다. 6각형이 위의 그림처럼 생겼다고 가정하자. 그림에서 길이가 가장 긴 변은 160이다. 이 변의 양옆으로 50과 20의 길이를 ...

문제 https://www.acmicpc.net/problem/1049 풀이 이 문제는 M개의 브랜드 줄 중 어느것이 6개 짜리 줄의 가격(all)과 한 줄의 가격(one)이 최소값인지 구하고 가장 최소값인 6개 짜리 줄 가격(all[0])과 가장 최소값의 한개 짜리 줄(one[0]) * 6의 각격 중 어느 것이 저렴한지 구해서 N개의 줄을 사는 최소...

문제 https://www.acmicpc.net/problem/1213 풀이 이 문제는 가운데를 기준으로 양옆이 같도록 출력하는 문제이다. 규칙을 찾아보면 홀수가 2개 이상나오는 순간 좌우가 대칭이 될수 없다는 것을 알수 있다. 대문자로 입력 받으므로 배열을 효율적으로 사용하기 위해 'A'를 빼줘서 0 ~ 25까지의 배열을 선언하여 사용하지 않는 배열이...

문제 https://www.acmicpc.net/problem/2864 풀이 이 문제는 입력을 한줄로 받으면서 5를 6으로 바꿔 최댓값을 만들거나 6을 5로 만들어서 최솟값을 만드는 문제인다. String의 replace()메서드를 이용하여 6을 5로 바꿔서 입력을 한 번 받고 5를 6으로 바꿔서 입력을 받아 이 문제를 해결하였다. 코드