몽상실현개발주의

[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] 3108 / 로고 / Python 파이썬 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 풀이 인접한 사각형끼리의 구분을 짓는것과 는 시간초과를 해결해야 하는 그래프 문제이다. 인접한 사각형의 경우는 경로가 이어져 있지 않지만 사각형 두개가 매우 인접해 있다면, 같은 그래프 경로로 판단되었다. 이를 해결하기 위해 주어진 모든 좌표를 -500~500 에서 0~2000 으로 만들어 주어 해결하였다. 시간초과를 해결하는 것에서 꽤나 애를 먹었는데, 모..

[BOJ] 2186 / 문자판 / Python 파이썬 https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 www.acmicpc.net 풀이 주어진 조건을 만족하는 모든 경로의 개수를 구하는 문제이다. 모든 경로는 DFS 를 이용하여 구현하였지만, 시간초과에 부딪히고 말았다. 모든 경로에 대한 완전탐색의 최적화는, 각 진행상황에 대해 memorization 을 해주며 중복하여 탐색하는 경우를 제거해 주어야 하였다. 그래서 visited를 2..

[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 #..