기로에 서다

문제 www.acmicpc.net/problem/2381 2381번: 최대 거리 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다. www.acmicpc.net 풀이 절댓값을 풀어서 나오는 네 가지 경우는 아래의 꼴입니다. 1. $±((a + b) - (c + d))$ 2. $±((a - b) - (c - d))$ 각 식을 살펴보면 결국 두 점간의 거리를 구하는 게 x, y좌표 대, 소관계와 관계없이 좌표 간의 합(차)의 차이를 구하는 것과 같고, 이에 최대 거리를 구하는 것은 각 좌표 간 합(차)의 최대 값에서 최소 값을 빼는 것과 같습니다. 코드 #include using namespace std; int..

문제 www.acmicpc.net/problem/5980 5980번: Corn Maze This past fall, Farmer John took the cows to visit a corn maze. But this wasn't just any corn maze: it featured several gravity-powered teleporter slides, which cause cows to teleport instantly from one point in the maze to another. The slides work in both www.acmicpc.net 문제 풀이 알파벳으로 입력받는 Transport해주는 점들의 좌표를 따로 관리해주며 그 점들 간의 이동시에는 0 코스트가 들기 때문에 방..

문제 www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 풀이 지나갈 수 있는 최소 값과 최대 값을 투포인터로 관리하며 시작점부터 bfs를 통해 끝점까지 가는 경우에 최대 값 - 최소 값을 갱신해준다면 $O(N^2*200)$으로 시간내에 답을 구할 수 있습니다. 코드 #include using namespace std; typedef pair pi; const int dir[4][2] = { {-1,0},{1,0},{0,-1},{0,..

처음보는 카카오 코딩테스트였습니다 :) 1. 문자열 처리 (솔) 2. 조합 (솔) 3. 파싱, 이분탐색(lower_bound) (솔) 4. 플로이드 (솔) 5. 슬라이딩 윈도우 6. bfs 7. 트리DP (1~4) 4솔하고 6번풀다가 끝났네요.. c++로 응시했는데 파싱하는데에 시간이 꽤 걸린 것 같아 다음에 보게 된다면 문자열 처리할 때는 파이썬을 사용하려합니다 (__) 개인적으로 부족한점이 많은걸 느낀 시험이었고 다들 긴 시간동안 시험보시느라 수고하셨습니다 !

문제 www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 각 R줄 동안 C만큼의 문자열이 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 문제 풀이 1. 빙하가 녹는 시간마다 BFS를 돌릴 때, 최악의 경우 $O(R*C*max(R,C))$로 TLE가 난다. 2. 이에 빙하가 녹는시간을 BFS 한번으로 전처리한 후, 빙하가 녹는 시간에 대한 백조의 이동을 줄여보기로 한다. 3. 백조가 만날 수 있는 최소시간이 T초일 때, T-1초엔 녹지않은 빙하때문에 만날 수 없다는 점에서 "시간이 T일 때 백조가 만날 수 있는 가?" 라는 결정함수..

문제 www.acmicpc.net/problem/3673 3673번: 나눌 수 있는 부분 수열 양의 정수로 이루어진 수열이 주어졌을 때, 연속하는 부분 수열의 합이 d로 나누어 떨어지는 것의 개수를 구하는 프로그램을 작성하시오. 예를 들어, 아래와 같은 수열의 부분 수열 중 4로 나누�� www.acmicpc.net 문제 풀이 1. n의 범위로 보아 연속된 부분수열의 합을 구하기 위해 누적합을 사용한다고 생각했습니다. 2. 시작점이 고정된 연속 부분수열의 합이 아니므로 구해야하는건 시작점을 s, 끝점을 e라 할 때, 구간[s,e]의 누적합이 (psum[e] - psum[s-1])%d ==0을 만족하는 (s,e)쌍을 찾는 것과 같았고, 이는 (psum[e] % d) == (psum[s - 1] % d)와 ..

문제 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 1. 항상 중앙 값을 구하기 위해 우선순위 큐 두 개를 아래의 그림과 같이 사용해서 입력받는 수를 관리하기로 한다. lpq = top쪽으로 갈수록 수가 커지는 max heap rpq = top쪽으로 갈수론 수가 작아지는 min heap 2. 입력받는 수(k)는 항상 두 힙중 하나에 들어가야하며 중앙값을 구하기위해 두 힙의 크기는 항상 같거나 lpq가 rpq보다 크기가 1큰 경우만..

문제 www.acmicpc.net/problem/17436 17436번: 소수의 배수 첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다. www.acmicpc.net 문제 풀이 m의 범위를 못보고 계속 int형으로 제출해 삽푼문제였다. 1. 우선 m에 대해 각각의 소수로 나눴을 때 나누어 떨어지는 개수를 모두 세어보면 m/p[0] , m/p[1] ...등이 있을 것이다. 2. 이 때 간단한 예시를 통해 생각해보면 중복으로 카운트되는 수들이 존재하는 걸 알 수 있다. m = 30, p[0]= 2 ,p[1] = 3 일 때, p[0]에선 2,4,6.....

문제 www.acmicpc.net/problem/16402 16402번: 제국 배성일력 73년, 대륙을 주름잡던 성일 제국은 무리한 정복 전쟁 끝에 멸망하게 되었다. 기회를 노리던 반란군들은 혼란을 틈타 제각각 왕국을 선포했고, 왕국들은 제국의 자리를 차지하기 위해 � www.acmicpc.net 문제 풀이 1. 유니온파인드로 집합을 관리하기 위해 각 국의 이름을 입력받은 후 파싱하여 map에 순으로 저장한다. 2. 위와 마찬가지로 각 국의 이름과 관계도 적절히 파싱한 후에 이기는 국가가 앞쪽으로 오도록 두 집합을 합쳐준다. 3. 합칠 때는 아래의 세가지 경우가 존재하고, 맨 위 두가지 경우는 같다고봐도 무방하다. (∵ 종주국 v의 부모는 pv) 종주국(u)이 종주국(v)을 이길 때 : u가 v의 속국으..

문제 programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 풀이 처음엔 열쇠를 따로 벡터에 넣어 관리하며 열쇠의 상태를 방문처리하는 방법으로 bfs를 돌려볼까 했으나 생각보다 구현이 힘들것 같아 다른 방향으로 생각해봤다. 키를 상,하,좌,우로 움직이는 경우를 생각해보면 아래와 같이 왼쪽 위 끝부터 오른쪽 아래 끝까지 이동할 수 있다. 키를 최대 $(n + m - 1)^2$번 이동하고 4번 회전할 수 있으며 lock의 개수 $(m^2)$만큼 비교하므로 충분히 완전탐색으로 구..