Optimal Solution

https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 문제 분석 뭐랄까 ... 중학생 때 일차함수를 공부하면서 기울기 라는 개념을 배운 적이 다들 있을 것이다(중학교 때는 문이과 분리가 안 되니까 ... 아마 다 알 것이라고 생각함). 이 문제는 그 '기울기' 를 응용해서 푸는 문제인데, N이 최대 50이기 때문에 러프하게 3중 for문을 걸어도 시간 제한에 걸리지 않아 3중 for문으로 해결할 수 있다고 생각했다. 코드 #include using ..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 분석 그래프가 있고, 이 그래프에서 방문하고자 하는 정점의 번호가 주어진다. 이 때, 이 정점들을 모두 경유할 수 있는 경로가 있는지 탐색하면 된다. 사실 문제를 보고 이 문제는 BFS로도 충분히 풀 수 있을 것 같다는 생각이 들었지만, disjoint-set, 즉 Union-Find를 활용해 풀 수 있을 것이라는 생각이 들었다. 그래서 Union-Find로 한 번 풀고, BFS로 한 번 더..

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net 문제 분석 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구해야 한다. 이중 for문으로 문제를 풀고자 한다면, N이 최대 10만이기 때문에 O(N^2)이 소요되므로 시간 내에 해결할 수 없다. 투 포인터를 사용해 문제를 해결할 수 있다. 코드 #include #include using namespace std; int n; i..

https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 문제 분석 진짜 너무너무 너무너무 귀찮은 문제이다. 특별한 알고리즘을 필요로 하지는 않는다. 그래서 문제 분석 칸이 짧다. 그냥 구현이고, 브루트포스이다. 코드를 작성하는 내내 귀찮아서 죽을 뻔 했다(이런 말을 해도 되나 ?). 코드 #include #include #include using namespace std; int n, k, p, x; bool isOn[10][7]; vector changables[10]; vector xVec; vector iVec; int result..

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 문제 분석 문제 이름에 대놓고 쉬운거 라고 적어놨는데, 쉬운 거 치곤 난이도가 높다. 아마 스카이라인 안 쉬운거 가 있으니까 저런 이름이겠지 ? 라는 생각을 했다. 글만 읽어서는 문제가 이해되지 않았다. 다행히 문제 본문 아래에 힌트로 스카이라인을 표시해주면서 예제 테스트케이스가 어떻게 그런 결과를 출력하는지 보여준다. 한 건물을 다른 건물과 ..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 분석 입력으로 2개의 문자열이 주어진다. 먼저 입력된 문자열은 어떻게 보면 폭발의 피해자 (?) 이다. 두 번째로 주어지는 문자열이 폭발 문자열인데, 먼저 입력된 문자열에서 폭발 문자열이 있다면 해당 부분을 폭발시킨(도려낸)다. 만일 폭발 문자열에 의해 폭발되고 나서, 문자열 내에 또 폭발 문자열이 포함되어 있으면 여전히 터진다. 그래서 더 이상 폭발하지 않을 때까지 계속 이 ..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 문제 분석 N개의 숫자들이 주어진다. 이를 1-base index 배열에 매칭시켜보면, 이런 구조이다. index 1 2 3 4 5 6 7 arr[index] 3 1 1 5 5 4 6 여기서, index들을 적절히 뽑으면 index 집합과 arr[index] 집합이 일치하게 될 수 있다. 이 경우에는 index 집합으로 [1, 3]을 만들거나, [1, 3, 5]를 만들면 arr[ind..

https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 문제 분석 도대체 이 문제가 왜 골드 5인지 이해할 수가 없다. 나는 틱택토에 대해서 알고 있어서 문제를 빠르게 이해한 것일 수도 있다(옛날에 Android MVC, MVP, MVVM을 공부할 때 틱택토 샘플 앱을 본 적이 있어서 그럴수도 ? 틱택토에 대한 이해도가 부족하다면, 혹은 문제가 무슨 말을 하는지 모르겠다면 직접 틱택토를 플레이해보고 오는 것도 좋은 것 같다. 구글에 틱택토 를 검색하..