PS

문제 https://www.acmicpc.net/problem/11726 풀이 2x1일때 방법은 (|) 1개이다. 2x2일때 방법은 (||), (=) 2개이다. 2x3일때 방법은 (|||), (|=), (=|) 3개이다. 2x4일때 방법은 (||||), (|=|), (==), (||=), (=||) 5개이다. 이정도에서 규칙을 보면 2x...

문제 https://www.acmicpc.net/problem/9095 풀이 정수 1일때 방법은 (1) 1개이다. 정수 2일때 방법은 (1+1), (2) 2개이다. 정수 3일때 방법은 (1+1+1), (1+2), (2+1), (3) 4개이다. 정수 4일때 방법은 (1+1+1+1), (1+1+2), (1+2+1), (2+1+1), (2+2), ...

문제 https://www.acmicpc.net/problem/2864 풀이 두수의 합이 최솟값이 될려면 상근이가 6을 5로 보면 된다. 마찬가지로 두수의 합이 최댓값이 될려면 상근이가 5를 6으로 본 수를 더하면 된다. 코드

문제 https://www.acmicpc.net/problem/11055 풀이 수열 A에서 각 자리에서 더할 수 있는 최대 합을 계산한 뒤 가장 큰 합을 출력하면 된다. 각 자리에서 최대의 수를 계산하는 방법은 A[i]가 A[i-1]보다 크다면 i에서의 최대 합은 A[i]+A[i-1]이 될것이다. 하지만 무조건 A[i]+A[i-1]이 큰 경우는 아니다...

문제 https://www.acmicpc.net/problem/1912 풀이 계속해서 더할지를 결정할때는 더했을때 값이 줄어들면 안된다는 것을 고려해서 더해야 한다. 더해야 하는 값이 음수이면 더했을때 수가 줄어들기 때문에 최대 합이 될 수 없다. 코드 다른 풀이 A[i]의 수가 최대 값이 될려면 A[i]와 A[i]+A[i-1]중 큰 값을 A[i]에...

문제 https://www.acmicpc.net/problem/2579 풀이 계단을 밟을 수 있는 방법은 두가지 이다. 전전꺼를 안밟고, 전꺼 밟고, 밟기 -> A[i-3] + A[i-1] + A[i] 전전꺼를 밝고, 전꺼 안밟고, 밟기 -> A[i-2] + A[i] 코드

문제 https://www.acmicpc.net/problem/11053 풀이 i번째 수에서의 증가하는 수열의 길이를 구할때, 1 ~ i-1번째 까지의 수들과 비교를 하며 수열의 길이를 최신화 해준다. 단, i번째 수보다 작다고 최신화 하는 것이 아닌 i번째 수의 길이와도 비교해서 최신화 해줘야 한다. > max(dp[j]+1, dp[i]) 코드 비슷...

문제 https://www.acmicpc.net/problem/11054 풀이 풀이는 11055번과 같다. i번째에서 가장 긴 바이토닉 부분 수열을 저장하면 된다. 그러기 위해서 수열 A를 뒤집은 re_A수열을 만들어서 반대로 똑같이 구한다. 그리고 난 뒤 다시 뒤집어서 더하고 1을 빼준다. 1을 빼주는 이유는 i번째 수가 중복되어서 카운트되었기 때문이다...

문제 https://www.acmicpc.net/problem/9461 풀이 P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. 여기서 규칙을 찾아보면 > P(i) = P(i-2) + P(i-3) 이다. 코드

문제 https://www.acmicpc.net/problem/2225 풀이 정수 k개를 더해서 그 합이 n이 되는 경우 k=1인 경우 1가지 밖에 없다. 정수 n수 밖에 없다. k=2인 경우 n+1가지 이다. 예를 들어 n=4라고 한다면 (0+4), (1+3), (2+2), (3+1), (4+0)이렇게 5개 이다. k > 2인 경우 k-1인...

문제 https://www.acmicpc.net/problem/11052 풀이 카드의 개수에 따른 최대 금액계산을 n개까지 하면 된다. P[1] = 1, P[2] = 5, P[3] = 6, P[4] = 7을 예로 들어보면 1개를 구매할때는 P[1]을 사면 된다. dp[1] = P[1] 2개를 구매할때는 P[1] + P[1] 혹은 P[2]의 경우가 있...

문제 https://www.acmicpc.net/problem/2011 풀이 25114를 예로 들어보면 2만 봤을때 (2) 1가지 경우밖에 없다. 25를 봤을때 (2,5), (25) 2가지 경우 251을 봤을때 (25,1), (2,5,1) 2가지 경우 2511을 봤을때 (25,1,1), (2,5,1,1), (25,11), (2,5,11) 4가지...

문제 https://www.acmicpc.net/problem/2751 풀이 입력받은 수를 정렬한뒤 출력한다. 코드

