몽상실현개발주의

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 1181 / 부분수열의 합 문제의 심화 문제이다. 부분수열의 합 문제의 경우에는 주어진 수열의 길이가 최대 20개 이므로 Combinations 과 DFS 로 모든 경우의 수를 구하여서 해결 하였다. 하지만 부분수열의 합 2 문제에서는 수열의 길이가 최대 40이기 때문에, 모든 경우가 2**40 개로 어마어마한 시간이 걸리게 된다. 이를 극복하기 위하여..

[BOJ] 1182 / 부분수열의 합 / Python 파이썬 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 풀이 주어진 수열의 부분 수열의 합을 구하는 문제인데, 조합과 DFS 로 풀어보았다. # 조합 from itertools import combinations N, S = map(int, input().split()) nums = list(map(int, input().split())) res = 0 f..

[BOJ] 1987 / 알파벳 / Python 파이썬 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 풀이 시간 조건이 굉장히 빠듯하다고 느꼇던 백트레킹 문제였다. 최장거리 경로탐색과 비슷하지만, 알파벳을 기록하는 부분에서 시간초과가 발생하였다. 다른분들의 풀이를 참고하니, dequeue 가 아닌 set 을 이용한 bfs 로 동작시간을 단축 하던가, 알파벳을 숫자로 변화하여 visited 로 처리하였는데 후자의 경우로 풀어보았다. imp..

[BOJ] 2580 / 스도쿠 / Python 파이썬 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 DFS 를 사용하는 백트래킹 문제이다. 여전히 습관적으로 모든 경로를 탐색하려고 시도하다 로컬에서도 time err 를 만나게 되었다. 고려해야 하는 경우만 탐색하도록 하자! ※Python 으로는 시간초과로 풀지 못하고, Pypy3 로 제출하여야 한다. maps = [] for _ in range(9): maps.append(list(ma..

[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] 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] 1991 / 트리 순회 / Python 파이썬 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 트리 순회의 기본 문제이다. 전위 순회(pre-order): Root -> Left -> Right 중위 순회(in-order): Left -> Root -> Right 후위 순회(post-order): Left -> Right -> Root N = int(input()) tree = {} for _ in range(N): nod..