본문 바로가기

분류 전체보기

 (171)
[BOJ] [Python] 11055번 : 가장 큰 증가 부분 수열 [1, 100, 2, 50, 60, 3, 5, 6, 7, 8]를 예로 이해하고 해결해보자. dp에는 자기 자신의 값이 초깃값으로 들어가 있다. 이제 0번째부터 9번째까지 하나씩 확인하며, dp를 늘려줄 것이다. 규칙은 아래와 같다. n번째) 0번째부터 n-1번째까지 돌면서, 1. n번째 수보다 작은 값을 찾는다. 2. 작은 값들이 가진 dp중 최대의 dp를 n번째 dp에 더해준다. 예를 들어, 지금 4번째라고 한다면 50보다 작은 값은 1과 2이다. 1보다 2의 dp값이 더 크므로, 2의 dp값에 50을 더해준다. 더해진 값은 50의 dp값이 된다. 마지막에 dp 리스트의 최댓값을 출력하면, 가장 큰 증가 부분 수열의 합을 찾을 수 있다. num = int(input()) li = list(map(int..
[BOJ] [Python] 1213번 : 팰린드롬 만들기 예외 처리를 먼저 생각해보자. 알파벳이 홀수인 게 2개 이상이면, 팰린드롬이 될 수 없다. 따라서 이때, I'm Sorry Hansoo"를 출력한다. 팰린드롬은 start, mid, end로 나눠서 구현할 수 있다. start에는 // 2를 이용해서 현재 알파벳의 개수 나누기 2의, 몫이 들어간다. mid에는 % 2를 이용해서 홀수 개수인 알파벳을 1개 넣어준다. end는 start의 역순이다. 참고로 딕셔너리를 중간에 sort 해줬기 때문에, 조건 중 하나인 '사전순으로 앞서는 것을 출력'은 신경 쓰지 않아도 된다. string = input() dic = {} for s in string: dic[s] = 0 for s in string: dic[s] += 1 count = 0 new_dic = so..
[BOJ] [Python] 2193번 : 이친수 문제의 조건을 살펴보자. 1. 0으로 시작하지 않는다. 2. 1이 두 번 연속으로 나타나지 않는다. 이를 간단하게 나타내보자. 1. 1로 시작한다. 2. 1뒤에는 0이 온다. 3. 0뒤에는 1또는 0이 온다. 코드를 작성하기 전, 예시를 몇 개 작성해보자 위 예시를 표로 나타내면 아래와 같다. 처음에 찾은 규칙이랑 같이 고려해보면 점화식을 찾을 수 있다. n의 0의 개수 : 0개 ( n = 1 ) n의 1의 개수 : 1개 ( n = 1 ) n의 0의 개수 : n -1의 0의 개수 + n - 1의 1의 개수 ( n > 1 ) n의 1개 개수 : n - 1의 0의 개수 ( n > 1 ) num = int(input()) zero = 0 one = 1 for _ in range(num - 1): tmp = z..
[BOJ] [Python] 2156번 : 포도주 시식 3잔 연속 마실 수 없다는 조건을 고려하여 점화식을 세워야 한다. 조건을 고려하면, 4번째 잔부터 점화식이 적용된다. 따라서 1~3번째 잔까지는 적절히 초깃값을 넣어준다. 점화식을 살펴보자. 현재 마셔야 하는 컵 기준, 최고의 선택을 해야 한다. 3잔 연속으로 안 마시기 위한 선택권은 2개이다. 1. 3번째 앞의 컵 DP + 1번째 앞의 컵 값 + 현재 컵 2. 2번째 앞의 컵 DP "틀렸습니다" 아래 코드는 틀린 코드이다. 완벽하다고 생각했는데, 틀렸다. 왜 틀렸을까? num = int(input()) li = [] for _ in range(num): li.append(int(input())) dp = [0] * num for i in range(0, num): if i == 0: dp[0] = li..
[BOJ] [Python] 11726번 : 2xn 타일링 타일링해야 하는 직사각형은 2 x N으로 고정이기 때문에, 1 x 2 직사각형 2개를 1개로 보고 풀었다. 2 x 1 타일로만 이루어지는 경우는 나중에 + 1 을 해주는 방식으로 처리했다. 찾은 규칙 N의 짝 홀수 상관없이 앞에 방법(순서를 바꿨을 때 1 x 2 과 2 x 1의 개수가 같으면, 같은 방법이라 생각한다.)에 2 x 1 타일을 1개 붙여서 가져간 다음, 순서를 고려한 것이 총 경우의 수[답에서 요구하는 방법의 수]가 된다. 거기에 짝수일 경우에는 1 x 2 직사각형을 이용한 방법 1개를 추가한다. 코드로 나타내기 한 방법에 1 x 2 와 2 x 1이 몇 개가 쓰였는지 개수만 센다. 그리고 다음 순서에 그 전 순서의 방법들에 사용됐던 2 x 1 타일 수에 1을 더해주는 것이다. 짝수일 경우에는..
[BOJ] [Python] 11399번 : ATM 시간이 짧은 순으로 처리해서 더하면, 최소 합이 된다. 2가지 방법으로 풀 수 있다. 1. 가로 tmp에 자기 차례까지 걸리는 시간을 저장한다. result는 각각 자기 차례까지 걸리는 시간의 총합을 저장한다. num = int(input()) li = list(map(int, input().split())) li.sort() tmp = li[0] result = 0 for i in range(len(li) - 1): tmp += li[i + 1] result += tmp print(result + li[0]) 2. 세로 인출 시간이 짧을수록 많이 더해지는 점을 이용한다. num = int(input()) li = list(map(int, input().split())) li.sort(reverse = ..
[BOJ] [Python] 1697번 : 숨바꼭질 BFS를 이용해서 풀었다. li 리스트에는 방문할 위치를 차례대로 넣고, 방문하면 제거한다. 그리고 dp 리스트를 이용해서, 방문했던 위치는 재방문하지 않는다. 수빈이가 동생을 찾기까지 신경 쓴 것 1. 0
[BOJ] [Python] 1003번 : 피보나치 함수 처음에는 재귀함수를 이용해서 해결하려고 했다. 하지만 시간초과가 발생한다. for문으로 바꾸니 해결됐다. 0의 개수와 1의 개수를 각각 계속 누적시켜서 더해준다. num = int(input()) for _ in range(num): n = int(input()) zero = [0] * (n + 1) one = [0] * (n + 1) for i in range(n + 1): if i == 0: zero[0] = 1 elif i == 1: one[1] = 1 else: zero[i] = zero[i - 2] + zero[i - 1] one[i] = one[i - 2] + one[i - 1] print(zero[i], one[i]) 아래는 재귀함수를 이용한 풀이이다. def fibo(n): if n == ..
[BOJ] [Python] 1010번 : 다리 놓기 서로 다른 M개에서 N를 순서와 상관없이 고르면 된다. 즉, 조합이다. 다른 방법으로도 풀어봐야겠다. # 조합 def recursion(n): if n == 0 or n == 1: return 1 else: return n * recursion(n - 1) num = int(input()) for _ in range(num): n, m = map(int, input().split()) print(int(recursion(m) / (recursion(m - n) * recursion(n))))
[BOJ] [Python] 1753번 : 최단경로 처음에는 2차원 배열을 이용해서 푸려는 무모한 계획을 세웠다. 이 문제에서 2차원 배열을 이용하려면, 최대 20000 x 20000[400,000,000]이 필요하다. 파이썬은 300,000,000부터 메모리 초과가 난다. 100,000,000에 381MB이다. 이 문제는 메모리가 256MB 제한이라서 300,000,000보다 작아도 메모리 초과이다. 그래서 2차원 배열 대신 heapq를 이용하여 풀었다. heapq를 사용한 이유는 최단 거리에 있는 노드를 선택하기 위함이다. 아래 예시로 설명해보면, 4로 가는 최단 거리에 있는 노드는 3이다. heapq가 없었다면, 2->4부터 계산하고 그다음에 3->4를 계산할 것이다. 그렇게 되면 4는 2번이나 이전보다 짧은 최단 거리를 만들었기 때문에, 4가 순서..

티스토리툴바