문제 https://www.acmicpc.net/problem/11650 풀이 문제에 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬이라고 나와있다. 그러면 우선 y좌표로 정렬한 다음에 x좌표로 정렬을 하면 된다. 가장 나중에 정렬하는 기준이 가장 중요한 기준이 된다. 그러니 y좌표로 정렬한 다음에 x좌표로 정렬 한다면 결...

문제 https://www.acmicpc.net/problem/11651 풀이 문제에 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬이라고 나와있다. 그러면 우선 x좌표로 정렬한 다음에 y좌표로 정렬을 하면 된다. 가장 나중에 정렬하는 기준이 가장 중요한 기준이 된다. 그러니 x좌표로 정렬한 다음에 y좌표로 정렬 한다면 결...

문제 https://www.acmicpc.net/problem/10814 풀이 이 문제를 풀때 고려해야 하는 것은 2가지 이다. 나이가 증가하는 순으로 정렬 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬 여기서 나이가 같을 경우 먼저 가입한 사람이 앞에 와야 하기 때문에 나이순으로 정렬을 하되, 안정 정렬(Stable sort)를 해야한다. ...

문제 https://www.acmicpc.net/problem/10825 풀이 기준 1, 2, 3, 4순으로 정렬을 하면 된다. sort 함수의 key의 인자를 여러개 넣으면 된다. array.sort(key = lambda x : (x[0], x[1]))식이면 x[0]을 우선순위로 정렬 후, x[0]이 같은 경우 x[1] 기준으로 다시 정렬하게 된다. ...

문제 https://www.acmicpc.net/problem/1463 풀이 정수 X에 사용할 수 있는 연산 3으로 나누기, 2로 나누기, 1빼기 를 보두 비교해본다. 그중 연산 횟수가 가장 적은 값을 저장해 가면서 X까지 가면 된다. 코드 1을 먼저 빼지 않는 코드

문제 https://www.acmicpc.net/problem/10989 풀이 입력받은 수를 정렬하면 된다. 하지만 단순히 정렬하였다면 시간초과나 메모리 초과를 격을것이삳. 주목해야 하는 건 입력받은 수는 10,000보다 작거나 같은 자연수이다. 이를 이용해 계수정렬을 사용하여 정렬해주면 된다. 코드

문제 https://www.acmicpc.net/problem/11652 풀이 파이썬의 딕셔너리를 이용하여 각 숫자들을 카운트 한다음 횟수와 숫자의 크기로 정렬한 다음 출력한다. 코드 다른 풀이 입력 받은 값들을 정렬한 후에 하나씩 카운트해서 간다 전값(i-1)과 현재 값(i)이 다르다면 지금까지 카운트(cnt)한 값과 비교해서 지금까지 카운트한 값이...

문제 https://www.acmicpc.net/problem/11004 풀이 입력받은 수를 배열에 입력한 뒤 정렬한다. index로 K번째 있는 수를 출력한다. 코드

문제 https://www.acmicpc.net/problem/10828 풀이 python의 list로 구현할 수 있다. len()을 이용하여 스택에 정수가 있는지 없는지 확인할 수 있다. 물론 파이썬은 list자체를 조건으로 사용할 수 있다. pop()을 이용해서 pop을 구현하고, list[-1]을 이용하여 top을 구현할 수 있다. 코드

문제 https://www.acmicpc.net/problem/9012 풀이 스택을 이용하여 풀이를 하면 된다. '('인 경우 스택에 push ')'인 경우 스택이 비어있지 않다면 pop 스택이 비어있다면 'NO' 문자열을 다 돌고 난 후 스택이 비어있지 않다면 'NO' 스택이 비어있다면 'YES' 코드

문제 https://www.acmicpc.net/problem/10845 풀이 list로 큐를 구현할 수 있다. pop은 pop(0)으로 가장 앞에 있는 수를 빼면서 출력할 수 있다. back 같은 경우도 list[-1]로 출력할 수 있다. 코드

문제 https://www.acmicpc.net/problem/10866 풀이 python에는 collection이라는 모듈에 deque라는 클래스로 이미 구현되어 있다. 이를 이용해보자. 코드

문제 https://www.acmicpc.net/problem/10808 풀이 python의 ord함수를 이용하여 알파벳을 숫자로 바꾼 다음 97(a의 아스키코드값)을 빼준 값을 인덱스로 더한다. 코드

문제 https://www.acmicpc.net/problem/10809 풀이 a ~ z까지 비교하면서 있다면 그 알파벳의 index를 배열에 넣는다. 코드

문제 https://www.acmicpc.net/problem/10820 풀이 계속 입력 받는게 문제이다. input을 사용한다면 EOFError를 이용하여서 풀면 되고, sys.stdin.readline을 이용한다면 비어있는지 확인함으로써 풀 수 있다. 나머지 소문자, 문자, 숫자, 공백을 구분하는 것은 python의 함수인 islower, isupp...

