https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선수위 큐와 그리디 문제다. 처음에는 작은 수가 여러 번 더해지는 게 최솟값이 나올 거라고 생각해 정렬 후 각 수에 n - i를 곱해서 더하는 방법을 생각했다. 이 방법은 항상 앞의 두 수 합에 바로 뒤에 숫자를 더한다. 반례가 있을 것 같다는 생각이 들었다. (a + b) (c + d) e 를 더하는 것이 최솟값이 나오는 경우가 있을 것 같았다. 있었다. 원소 삽입마다 정렬이 되..
Algorithm
https://www.acmicpc.net/problem/1938 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 ≤ N ≤ 50) 주어진다. 이어서 그 지형의 정보가 0, 1, B, E로 이루어진 문자열로 주어진다. 한 줄에 입력되는 문자열의 길이는 N이며 입력 문 www.acmicpc.net BFS와 구현 문제다. BFS와 동일하게 진행하고, 움직일 때 범위 검사만 추가해서 했다. 회전에 대해서는 방문 배열을 3차원으로 생성해 가로일 때 방문과 세로일 때 방문을 구분해서 체크했다. 회전시 계산이 편하도록 3칸 중 중간 칸을 기준으로 삼았다. #include #include using namespace std; // 상하좌우 탐색을 위함 int dr[4] = { ..
https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택 자료구조 문제다. 시간초과가 날 걸 알면서도 단순하게 하나하나 검사하는 방법으로 해봤다. 혹시나 했는데 어림도 없지 시간초과다. 뒤에서부터 탐색하여 최댓값들을 저장하는 방법에 대해 생각했다. 그러면 최댓값이 가장 오른쪽에 존재한다는 보장이 없다. 지금까지 저장한 오큰수들을 탐색해보려고 했는데 이거는 단순 이중 반복문이나 다름이 없었다. 그러다 든 생각은 뒤에서부터 탐색하며 수들을 스택에 넣는 것이다. ..
https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 누적 합과 구현 문제다. 자신보다 사이즈가 큰 공을 찾기 위해서는 정렬이 필요하다고 생각했다. 이중 반복문으로 하나하나 검사를 하면 시간초과가 날 것 이기 때문에 효율적인 방법을 찾으려 했다. 처음에는 반복문 하나에 누적합을 구하는 방법을 사용했다. for (int i = 1; i n; for (int i = 1; i > c >> s; arr[i] = { s, c, i..
https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 구현 문제다. 마법사 상어와 파이어볼과 비슷한 문제다. https://abbiddo.tistory.com/19 큐나 벡터 하나만을 사용하면 이동한 상어에 대해 또 이동을 할 수 있다는 반례가 생긴다. 상어가 어디에 위치했는지 알기 위한 벡터와 현재 위치해 있는 상어들에 대한 정보를 담은 큐를 사용했다. 상어가 동일한 곳에 도착하면 큰 상어만 남아야 하는데 이동하자마자 큐에도 넣..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net BFS 문제다. 말이 되고픈 원숭이와 비슷하다. https://abbiddo.tistory.com/16 만날 때마다 새롭다. 특수 경우가 방문한 곳을 일반적인 경우로 방문할 수 있어야 한다는 점이 항상 헷갈리게 한다. 방문 배열을 3차원으로 만들고 [r][c][0]에는 벽을 뚫고 가지 않은 경로 / [r][c][1]에는 벽을 뚫고 간 경로를 저장했다. 초기값은 벽이 아니기..
