문제 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 [1,1]도 가능하므로 vis 배열이 필요없는 문제이다! 코드 import sys read = sys.stdin.readline n,m = list(map(int,read().split())) vis = [0 for _ in range(n+1)] arr = [0 for _ in range(m)] def choose(k): if(k==m): print(" ".join(map(str,ar..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 N과M(1)에서 [1,2], [2,1]과 같은 경우는 중복되는 경우로 보고 [1,2]만 출력하는 문제이다. start번호를 줘서 배열에 저장할 수에 제한을 주면 된다. 코드 import sys read = sys.stdin.readline n,m = list(map(int,read().split())) #1~n까지 자연수 중 중복없이 m개를 고르는 수열 #고른 수열은 오름차순 vis=..

문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 백트래킹 연습 문제 출력할 때 print(' '.join(map(str, arr))) 을 사용할 수도 있는 듯 하다. 해당 코드는 아래에 ver2로 첨부하였다. 코드 import sys read = sys.stdin.readline n,m = list(map(int,read().split())) #1~n까지 자연수 중 중복없이 m개를 고르는 수열 vis=[0 for _ in range..

문제 https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 풀이 코드에 주석으로 다 써놨다.. 문제에 약간 논란이 있는 듯 한데, 문제 이해가 관건이다. 파이썬은 위대하다.. rotate랑 count를 처음 써봐서 신세계였던 문제 코드 import sys from collections import deque read = sys.stdin.readline n, k = map(int, input().split()) belt = de..

문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 풀이 기본 BFS 문제이다. 상하좌우가 아닌, 나이트가 이동할 수 있는 좌표를 탐색한다. dx,dy만 잘 설정해주면 된다. 거리를 계산해서 배열에 저장하고, 목적지에 저장된 거리를 출력하면 된다. 코드 import sys from collections import deque read = sys.stdin.readline T = int(read()) dx = [2,1,-1,-2,-2,-1,1,2..

문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 풀이 완전탐색을 활용하여 풀었다. 완전탐색이 가능한 이유는, N이 최대 10000이고, 10000번째 종말의 숫자는 6,669,999보다 작다. 따라서 100,000,000보다 작으므로 루프문으로 해결이 가능하다. 총 연산 수가 약 1억회 이하인 경우, 완전 탐색으로 접근할 수 있다! 코드 import sys read = sys.stdin.readline n = int(read()) cnt..

문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 이 문제도 BFS의 기본 문제. 아무래도 C++과 자바로 풀었던 문제라 쉽다고 생각했는데 vis를 Boolean으로 선언해놓고 0이냐 아니냐로 비교했더니 오류나서 한참 고생... BFS를 함수로 선언한 코드가 많던데, 난 중복이 없길래 그냥 ... 풀어서 썼다. 이중 for문을 통해서 BFS 탐색을 시작할 위치를 고르고, 그림의 수를 카운팅해준다. 그리고 면적은 큐에 들어온 좌표 수 만큼 카..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 예를 들어 101010이 입력됐다면, C++이라면 String으로 입력받아서 하나씩 저장했다면, 파이썬에서는 아래와 같이 for _ in range(n): graph.append(list(map(int,read().rstrip()))) 이 코드를 쓴다. rstrip쓰는 이유는 readline 방식이 \n도 같이 입력받기 때문에 이를 지우기 위함이다. 더 쉽게 입력 받는 방법은 n,m = map(int,input().s..

문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 처음에는 BFS로 풀었는데 틀렸습니다.가 나왔다. 구글링을 통해 왜 BFS가 아닌 DFS로 풀어야하는지에 대해 찾아보았다. BFS를 사용하지 못하는 이유는 처음 지점부터 끝 지점까지 연결한 파이프는 한 줄이다. 따라서 오른쪽 위, 오른쪽, 오른쪽 아래 세 지점을 탐색해야하는데 만약 오른쪽 위 지점을 연결해서 쭉 이어가다 파이프 연결했으면 다시 돌아와서는 오른쪽과 오른쪽 아래 지점을 탐색할 수 없고 모든..

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드의 연습 문제 UNION 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 private static void union(int a, int b) { //union 연산: 대표 노드까지 연결하기 a = find(a); b = find(b); if(a!=b) { parent[b] = a; } } FIND 두 노드가 같은..