문제 https://www.acmicpc.net/problem/11655 풀이 아스키코드를 이용하여 13을 더하면 된다. 다만 z혹은 Z를 넘어가는 값은 a 혹은 A부터 다시 시작하는 걸로 철리해줘야 한다. 예를 들어보자 o는 아스키 코드 값이 111이다. 111 + 13은 124인데 z인 122를 넘는다. 이런 경우를 처리해 줘야 한다. o를 97(a의...

문제 https://www.acmicpc.net/problem/10824 풀이 문자열로 입력받은 a, b, c, d를 각각 a+b, c+d로 만든다음 int()로 변환시킨 후 더하면 된다. 코드

문제 https://www.acmicpc.net/problem/1158 풀이 k번째 수를 pop하여 제거하면서 array에 저장한 후 array를 출력한다. 코드 다른 풀이 queue를 이용하여 k번째 까지 pop하고 pop한 값을 다시 push한다. 그리고 가장 앞에 있는 수를 pop하면서 array에 저장한다. 다른 코드

문제 https://www.acmicpc.net/problem/2042 풀이 부분합 세그먼트 트리를 만들어서 풀면 된다. 코드 참고 https://www.crocus.co.kr/648

문제 https://www.acmicpc.net/problem/1168 풀이 리프가 1인 세그먼트 트리를 생성한다. 그렇게 되면 부분별로 몇개를 가지고 있는지 알 수 있게 되고 순서를 알 수 있게 된다. 예제인 '7 3'으로 세그먼트 트리를 만들면 아래와 같다. 코드 참고 https://cocoon1787.tistory.com/433 https://w...

문제 https://www.acmicpc.net/problem/1934 풀이 두 수의 곱 = 최소공배수 * 최대공약수 라는 것만 알고 풀면 된다. 유클리드 호제법으로 두 수의 최대공약수를 구한 뒤 최소 공배수를 구해주면 된다. 코드

문제 https://www.acmicpc.net/problem/1850 풀이 유클리드 호제법으로 최대 공약수를 구한 다음 그 수만큼 1을 출력해주면 된다. 코드

문제 https://www.acmicpc.net/problem/9613 풀이 유클리드 호제법으로 모든 경우의 GCD(최대공약수)를 구한다. 코드

문제 https://www.acmicpc.net/problem/10430 풀이 문제에 있는 그대로 첫째 줄에 (A+B)%C, 둘째 줄에 ((A%C) + (B%C))%C, 셋째 줄에 (A×B)%C, 넷째 줄에 ((A%C) × (B%C))%C를 출력한다. 코드

문제 https://www.acmicpc.net/problem/2609 풀이 유클리드 호제법을 이용하여 두 수의 최대공약수를 구한다음, 두수의 곱 = 최대공약수 * 최소공배수라는 공식을 이용하여 풀면 된다. 코드

문제 https://www.acmicpc.net/problem/11005 풀이 '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'를 가진 문자열을 만든다음 바꾸고자 하는 진법에 맞춰 N을 B로 나눈 나머지의 인덱스를 새로운 문자열에 저장한뒤 거꾸로 출력한다. 코드

문제 https://www.acmicpc.net/problem/1406 풀이 배열을 왼쪽(L) 오른쪽(R)로 나눈 다음에 커서를 기준으로 나눠서 계산 한다. 커서를 왼쪽으로 하나 옮길때는 L에서 pop한다음에 R에 push해준다. 여기서 주의할 것은 R의 경우 뒤에서추가되는 방식이어서 나중에 R을 뒤집어 주어서 출력해줘야 한다. 코드 처음 풀이 pyt...

문제 https://www.acmicpc.net/problem/2745 풀이 2진수 1000(8)을 10진수로 바꿀려면 1000 = (12^3)+(02^2)+(02^1)+(02^0) = 8을 이용한다. 코드 다른 풀이 python의 int함수를 이용해서 풀어본다. int(숫자, 숫자의 진법)이렇게 입력하면 10진수로 바꿔준다. 다른 코드

문제 https://www.acmicpc.net/problem/2089 풀이 진수 계산법을 이용했다. N을 -2로 나누는 방식으로 구현했다. 단 나머지는 1, 0 이 나와야 하므로 -2로 나누어 떨어지지 않는 경우 몫에 1을 더하여 나머지가 1이 되게 한다. $$-13=-2*(7)+1 $$ $$\quad\quad7=-2*(-3)+1 $$ $$\;\,-3=...

문제 https://www.acmicpc.net/problem/1212 풀이 python의 int함수를 이용해서 8진수의 수를 10진수로 바꾼다음에 bin함수를 이용해서 2진수로 바꾼다. 코드 다른 풀이 8진수에서 1자리로 나타낼수 있는 0~7을 2진수로 저장한다음 8진수 한자리씩 2진수로 바꾼다. 다른 코드 다른 풀이 https://blockdm...

