정신차려 하프물범 정신차려 하프물범

문제 링크https://www.acmicpc.net/problem/3079 3079번: 입국심사첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)www.acmicpc.net 풀이풀이 설명* 분류: 이진탐색인원수가 10억명, 시간도 10억초 까지의 범위이므로 이진탐색을 떠올린다.대체로 이진 탐색의 기준이 되는 건 구하고 싶은 변수이다. 지금은 시간을 출력하는 것이므로 기준을 시간(초)로 잡는다.  검사대 시간 배열 -> info시간을 기준으로 한다면 start = 가장 짧은 검사대 시간, end = (가장 긴 검사대 시간 * 사람 인원수) 로 하겠다..

문제 링크https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1)www.acmicpc.net 풀이풀이 설명* 분류: 이진탐색n번의 가위질을 할때 만들어지는 조각의 경우의 수를 정하는 기준은 가로로 몇번, 세로로 몇번 자르는지에 따라 달라진다. 예를 들어, 3번 자를 경우1) 세로로 3번 자르는 경우 -> 4조각2)세로로 1번 가로로 2번 자르는 경우 -> 6조각이 나온다. 따라서 가로: row, 세로: col(n-row) 로 친다면, total(조각수) = (row + 1)(col + 1) 이므로,row를 기준으로 탐색한다고 하면 mid 값으로 설정할 수 있다.풀이 코드n, k..

문제 링크 https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 알고리즘 [그리디] 여러 센서의 후보들을 묶는 것으로 생각하면 k개의 묶음을 만들면 된다. 센서를 오름차순하여 좌표 순으로 놓는다. ex. [1, 6, 9, 3, 6, 7] -> [1, 3, 6, 6, 7, 9] 원소간의 차를 표현한 리스트를 만든다. -> diff = [2, 3, 0, 1, 2] 2개의 묶음을 만들기 위해선 1개의 간격을 버리면 된다. -..

문제 링크 https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net 풀이 풀이 설명 우선 문장에 K 포함 유무에 따라 나뉜다. K가 없는 경우 -> M만 있다는 뜻. result를 바로 구할 수 있다. ex. MMM인 경우 max: 111, min: 100 K가 있는 경우, K를 기준으로 나뉘기 수가 결정되므로 K의 위치를 담은 리스트(k_pos)를 전달해준다. def find_max(k_pos) # max 값을 찾는다. k를 포함하여 $5*10^N$ 꼴로 정리한다. 문장의 끝이 k가 아니라면, m으로 끝난다는 뜻이므로 마지막 k의..

문제 https://www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 문제 풀이 회전하는 행렬의 인덱스들을 1차원 배열로 뽑아 놓는다.(반시계방향으로) ex. n, m, r = 2, 3, 2 array = [[1, 2, 3], [4, 5, 6]] [(0, 0), (1, 0), (1, 1), (1, 2), (0, 2), (0, 1)] #위치 인덱스를 담은 배열 회전수 ..

문제https://www.acmicpc.net/problem/2615 2615번: 오목오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호www.acmicpc.net 문제 풀이출력해야하는 제일 왼쪽(세로줄은 가장 위쪽) 좌표를 기준으로 [주 대각선, 세로줄, 가로줄, 부 대각선] 순으로 하여 4개의 방향을 탐색했다. (BFS)단, 조건으로 6개 연속인 바둑알은 승리가 아니므로, 연속된 조건의 count를 자신을 제외하고 각 방향으로 5번까지 진행한 후연속된 바둑알의 갯수가 4개인 경우(기준 좌표 제외)만 승리로 간주한다.n = 19blacks = []white..

문제 링크 https://www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.acmicpc.net 풀이 코드 시간을 줄이기 위해 코드가 길어졌음. -> 제한 시간이 3초라 안길었어도 될 뻔했다.. 주대각선, 가운데열, 부대각선, 가운데행 이 4가지 줄만 바뀌므로, 원래 배열에서 이 4가지를 빼서 before 배열에 담아둔다. after 배열에 바뀌는 부분만 담는다. 각도에 따라 처음 배열의 주 대각선 원소들이 놓여지는 방향이 다르므로, 규칙에 따라 8가지로 나누었다. (시간 제한이 3초나 되기 때문에 누적해서 계속 돌려도 통과하는 것 ..

문제 링크 https://www.acmicpc.net/problem/22858 22858번: 원상 복구 (small) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 풀이 코드 P 카드를 D의 규칙에 따라 이동하는 문제 원래 카드인 P를 다시 찾는 것이므로 결과 카드인 S를 D의 규칙 반대로 이동시키기. P[Di] 카드를 i번째로 옮기기 -> S[i] 카드를 Di로 옮기기 from copy import deepcopy n, k = map(int, input..