BOJ

문제https://www.acmicpc.net/problem/21610 풀이 전형적인 삼성 역량 테스트의 구현 문제입니다.  우선 문제를 통해 다음의 동작으로 메서드를 구분해볼 수 있습니다. 1. 구름 이동 (moveClouds)2. 비 내리기(rain)3. 물 복사(copyWater)4. 구름 만들기(makeClouds) 각 단계별 메서드를 따라 구현을 해주면 되는데, 이 문제에서 생각해 볼 것은 1번 열과 N번 열, 그리고 1번 행과 N번 행이 연결된 것을 구현하는 것입니다. 이것은 % 연산자를 통해 간단히 구현할 수 있습니다.  그리고 이 문제의 전반적인 부분에서 조심해야하는 것은, 구름을 이동하거나 물을 복사하는 동작에서, 수정된 데이터를 사용하는 것을 주의해야합니다. 그것을 방지하기 위해 Arr..

문제https://www.acmicpc.net/problem/1240   풀이 트리에서의 탐색 문제입니다. Dfs를 이용해서 문제를 해결했습니다.  우선 Arraylist[] 배열에 입력값을 입력받습니다. 이 때, 방향은 양방향 모두 갈 수 있으니 양뱡향으로 입력 받습니다.  그리고 dfs메서드를 통해 시작점부터 탐색을 시작합니다. 한 가지 주의해야할 것은, 거리의 합을 구하는 것에 있습니다. 만약 아래와 같은 입력 값이 주어질 때를 생각해보겠습니다. 4 11 2 12 3 12 4 11 4// 정답 2  이 반례 코드에서 2는 3, 4의 두 방향으로 뻗게 됩니다. 그래서 3으로 보낸 dfs에서 거리의 합에 거리를 더하고, 그것을 바로 4로 보내게 되면 중복해서 값이 들어가게 됩니다. 그래서 한 노드에서 ..

문제 https://www.acmicpc.net/problem/5568 5568번: 카드 놓기 예제 1의 경우 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 풀이 순열과 Set 자료구조를 통해 해결했습니다. 우선 N개의 카드 중 K개의 카드를 순서를 고려하여 뽑아야하기 때문에, 순열 백트래킹을 통해 selected[] 배열에 인덱스를 저장합니다. 그리고 card[] 배열에 대입하여 해당하는 카드 번호들을 뽑아냅니다. 이때 번호의 나열은 StringBuilder를 이용해 합치고 그 결과를 Set에 집어넣습니다. Set은 중복을 허용하지 않는 자료구조입니다. 그렇기 때문에 Set의 size를 구하면 중복되지 않은 경우의 수가 나오게 됩니다. 아..

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 풀이 스택 자료구조를 활용한 문제입니다. stack에는 순서대로 들어오는 각 층을 쌓습니다. 여기서 조건을 잘 정리해야합니다. 우선, 스택이 비어있거나 stack의 peek이 들어올 y좌표보다 작을 때는 push를 합니다. 만약 peek이 크다면, peek이 y좌표보다 작을때마다 pop을 수행하고 pop 개수는 건물의 개수가 됩니다. 그리..

문제 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선 순위 큐를 이용해 문제를 해결했습니다. 단순히 반복문 두 개로도 해결할 수는 있지만, 시간 복잡도가 300,000*300,000으로 제한 범위를 훨씬 넘어가게 됩니다. 풀이 방법은 다음과 같습니다. 1. 우선 보석을 무게에 대해 오름차순으로 정렬합니다. 그리고 무게가 같다면 가격에 대해 내림차순 정렬합니다. 2. 가방은 ..

문제 https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 풀이 최소 공통 조상을 찾는 문제입니다. 위 문제는 sparse table이나 세그먼트 트리를 사용하지 않고, dfs로도 구현이 가능합니다. 우선 입력 값을 Arraylist[] 배열에 넣어 트리 상의 연결된 두 정점을 표현합니다. 그리고 parents[] 배열과 depth[] 배열을 통해 각 정점의 부모와 깊이를 저장합니다. (findDepthAndParents 메서드) 그럼 pare..