문제 https://www.acmicpc.net/problem/11576 풀이 입력된 수를 10진법으로 바꾼뒤 B진법으로 바꾸면 된다. 여기서 입력된 수를 뒤에서부터 계산하여서 10진법으로 바꿔야 한다. 코드

문제 https://www.acmicpc.net/problem/6588 풀이 1000000까지의 소수를 에라토스테네스의 체를 이용해서 구한 뒤 입력 받는 n에 대하여 홀수인 소수를 뺀 값이 소수인지 판단하여 출력한다. 코드

문제 https://www.acmicpc.net/problem/11653 풀이 에라토스테네스의 체로 n까지의 소수를 구한 다음 가장 낮은 소수부터 나누어 떨어지면 출력하고 다시 그 소수로 나눠보는 방법을 사용했다. 코드 다른 풀이 어차피 가장 작은 소수는 2이고, 2로 계속 나누다 보면 2의 배수로는 나눌 수 없어질 것이다. 그러면 다음 소수인 3으로...

문제 https://www.acmicpc.net/problem/2004 풀이 팩토리얼을 사용해서 $n\choose m$을 구한뒤 10으로 나누는 방식으로 정답을 구하려고 하면 너무 큰 n,m조건때문에 시간초과가 날 수 있다. 0의 개수는 2와 5의 쌍의 개수라고 할 수 있다. 즉, $n\choose m$에서 2와 5의 개수를 구한 뒤 작은 개수가 0의 개...

문제 https://www.acmicpc.net/problem/1676 풀이 $n!$을 구한다음에 10으로 몇번 나눠 떨어지는지 카운트 한다. 코드

문제 https://www.acmicpc.net/problem/1260 풀이 DFS와 BFS를 이용해서 탐색 순서를 나타낸다. 코드

문제 https://www.acmicpc.net/problem/11724 풀이 DFS를 이용해서 연결 요소들을 카운트 한다. DFS를 한번 했다는 것은 1개의 연결 요소를 구했다는 말이다. 물론 BFS로도 풀 수 있다. 파이썬에서 DFS를 이용해서 풀다가 RecursionError가 날 수 있다. 제귀 깊이의 한계때문에 나는 Error이니 제귀 깊이를 변...

문제 https://www.acmicpc.net/problem/1707 풀이 BFS를 이용해서 그래프를 탐색한다. 노드를 방문할때마다 group으로 표시를 한다. 연결되어 있는 노드와 같은 group인지 판단하면서 이분그래프를 판단한다. 코드

문제 https://www.acmicpc.net/problem/10451 풀이 1 ~ n까지의 배열을 만들고, 입력받은 순열과 그래프를 만든다. 만든 그래프를 DFS를 이용해서 탐색한다. 연결되어 있는 그래프는 DFS한번에 1개씩 카운트 한다. 코드 더 좋은 풀이 굳이 1~n까지의 배열을 안만들고, 반복문을 이용해 연결되어 있는 노드를 다 방문하고, ...

문제 https://www.acmicpc.net/problem/2331 풀이 다음 항(n)을 계산한 다음 n이 순열에 있는지 확인하고, 없다면 순열에 넣고, 있다면 n의 index를 출력한다.(n이 있다는 것은 n부터 반복된다는걸 의미한다.) 코드

문제 https://www.acmicpc.net/problem/9375 풀이 입력받은 옷을 종류별로 나눠서 카운트 한다. 카운트 한 값에 각각 1을 더해서 곱한뒤 1을 나눈다. 경우의 수 를 구하는 것이다. 1씩 더하는 이유는 입지 않는 것도 선택하기 위해서 이고, 1을 빼는 이유는 아무것도 안 입었을 경우를 빼기 위해서 이다. headgear : ...

문제 https://www.acmicpc.net/problem/2667 풀이 입력받은 지도를 DFS로 탐색하면서 카운트한다음 오름차순으로 출력하면 된다. DFS를 시작한 횟수 = 단지의 수, DFS가 호출된 수 = 단지내의 집의 수 이다. 코드 테스트 케이스 https://www.acmicpc.net/board/view/108889

문제 https://www.acmicpc.net/problem/1541 풀이 -를 기준으로 - 뒤에 +가 나오면 먼저 한다.(다른 -가 나오거나, 끝날때 까지) -뒤에 -가 나오면 앞에 있는 -를 먼저 한다. 마친 후 남은 연산을 한다. 코드 반례 1-2-3+4 / -8 1000 / 1000 1-1-1 / -1 1+2-3+4+5 / -9 1-1 / 0...

문제 https://www.acmicpc.net/problem/4963 풀이 DFS를 이용하여 갈 수 있는 곳을 탐색한뒤 마칠때마다 count해준다. 코드

문제 https://www.acmicpc.net/problem/1780 풀이 탐색하는 종이의 첫번째 수를 flag로 기억한 다음 종이를 탐색하면서 flag와 같은 수 인지 본다. 종이를 다 돌때까지 같다면 해당 수를 +1 시킨다. 만약 다르다면 종이를 9등분해서 각각 다시 위의 과정을 반복한다. 코드 비슷한 문제 2630번 : 색종이 만들기 / 풀이 ...

문제 https://www.acmicpc.net/problem/2630 풀이 탐색하는 종이의 첫번째 수를 flag로 기억한 다음 종이를 탐색하면서 flag와 같은 수 인지 본다. 종이를 다 돌때까지 같다면 해당 수를 +1 시킨다. 만약 다르다면 종이를 4등분해서 각각 다시 위의 과정을 반복한다. 코드 비슷한 문제 1780번 : 종이의 개수 / 풀이

문제 https://www.acmicpc.net/problem/7576 풀이 BFS를 이용해서 익은 토마토가 있는 곳에서 4곳을 탐색한다. 몇일인지 세는 방법은 숫자를 1씩 증가시키면서 가면 된다. 주의해야 할 것은 처음부터 익은 토마토가 있는 곳을 queue에 넣어줘야 한다는 것이다. 그래야지만 각각의 익은 토마토에서 하루씩 계산할 수 있다. 코드 ...

문제 https://www.acmicpc.net/problem/2178 풀이 BFS를 이용해서 이동을 한다. 몇번째 칸인지는 전에 있던 칸에서 +1하는 식으로 계산한다. 코드 비슷한 문제 7576번 : 토마토 / 풀이 2146번 : 다리 만들기 / 풀이

문제 https://www.acmicpc.net/problem/2146 풀이 섬들을 숫자로 마킹을 해줘서 섬들을 따로 구별할 수 있게 해야한다. 구별된 섬들을 기준으로 다른 섬들로의 다리를 계산 하면서 최솟값을 계속 갱신한다. 코드 메모리 초과 사례 메모리 초과가 나는 원인이었던 init함수이다. 섬을 k로 바꾸는 과정에서 queue에서 pop하면서...

문제 https://www.acmicpc.net/problem/1991 풀이 트리를 딕셔너리에 {노드:[leftchild, rightchild]}로 저장을 한다. 그리고 왼쪽과 오른쪽을 제귀함수로 호출한다. inorder는 (왼쪽 자식)/(노드)/(오른쪽 자식) preorder는 (노드)/(왼쪽 자식)/(오른쪽 자식) postorder는 (왼쪽 자식)/(...

문제 https://www.acmicpc.net/problem/12015 풀이 이 문제는 dp를 이용해서 풀면 시간초과가 날 수 있다. 이분탐색을 이용해서 dp에 증가하는 수열을 최신화 하면서 생성한다. dp의 첫번째 수는 arr의 첫번째 수를 넣어놓고 시작한다. arri]가 dp[-1보다 크다면 그냥 dp에 넣으면 된다. arri]가 dp[-1보다 작거...

문제 https://www.acmicpc.net/problem/1074 풀이 분할 정복으로 2by2까지 자른다음에 하나하나 찾아보는 식으로 문제를 풀었는데, 시간초과가 났다. 문제를 어떻게 풀까 고민하다가 r, c가 포함된 구간만 분할정복으로 나누면 되지 않을까 했다. r, c가 포함된 사분면으로 계속 나누면서 count를 증가하면 된다. 여기서 coun...

문제 https://www.acmicpc.net/problem/27930 풀이 KOREA 와 YONSEI를 저장한 배열을 0번째 부터 차레대로 비교하면서 수를 증가시키면 된다. 주변을 재거하고 뭐가 뭔저 나오느냐이기 때문에, 나올때마다 index를 증가시켜 먼저 index를 충족시키는 쪽이 정답이다. 코드

문제 https://www.acmicpc.net/problem/1697 풀이 BFS를 이용해서 x에서 갈 수 있는 곳을 다 가보면서 k인지 비교한다. 시간은 x에서의 시간 +1을 해주면 그게 x 다음번에 갈 곳에서의 시간이다. 코드 아쉬운 점 BFS문제인지도 모르고, 수학적으로 계산을 하다가 메모리 초과와 시간 초과를 보았다. 안풀린다면 답을 보는 것...

문제 https://www.acmicpc.net/problem/1927 풀이 최소힙을 만들어서 푸는 문제이다. 코드

문제 https://www.acmicpc.net/problem/11279 풀이 최대힙을 구현하는 문제이다. 코드

문제 https://www.acmicpc.net/problem/11725 풀이 BFS와 DFS를 이용해서 풀 수 있다. 노드 2개가 주어질때 각 노드를 연결하여 graph에 넣고 이 그래프를 1부터 탐색한다. 과 연결되어 있는 것은 무조건 1의 자식이고, 그 자식과 연결되어 있는 것은 자식의 자식임을 이용한다. 코드(BFS) 코드(DFS)

