몽상실현개발주의

[BOJ] 2251 / 물통 / Python 파이썬 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 풀이 주어진 조건에 해당하는 모든 경우의수를 완전 탐색으로 찾는 문제이다. 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 첫번째 물통이 비어 있을 때, 세 번째 물통에 담겨있을 수 있는 물의 양을 모두 구하여라. from collections import deque A, B, C = map(int, ..

[BOJ] 1525 / 퍼즐 / Python 파이썬 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 Data 의 저장형태를 고려해야 하는 BFS 완전탐색 문제이다. 3 X 3 퍼즐이 주어지는데, 익숙하게 List 로 진행한다면 Deep Copy 문제와 함께 시간초과를 만나게 된다. 3 X 3 퍼즐의 좌표를 1열로 바꿔주고, List 가 아닌 String 으로 Data 를 저장하여 해결 하였다. 문제를 풀면서 자연스럽게 발생하는 문제를 예측하고, 해결하기 위한 설계로 어려움 없이 해결하여 풀이과정이 매우 만족스러웠다...

[BOJ] 9019 / DSLR / Python 파이썬 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 전형적인 Queue 를 사용한 BFS 문제라고 생각하였다가 시간초과로 꽤나 고생을 하였다. 풀고나니 파이썬으로는 해결이 불가능 하다고 결론을 내었지만 그래도 배울것이 많은 문제였다. List 로 visted 를 만드는 것보다, set 이 더 빠르다. List 에서 in 을 사용하는 탐색은 O(n) -> list 의 index..

[BOJ] 1697 / 숨바꼭질 / python 파이썬 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 최단시간으로 도달하는 문제이기 때문에 BFS 로 풀이 하였다. 처음 시도에는 단순히 모든 경우의수를 탐색하였기 때문에, 메모리 초과가 발생 하였다. 방문했던 위치에 재방문 하는 경우의수를 고려하여 해결하였다. from collections import deque N, K = map(int, input().spl..

[BOJ] 1963 / 소수 경로 / Python 파이썬 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 풀이 [BOJ] 1963 / 숨바꼭질 문제와 유사한 문제였다. BFS 로 완전탐색을 하면서 memoization 으로 중복 탐색하는 경우를 제거하여 풀이하였다. 소수 판단은 "에라토스테네스의 체" 로 미리 만들어 주었고, 새롭게 생성되는 비밀번호는 자리수별로 0~9까지 변경하여 만들어 주었다. from collections import deque #..

[BOJ] 10971 / 외판원 순회2 / Python 파이썬 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 가장 기본적인 형태의 Traveling Salesman problem(TSP) 문제 이다. visited 로 방문한 경로를 check 하며 DFS 탐색하여 해결하였다. # 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. # 가..

[BOJ] 10819 / 차이를 최대로 / Python 파이썬 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 순열을 이용하여, 모든 경우를 만들어 비교하였다. from itertools import permutations N = int(input()) nums = list(map(int, input().split())) res = 0 for per in permutations(range(N), N): tmp = 0 for i in range(1, N)..

[BOJ] 9095 / 1, 2, 3 더하기 / Python 파이썬 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 주어진 숫자를 1, 2, 3 으로 표현하는 경우의 수는 점화식으로 표현 가능하다. dp(1) = 1 dp(2) = 2 dp(3) = 4 dp(4) = dp(1) + dp(2) + dp(3) dp(N) = dp(N-3) + dp(N-2) + dp(N-1) N = int(input()) nums = [0, 1, 2, 4] for _ in range(4, 12): nums.append(sum(nums[-3:])) for _ in..