몽상실현개발주의

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

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

[BOJ] 1167 / 트리의 지름 / Python 파이썬 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 Tree 의 지름을 구하는 문제이다. 문제를 선형시간안에 풀기위해서는 Tree 의 지름과 구하는 알고리즘에 대한 사전 지식이 필요하였다. Tree 의 지름 : 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로 선형 시간내에 Tree 의 지름을 구하는 Algorithm 트리에서 임의의 정점 xx를 잡..