몽상실현개발주의

[BOJ] 1261 / 알고스팟 / Python 파이썬 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 누적 합이 가장 적은 구간을 찾는 문제이다. 처음에는 deque 를 이용한 bfs 로 구하였는데 시간초과가 발생 하였다. 어느 경우에서든 "누적 합" 이 적은 경우로 진행하여야 하기 때문에, 우선순위 queue 로 해결하여야 효율적으로 해결 할 수 있었다. 이를 위하여 deque 에서 appendleft 로 누적합이..

[BOJ] 5014 / 스타트링크 / Python 파이썬 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 풀이 최단거리 구하기 문제로 BFS를 사용하여 풀었다. 처음의 시도에서는 시간초과가 계속 발생 하였는데, 이것은 queue 에 추가하기 전에 visited check 를 하는것으로 해결하였다. queue 에서 꺼낼때 visited check 를 하는것이 경우의 수가 더 많기 때문이었다. ※ 전혀 고려하지 못하였던 부분이라 새롭게 공부하게 되었다. fro..

[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] 1967 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 전날 풀었던 [BOJ] 1167 / 트리의 지름 / Python 파이썬 문제와 같이 Tree 의 지름을 구하는 문제이다. 다시 복습하자면, Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx..