https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제조건 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있다. 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 숫자를 최대로 뽑는 경우, 뽑는 숫자들을 출력하라. 접근방법 모든 경우의 수를 따져서 비교해줄려고 DF..

https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 문제조건 부모 자식들간의 관계가 주어졌을때, 계산하고자 하는 두사람의 촌수를 구해라 접근방법 트리 모양 구조를 탐색하는 그래프 탐색 방법으로 접근했다. 근데 촌수 이므로 cycle이 생길 일은 없다. 따라서 각 노드를 양방향 연결해주고 DFS로 탐색해줬다. 아버지의 형제들과 나와의 관계는 3촌으로 분류할 수 있는데, 이를 계산하는 방식은 나 → 아버지(1촌) → 할아버지(2촌)..

https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제조건 톱니바퀴 4개, S극(1), N극(0) 존재 각 톱니바퀴가 맞닿아있는 부분이 극이 다르면 다른 방향으로 회전, 같으면 맞닿아있는 톱니바퀴는 회전X 12시방향부터 시계방향순서대로 8개의 톱니에 S, N 주어짐 돌리는 과정을 모두 수행한뒤, 최종적인 톱니바퀴 상태에서 4개의 12시방향에 있는 S들의 합 문제 파악하는데 30분 정도 걸린거같다. 역시나 문제는 복잡하고 풀이 방법은 쉽겠지,,..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net 문제조건 A,B로만 이루어진 두 문자열 S, T 가 주어지고, S를 T로 바꾼다. 문자열뒤에 A를 추가한다. 문자열의 뒤에 B를 추가하고 문자열을 뒤집는다. S를 T로 바꿀수 있으면 1 출력, 아니면 0 출력 S에서 두가지 행동만 할 수 있는데 행동들이 전부 문자 길이를 늘리는 것이므로 S, T가 똑같은 길이가 되었을때, 같은 문자열이 아니라면 0을 출력하..

https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 이 문제의 핵심은 이 그림을 가지고 어떤 규칙이 있는지 유추하는 것이 핵심이다. 같은 모양이 반복적으로 나타나는 구조인 프랙탈(?) 구조인 것을 볼 수 있다. 여기서 나의 접근 방법은 Top-Down Approach를 통 DFS로 결정을 했다. 3x2^k (0> n; dfs(n / 3, 0, 0); for (int i = 0; i < n; i++) { for (int j = 0; j < 2 * n - 1; j++) { if (map[i][j] == ..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 처음 문제를 보자마자 그래프가 나오길래 그래프 탐색 방법을 떠올렸다. 접근 방법은 차례대로 인덱싱하는 방향이길래 왼쪽부터 차례대로 인덱싱할수 있도록 DFS방식으로 접근해봤다. 또한 각 레벨에서의 너비를 구해야하는데, 탐색할때마다 인덱스를 1부터 시작해서 하나씩 증가시켜주며(어차피 왼쪽에서 부터 차례대로 인덱싱 할거니까), 각 레벨의 low, high 배열을 갱신시켜서 왼쪽 끝과 ..