문제 https://www.acmicpc.net/problem/1167 풀이 DFS를 이용해서 1에서 가장 먼 노드(v)를 찾고, 다시 v에서 가장 먼 노드를 찾는다. v에서 그 노드까지의 거리가 트리의 지름이 된다. 코드 비슷한 문제 1967번 : 트리의 지름 / 풀이

문제 https://www.acmicpc.net/problem/1967 풀이 DFS를 이용해서 정점(n)에서 가장 먼 노드를 찾는다. 트리의 지름을 구하는 방법은 n에서 가장 먼 정점(i)를 찾고, 거기서 가장 먼 정점(j)를 찾으면 정점(i) ~ 정점(j)까지의 거리가 트리의 지름이된다. 코드 비슷한 문제 1167번 : 트리의 지름 / 풀이

문제 https://www.acmicpc.net/problem/1654 풀이 매개 변수 탐색을 이용해서 문제를 풀 수 있다. mid = (1+가장 긴 랜선 길이)/2 를 기준으로 랜선들을 잘랐을때 만들 수 있는 랜선의 개수를 계산해서 만약 원하는 랜선의 개수보다 많다면 기준이 되는 길이를 더 길게 잡아서 다시 구한다. 원라는 랜선의 개수보다 작다면 기준을...

문제 https://www.acmicpc.net/problem/2805 풀이 매개 변수 탐색을 이용해서 문제를 풀 수 있다. 처음은 1~'가장 큰 나무의 높이' 의 중앙을 찾고(mid), 절단기를 mid로 설정했을때 나오는 나무들의 길이가 M보다 크다면 mid를 줄여가면서 M에 맞는 최대값을 찾는 방법으로 문제를 풀 수 있다. 만약 나무들의 길이가 M보다...

문제 https://www.acmicpc.net/problem/2110 풀이 이 문제를 풀때는 간격을 기준으로 생각해봐야 한다. 간격을 얼마로 할지 정하는 문제이기에 1(가장 작은 간격) ~ array-1] - array[0 사이에 정답이 있을 것이다. 그렇다면 조건을 만족하는 간격을 매개 변수 탐색으로 찾으면서 조건에 맞다면 간격을 늘려가는 식으로 문제...

문제 https://www.acmicpc.net/problem/10816 풀이 python의 딕셔너리를 사용하여 key값을 카드에 적힌 숫자, value를 개수로 하나씩 증가하면서 딕셔너리를 만들어준 다음에 출력해주면 된다. 또 다른 방법으로는 array를 이중배열로 만들어 arrayi에는 카드의 숫자, arrayi에는 카드의 개수를 저장한다음 이분 탐...

문제 https://www.acmicpc.net/problem/11728 풀이 배열 A와 배열 B를 가리키는 두개의 포인터(aindex, bindex)를 만든다.두개의 포인터가 가리키는 값을 비교하면서 작은 것들을 넣고, 해당 포인터를 1증가시킨다. 같다면 둘다 넣어주는 식으로 풀이했다. 코드 코드(그냥 파이썬)

문제 https://www.acmicpc.net/problem/1992 풀이 탐색을 시작할 첫번째의 값이 데이터 값이 변하지 않는다면 압축할 수 있다. 즉 출력할 수 있다. ()는 분할되는 과정에서 분할됨을 나타낸다. 즉, 데이터의 구간들이 값이 같다면 출력하고, 다르다면 4분할 하면서 푼다. 코드

문제 https://www.acmicpc.net/problem/2447 풀이 nn 배열을 선언한다음 9개의 구간으로 나눈다. 북서, 북, 북동, 서, center, 동, 남서, 남, 남동 이렇게 9개 구간으로 나누어서 들어간다. 그러다 1칸을 보개 될 경우 을 입력한다. 여기서 center는 아예 보지 않는 것으로 *을 입력하지 않는다. 코드 다른 풀...

문제 https://www.acmicpc.net/problem/11729 풀이 n개의 원반을 장대 1에서 장대3으로 옮기는 최소한의 횟수는 $2^n-1$이다. 재쉬는 n-1개의 원반을 1에서 2로 2에서 3으로 옮기는 방식으로 진행된다. 코드 참고 https://mgyo.tistory.com/185

문제 https://www.acmicpc.net/problem/1517 풀이 이 문제를 버블정렬를 구현하면서 count한다면 시간초과가 난다. 이 문제는 0~(i-1)의 원소들 중 arr[i]보다 작은 원소들의 개수를 카운트 한다. 이것을 병합정렬을 구현해서 왼쪽 리스트와 오른쪽 리스트를 합칠때 오른쪽 리스트의 값을 추가할때 왼쪽 리스트에 남은 원소개수를...

