https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net # 시간제한이 12초인 문제는 처음본다.. I. 처음에 A, B배열의 모든 원소의 합을 AB배열에 넣고, C, D배열의 모든 원소의 합을 CD배열에 넣은 뒤 정렬 한뒤 투 포인터를 사용해 합이 0인 경우를 count해주려고 했지만, AB = [0, 0, 0, 0], CD = [0, 0, 0, 0]인 경우 합이 0인 경우 두 포인터 중 하나가 무조건 이동하므로 또 0이 나오는 경우..
https://www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net # 랜덤으로 4개를 뽑아서 비교하면 nC4이므로 당연히 시간초과이다. 따라서 '세 용액'문제와 비슷하게, 미리 기준점을 하나 설정하고 나머지 2개의 원소를 '투 포인터' 알고리즘을 사용해서 비교하며 풀었다. 1. 우선 i와 j를 설정한다. (i 와 j의 차이는 3이상) -> 그래야 최소 i와 j사이에 원소 2개이상 존재 2. 기준점인 눈사람 한개를 fix로 설정 (s..
https://www.acmicpc.net/problem/3187 3187번: 양치기 꿍 입력의 첫 번째 줄에는 각각 영역의 세로와 가로의 길이를 나타내는 두 개의 정수 R, C (3 ≤ R, C ≤ 250)가 주어진다. 다음 각 R줄에는 C개의 문자가 주어지며 이들은 위에서 설명한 기호들이다. www.acmicpc.net 1. 영역을 m에 입력받고, 반복문을 돌며 현재 칸이 '#'이 아니라면 bfs함수를 실행한다. * bfs함수: 양의 수를 저장할 변수 sheep과 늑대 수를 저장할 변수 wolf를 선언해준다. 현재 칸이 v이면 wolf += 1, 현재 칸이 k이면 sheep += 1 q에 넣고 bfs를 돌리는데, 다음칸이 맵 밖을 벗어나지 않고 '#'이 아니라면 (nx, ny)를 방문처리해주고, (n..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net # 저번주에 풀었던 '두 용액'에서 한번 더 응용한 문제이다. # 당연히 전체 용액 중 3개를 뽑아 다 구하는 NC3풀이는 안되고 '두 용액' 풀이처럼 투 포인터를 사용하였다. # N이 5000이하여서 반복문을 돌며 용액을 하나 고르고 나머지 N-1개의 용액에서 투 포인터를 사용하여 답을 구했다. 이러면 처음에 용액을 고르는데 O(N), 투 포인터를 사용하면 O(N)이어서 O..
https://www.acmicpc.net/problem/16916 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net # KMP알고리즘을 사용하여 풀었다. # 아직 정확히 이해하진 못해서, 나중에 이해한 뒤 다시 정리할 예정이다. def KMP(): table = make_table() j = 0 for i in range(len(s)): while j > 0 and s[i] != p[j]: j = table[j - 1] if s[i] == p[j]: if j == len(p)-1: return True else: j += 1 return..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net # 투 포인터 문제중에는 대표적인 문제로 잘 알려져 있는 문제이다. # 이분탐색을 사용해서 풀 수도 있다는데..(그건 잘 모르겠고) 1. nums에 용액들의 특성값을 입력받고 오름차순 정렬해준다. 두 용액의 최대 차이는 10억 - (-10억) = 20억이므로, tmp를 20억+1로 설정해준다. 2. 우선 nums배열을 반복문으로 돌며 용액이 모두 양수이면 가장 작..
https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 1. 고속도로 끝과 이미 설치된 곳에 휴게소를 세우지 못하므로 휴게소 위치를 입력받아 rest배열에 넣은다음 처음과 끝 위치도 추가해준 뒤 정렬해준다. 2. count함수: 휴게소가 세워진 위치 사이를 이분탐색을 통해 구한 mid값으로 나눈 값들을 cnt에 저장한다. cnt가 M보다 같거나 작으면 True를 리턴, M보다 크면 False를 리턴해준다. 3. lo = 0,..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net # N이 최대 10만이므로 완전탐색으로 구하는것은 시간초과가 난다. 따라서, 투 포인터 알고리즘을 사용하여 풀었다. 1. 처음 부분합 s에 nums[0]을 넣어준다. (첫번째 숫자 그 자체로 S를 넘을 수 있기 때문에) 그리고 포인터 i, j를 0으로 초기화해준다. 2. 만약 현재 부분합 s가 구하고자 하는 S보다 같거나 크면 왼쪽 포인터가 가리키는 nums의 수(nums[i])를 ..
모르는 사이에 조금씩 조금씩..
