완전 탐색 배열을 모두 순회하는데 O(100 * 100) 이 필요하다. 최대 - 최소의 경우, 차이가 1이라 할 때, 차이가 1이 되는 최대, 최소의 쌍은 (1, 2), (2, 3), (3, 4), ... (199, 200) 식이다. 차이가 최대 200까지 발생하니, 쌍을 구하는 것에 대한 시간 복잡도는 (199 + 198 + 197 + ... + 0) = 약 20,000 정도 된다. 총 시간 복잡도는 O(100^2) * O(199 + 198 + ... + 0) = 2억으로 시간 초과가 발생한다. 완전 탐색 최적화 배열을 일부만 탐색할 수는 없으니, 쌍을 구하는 과정에서 최적화를 수행해야 한다. 하지만, 어떤 최대, 최소의 차이 A를 구하기 위해선, 이를 만족하는 모든 경우를 확인해야만 한다. 따라서, ..
Koala - 9기
1966번: 프린터 큐 (acmicpc.net) 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 코드 코드 설명 n개 문서들의 중요도를 차례로 나열한 것을 큐인 dq에 받아 저장 dq를 복사한 큐 dqc 생성 몇 번째로 출력되는지 궁금한 문서의 위치가 m이므로 dqc 큐에 있는 m위치에 있는 문서의 중요도를 -1로 변경 중요도는 1이상 9이하 정수이고, max 함수를 사용할 것이기 때문에 중요도 변경 시 max 값에 걸리지 않기 위해 -1로 설정 중요도가 같은 문서가 있을 수 있으므로 dqc의 중요도만 변경하고 ..
https://www.acmicpc.net/problem/16955 16955번: 오목, 이길 수 있을까? 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 www.acmicpc.net 문제 구사과와 큐브러버는 10×10 크기의 바둑판에서 오목을 하고 있다. 턴은 구사과가 먼저 갖는다. 바둑판의 상태가 주어진다. 구사과가 턴을 한 번 더 가졌을 때, 이길 수 있는지 구하는 프로그램을 작성하시오. 오목에서 승리했다는 것은 자신의 돌이 5개 이상 연속한다는 것이다. 연속은 가로, 세로, 대각선 방향 모두 가능하다. 입력 총 10개의 줄에 바둑판의 상태가 주어진다. ..
https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은..
https://www.acmicpc.net/problem/7117 7117번: Sevens, twos and zeros The number s as described above must be output on the screen. If it is not possible to find the corresponding value of s to the given value of n, output one word "NAV". www.acmicpc.net 문제 분석 난이도 플래티넘5 분류 중간에서 만나기(MITM), 그래프 탐색, 너비우선탐색 들어가기 전에 중간에서 만나기 알고리즘을 알고 있어야 쉽게 풀 수 있는 문제 문제 최대 길이가 20이고 2, 7, 0으로 이루어진 0으로 시작하지 않는 수가 있다. 이 수들..
https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 코드 문제 풀이 문제에서 가장 앞에 있는 문서의 중요도가 가장 높으면 바로 인쇄한다 = popleft 를 사용해야 하므로 deque 를 사용. for 문을 활용하여 T 만큼 반복, 반복문 내에서 N,M 과 N개의 문서 중요도 a를 입력. whlie을 활용하여 원하는 문서 a[M] 을 출력할 때 까지 반복. 1) a[M] 이 a의 맨 앞에 있을 때, 1-1) 이를 a의 가장 큰 수와 비교하여 a[..
문제 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다. 비어있는 칸 중에서 좋아하는 학생이 인접한..
문제 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 코드 풀이 입력되는 숫자를 모두 받아서 정렬하는 방법으로 코드를 짰는데 메모리초과만 나서 heapq를 쓰는 방안을 찾게 되었다. ㅇheapq의 크기가 5보다 크면 최솟값을 빼내고 입력받은 값을 집어넣고, 아니면 그냥 넣고 크키가 5일때와 그 이상일때로 나누어 뒤에서 5번째인 수를 출력한다.
문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 코드 풀이 arr에 체스판을 입력받은 뒤 i와 j로 8*8을 이동할 for문을 만든다. i와 j를 시작점으로 총 8개의 칸을 돌아가며 (0,0)이 W일 상황 cnt1과 B일 상황 cnt2를 찾아 더 작은 값을 result에 저장하고, 저장된 result값의 최소값을 출력한다.
문제 7795번: 먹을 것인가 먹힐 것인가 (acmicpc.net) 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제설명 이 문제 풀이에 대해 시간 초과 오류 계속 발생하는데 이를 해결하기 위한 방법은 바로 '이분 탐색' 이다. 생명체 A의 각 요소와 생명체 B의 각 요소를 비교해 A의 요소 값 > B의 요소 값을 구하는 과정을 가진다. 이를 위해 생명체 A와 B를 각각 리스트로 표현한다. A[i] 와 B[0] ~ B[i]의 크기 비교를 리스트 A의 크기..
문제 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net Algorithm 2차원 리스트를 key 매개변수를 이용해 문제의 규칙에 따라 정렬한다. 정렬된 리스트 A에서 첫번째 열에 K가 저장되어 있는 행을 찾고 그 행의 위치를 i로 기억해둔다. 그리고 1등부터 N등까지의 등수를 의미하는 리스트 B를 만들고 A는 정렬되어 있기 때문에 K 국가의 등수는 K의 A에서의 행의 위치가 B에서의 위치가 된다. A는 정렬되어 있으므로 모든 메달의 개수가 같은 국가를 찾기 위해서 인접한 행만 비교하면 된다..
[문제] https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net [풀이] 입력을 받은 후 lambda를 사용해 금, 은 동 메달 순으로 정렬한다 정렬된 리스트를 기준으로 arr[i][0]이 찾아야하는 K와 같을 때 순서를 출력한다 [코드]