문제 https://www.acmicpc.net/problem/2448 풀이 3일때는 그냥 출력하면 된다. 6일때부터는 3군데(가운데, 오른쪽, 왼쪽)으로 쪼개서 크기가 3까지 갔을때를 구하면 된다. 코드 참고 https://ku-hug.tistory.com/149

문제 https://www.acmicpc.net/problem/5525 풀이(50점) 하나하나 비교하면서 처음이 같다면 그 뒤에것도 비교한다. 이렇게 풀면 50점이 나온다. 시간복잡도가 너무 커지기 때문이다. 코드(50점) 풀이(100점) P2에는 P1이 2개 들어있다. IOIOI = IOI+IOI(중간에 I는 겹친다고 생각해보자) 그렇다면 PN에는 ...

문제 https://www.acmicpc.net/problem/11047 풀이 가지고 있는 동전 중 가장 큰 동전부터 K에 얼마나 들어가는지 계산하는 방법으로 풀면 된다. 한번씩 빼는 방법 보다는 나누기와 나머지 연산을 이용해서 가장 큰 동전이 K에 들어갈 수 있는 방법을 계산하는게 빠르다. 코드

문제 https://www.acmicpc.net/problem/2875 풀이 만들 수 있는 팀의 개수를 구한다음 팀이 되지 못한 인원들을 인턴쉽으로 보내고, 인원이 부족하다면 팀에서도 사람을 데려와서 보내면 된다. 코드

문제 https://www.acmicpc.net/problem/11286 풀이 힙 자료구조를 사용해서 최소힙을 만들면 된다. 다만 절댓값을 기준으로 최소 힙을 만들고, 절댓값이 같은 경우 실제 값을 비교하는 조건식을 추가해 주어야 한다. 코드

문제 https://www.acmicpc.net/problem/7569 풀이 BFS를 이용해서 상하좌우위아래를 탐색한다. 처음에 상자에 있는 토마토들을 queue에 넣는다. 그 후 탐색해서 queue에 넣을때마다 +1해서 넣어준다.+1을 한다는 것은 하루가 지났다는 것을 의미한다. 코드

문제 https://www.acmicpc.net/problem/10610 풀이 배수판정법을 이용해서 문제를 풀 수 있었다. 배수판정법은 $m$이 $n$의 배수임을 판단할때 $n$의 이론적 성질을 이용해서 판단하는 방법이다. > $30$의 배수 판정법은 > 1. 각자리 수의 합이 3의 배수이다. > 2. 1의 자리가 0이다. 이 두가지를 이용해서 풀 수...

문제 https://www.acmicpc.net/problem/1783 풀이 문제의 조건중에 이동 횟수가 4번보다 적지 않다면, 이동 방법을 모두 한 번씩 사용해야 한다.는 조건이 있다. 그렇다면 이동 방법을 모두 사용하지 못하는 경우를 살펴 보자. 세로의 길이가 1인 경우 : 세로의 길이가 1인 경우는 이동을 아예 못하기 때문에 이동 횟수가 0이다. ...

문제 https://www.acmicpc.net/problem/1931 풀이 가장 많은 회의를 찾는 방법을 찾을때 고려해야 하는 것은 끝나는 시간이 빨라야 한다. 가장 최근의 끝나는 시간과 시작하는 시간이 가까워야 한다. 이 두가지를 적용해서 우선 시작시간으로 정렬을 한 다음 끝나는 시간으로 정렬을 한다. 가장 첫번째 회의를 배정한다.(가장 빨리끝나는...

문제 https://www.acmicpc.net/problem/11399 풀이 이 문제의 핵심은 인출하는 시간이 짧은 사람부터 먼저 인출하게 만드는 것이다. 그러기 위해서 오름차순으로 정렬한다음 0~i번째의 합을 i가 n이 될때까지 계속 더하면 된다. 코드

문제 https://www.acmicpc.net/problem/2873 풀이 이 문제는 3가지 경우로 나눠서 볼 수 있다. > 1. r이 홀수일때 r이 홀수라면 모든 부지를 방문할 수 있다. 단 $ㄹ$자 모양으로 방문하여야 한다. > 2. c가 홀수일때 c가 홀수여도 모든 부지를 방문할 수 있다. 단 $N$자 모양으로 방문하여야 한다. > 3. r,...

문제 https://www.acmicpc.net/problem/1744 풀이 곱해야 할때 고려해야 하는 것은 3가지이다. 두 수 모두 양수일때 큰것과 큰것을 곱해야 한다. 두 수 모두 음수일때 작은것과 작은것을 곱해야 한다. 0일때는 곱하지 못한 음수중 가장 작은 것을 곱해야 한다. 이렇게 3가지를 고려하기 위해 음수와 양수를 따로 저장합니다. 양수는...

