https://www.acmicpc.net/problem/2824 2824번: 최대공약수 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 www.acmicpc.net GCD 응용 문제. 입력으로 들어오는 수들을 다 곱해내면 범위제한을 훌쩍 초과하게 된다. 오버플로우가 발생하는것을 막기 위해서, 입력으로 들어오는 수들에서 바로 최대공약수를 계산해야 한다. A와 B 두 배열에 입력을 받았을 때, 두 배열에서 임의의 한쌍의 수를 뽑는데 O(N^2) 만큼이 걸리며, 이렇게 뽑아온 두 수의 최대공약수를 정답에 곱해주는 방법으로 ..

https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 자료구조 문제. 차량 번호로 주어지는 문자열을 숫자에 매칭시켜줘야 한다. 처음 N줄에 들어오는 문자열들을 1부터 차례대로 숫자에 매칭시켜주고, 다음 N줄에 들어오는 문자열들을 앞서 매칭시켰던것을 이용해서 하나의 숫자 배열로 바꿔준다. 숫자 배열을 비교하면서 탐색하는데, 자기 자신의 뒤에서 자기 자신보다 적은 번호를 매칭받은 번호판이 있다면 자기 자신이 반드시 그 번호판의 차량을 추..

https://www.acmicpc.net/problem/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net DP 문제 ( 수열의 유도 및 구현 ) 개념을 알고 모르고의 유무로 난이도가 극명하게 갈린다고 할 수 있는 문제. 이 문제에서 요구하는 수열은 "교란순열" 혹은 "완전순열" 이다. 44라는 숫자가 나오면 한번쯤 의심해볼만할듯. dp[i] = (dp[i-1]+dp[i-2])*(i-1) 교란순열을 구하는 DP 점화식은 다음과 같다. DP[i] : i명끼리 조건에 맞게 선물을 분배하는 경우의 수 유도 각각의 사람의 번호를 $a_i$ , 선물의 번호를 $b_i$ 로 둔다. 어떠한 사람 A가 선물을 하는 경우는 $(N-1..

https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 부분합 + 그리디 문제. 꿀벌 둘을 A,B ( B가 더 오른쪽에 있는 꿀벌 ) 벌통을 C로 두면 크게 세가지 경우의 수가 있을 수 있다. 1. A < B < C 순 배치. 이 경우에 있어서, 꿀통인 C는 오른쪽 끝에 위치하는것이 가장 이득이 되고, 첫번째 꿀벌 A는 가장 왼쪽 끝에 위치하는것이 가장 이득이 된다. 남은 꿀벌 B가 어디에 있느냐에 따라서, (전체 꿀 + B~C 이동에서의 꿀 - A, B지점에서의 꿀) 을 계산해주면 된다. 벌이 있는 곳에서는 꿀을 딸 수 없기 때문에 A, B 지점의 꿀은 계산에서 따로 빼줘야 함에 유의할것...

https://www.acmicpc.net/problem/15483 15483번: 최소 편집 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. www.acmicpc.net 편집거리를 계산해내는 문제. PHP levenstein() 함수를 써먹고싶어지는 문제다 "편집 거리" 로 표현해 두었지만, 실제로 정확한 용어는 levenshtein distance 이다. 처음 발견한 사람이 레벤슈타인 이었나 보다. 위키피디아에서의 레벤슈타인 거리의 정의는 아래와 같다. 해당 점화식을 해석해서 DP로 기술할수 있는 분들은 건너뛰셔도 된다. 레벤슈타인 거리는 보통 O(N^2) DP로 해결하게 되는데, 두 문자열을 A, B라고 할때 DP[i][j]..

https://www.acmicpc.net/problem/16563 16563번: 어려운 소인수분해 첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다. www.acmicpc.net 소인수분해를 빠르게 해주면 되는 문제. "런타임 전의 전처리" 태그를 붙여줘도 나쁘지 않지 싶다. 소인수분해를 $k_i$를 입력받을때마다 직접 해주면 시간초과를 받기 쉽다. 소인수 분해를 위한 할수 있는 모든 준비를 미리 처리해둬서 최대한 빠르게 소인수분해를 해야 한다. 이를 위해서 수 k의 1이 아닌 약수 중 가장 작은 수를 미리 배열에다가 전처리해서 저장해줬다. 이렇게 하면 $k_i$를 입력받았을때..

https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net BFS 응용 pair 로 좌표를 관리해줘도 되는데, 나는 그냥 편의상 x*1000+y 로 묶어서 1차원 배열로 만들어서 BFS를 돌려주었다. 불을 켜는 경우와 실제로 탐색하는 경우를 분리해줘야 하는데, 이를 위해서 방문체크를 위한 vis배열과 불이 켜져있는지 체크를 위한 light 배열 두개를 만들어서 각각 관리해줬다. 프로그램 작성 과정에서도..

https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 말이 세 수의 합이지 브루트포싱하면 O(N^4)이다... 세 수의 합 d와 배열 안의 어떤 수 U가 같아지는 경우를 찾아야 한다. 브루트포스로 접근했을 때 세 수가 O(N^3), U와 매칭시키면서 O(N)이므로 전체 시간복잡도가 O(N^4)가 되어서 시간초과를 받는다. 밋인더미들 알고리즘을 사용해서 선택해야하는 네 수 (세 수 a,b,c 와 U) 를..

https://www.acmicpc.net/problem/1174 1174번: 줄어드는 수 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 수라고 한다. 예를 들어, 321와 950은 줄어드는 수이고, 322와 958은 아니다. N번째로 작은 줄어드는 www.acmicpc.net 브루트포스 문제. 줄어 드는 수 중 가장 큰 수는 9876543210 이므로, 0부터 숫자를 1씩 증가하면서 "줄어드는 수" 인지 체크하는 방법은 TLE를 받게 된다. [9, 8, 7, 6, 5, 4, 3, 2, 1, 0] 순으로 배열된 배열에서 각각의 숫자를 포함하거나 포함하지 않는 경우를 기준으로 브루트포싱을 해주면 순회 횟수가 2^10 밖에 되지 않으므로 무난하게 해결할 수 있..

https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 스위핑 + 유니온파인드 문제 X 좌표가 서로 일부 겹치고 있다면 모종의 방법을 통해서 점프해 이동할 수 있기 때문에, 문제의 입력으로 들어오는 Y좌표와 지문의 조건 점프할 때 다른 통나무 위를 지나면 안된다. 를 무시할 수 있다. 이를 무시하고 x좌표만을 사용한 수직선들로 보면 겹치는 부분이 있는 선분들에 대해서 같은 그룹으로 묶어줘야 함을 알 수 있고,..