문제 https://www.acmicpc.net/problem/1476 풀이 나머지 연산을 이용해서 연도가 들어날때마다 각 범위를 나머지 연산해서 입력값이랑 같아지면 그 때의 년도를 출력한다. 코드 더 좋은 풀이 증가하는 연도(year)에서 입력받은 연도(E,S,M)을 빼고, 각 범위의 최대 값으로 나눴을 때 나머지가 0이라면(배수라면) 그 연도(ye...

문제 https://www.acmicpc.net/problem/1107 풀이 가능한 모든 수를 확인하면서 가장 적게 버튼을 누르는 횟수를 갱신한다. 0~1000000까지의 채널들을 다 확인해 본다. 부서진 숫자로 만드는 채널은 제외한다. 1000000인 이유는 채널을 아래에서 위로 탐색하는 방법과 위에서 아래로 탐색하는 방법 둘다 사용해 봐야 하기 때문이...

문제 https://www.acmicpc.net/problem/1451 풀이 직사각형을 3개로 나누는 방법은 총 6가지밖에 없다. 이 6가지를 모두 실행하면서 가장 큰 값을 갱신한다. 코드

문제 https://www.acmicpc.net/problem/10819! 풀이 주어진 정수들의 모든 경우의 수를 구한다. 즉 모든$nPn$을 구한다음 해당 식으로 계산한 값의 최댓값을 출력한다. 코드

문제 https://www.acmicpc.net/problem/10971 풀이 DFS를 이용해서 시작 노드에서 모든 노드를 거쳐 다시 시작노드로 돌아오는 것을 확인하면 된다. 다시 시작노드로 돌아온다면 최소비용을 최신화 시켜주면 된다. 코드

문제 https://www.acmicpc.net/problem/1963 풀이 에라토스테네스의 체를 이용해서 10000까지의 소수를 찾는다. 그후 BFS를 이용해서 가능한 모든 소수들을 탐색하면서 횟수를 저장한다. 코드

문제 https://www.acmicpc.net/problem/9019 풀이 BFS를 이용해서 A에서 갈 수 있는 모든수를 가면서 B가 나올때 까지 명령어를 저장한다. 문자열로 풀기보다 숫자로 푸는것이 시간단축이 된다. Python의 경우 PyPy3로 제출해야한다. 코드 참고 https://paris-in-the-rain.tistory.com/94

문제 https://www.acmicpc.net/problem/1525 풀이 처음 주어진 모양에서 갈 수 있는 모든 경우의 수를 가보면서 정리된 상태가 된다면 횟수를 반환하는 것이다. 모든경우를 가보면서 횟수를 저장하는건 BFS를 이용하면 된다. 입력값을 문자열로 받고, "123456780"를 정리된 상태로 생각하고 문제를 풀면 된다. 코드

문제 https://www.acmicpc.net/problem/2251 풀이 각 a, b, c물통에 대하여 물을 옮길 수 있는 모든 경우의수를 고려하면 된다. 각 경우를 고려하다가 a물통에 물이 비어있는 경우 c물통에 있는 물의 양을 저장하면 된다. $추가$ : 예를 들어 a -> b로 물을 옮길때 > $w = min(a,maxb - b)$ $a = a...

문제 https://www.acmicpc.net/problem/2186 풀이 DFS를 이용해서 단어의 첫번째 문자에서 시작해서 가능한 모든 경우를 count한다. 코드

문제 https://www.acmicpc.net/problem/3108 풀이 우선 입력받은 사각형은 bord에 1로 마크한다. 그리고 BFS를 이용해서 한붓으로 그릴 수 있는 사각형들을 체크한다. 몇번 BFS에 들어가는지가 중요하다. (0,0)에 있는 사각형이 있다면 1을 빼줘야 한다. 코드

문제 https://www.acmicpc.net/problem/1389 풀이 플로이드-워셜 알고리즘을 이용해서 모든 노드쌍에 대한 최단거리를 구한다음에 최솟값을 구한다. 코드

문제 https://www.acmicpc.net/problem/6064 풀이 이 식은 x, y를 달성했을때를 판별하는 식이다. 여기서 count를 1씩 증가시키면 시간초과가 난다. 그렇기 때문에 count를 m으로 증가시키는 것이다. 이 풀이를 해석하자면, 처음 x를 고정시킨 다음에 m으로 x, y를 증가시킨다고 해석하면 된다. 예를 들어 M:10,...

문제 https://www.acmicpc.net/problem/6064 풀이 이 식은 x, y를 달성했을때를 판별하는 식이다. 여기서 count를 1씩 증가시키면 시간초과가 난다. 그렇기 때문에 count를 m으로 증가시키는 것이다. 이 풀이를 해석하자면, 처음 x를 고정시킨 다음에 m으로 x, y를 증가시킨다고 해석하면 된다. 예를 들어 M:10,...