링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 큐를 이용한 BFS 재귀를 이용한 DFS 방문처리 배열 하나로 두 번 사 구현(틀림) import sys from collections import deque #dfs def dfs(v): dfs_li.append(v) for i in range(n): if m_li[i][0] == v and not check[m_li[i][1]]: check..
링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여www.acmicpc.net아이디어바로 보자마자 bfs로도 풀 수 있을 것 같음근데 dfs를 연습하기 위해 dfs를 사용2중 for문을 통해 방문처리를 확인하고 dfs진행dfs는 재귀를 사용각 영역마다 each변수로 크기 표현구현import sys input = sys.stdin.readline n = int(input()) danzi = [list(map(int, input().strip())) for _ in range..
링크: https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 아이디어 배열이 그렇게 크지 않아 적록색약인 경우와 아닌 경우 두 번 bfs를 해도 될 것 같음 방문처리 배열도 만들어서 bfs 진행해보자 첫 bfs함수는 색깔을 인자로 같이 넣어주어 같은 색상끼리 묶어주기 두 번째 bfs함수는 R,G를 같은 색상으로 인식하게 해주면 될듯 (조건문) 두번째 함수 돌릴 때는 방문처리 배열을 재활용하자 1이 방문이 되지 않은 것으로 인지 코드 impor..
링크: https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 아이디어 dp 배열 2개를 만들어 각 지점에서 우측 좌측 '가장 긴 증가하는 수열' 문제에서 사용한 점화식을 적용 두 dp배열을 모두 만들어준 후 합쳐주어 바이토닉 부분 수열의 길이를 구함 구현 import sys input = sys.stdin.readline n = int(input()) s = list(map(int, input().split())) dp_left = [1]*n dp_right = [1]..
링크: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 아이디어 가로 새로 크기만큼 배열 생성 입력된 좌표를 1로 변경 이중 for문을 돌며 1인 좌표에서 bfs 탐색 진행 탐색을 마친 좌표는 0으로 변경 from collections import deque import sys input = sys.stdin.readline dx = [0,0,1,-1] dy = [1,-1,0,0] t = int(input()) def bfs(graph, a, b): que..
링크: https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 아이디어 첫째날 둘째날을 a, b로 두고 D와 K를 가지고 점화식을 만들어 보자 예) D가 4면 a, b, a+b, a+2b, 2a+3b, 3a+5b=> K=a+2b DP배열을 2차원배열로 만들어 a에 곱해지는 값과 b의 곱해지는 값을 저장함 구현 D, K = map(int, input().split()) d = [0] * 31 d[1] = (1,0) # 첫째날 1a + b d[2..
링크: https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 아이디어1 (시간초과) 일단 단순하게 b번 반복하며 a 곱하기 파이썬은 자동으로 동적할당이 되어 너무 큰 수가 나오면 메모리초과가 나올 수 있음 a를 곱하고 c로 바로바로 나눠주며 메모리초과 방지 import sys input= sys.stdin.readline a, b, c = map(int, input().split()) for i in range(b): a *= a a %= c print(a) 단순히 반복하는 로직은 답이 아닌듯 하다. 아이디어 2 ..
링크: https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 아이디어 익은 토마토(1)의 좌표들를 q에 넣고 bfs 숨바꼭질과 동일하게 방문처리와 깊이 저장을 동시에 진행 (이건 토마토 배열 안에서 해도 될듯) 상하좌우 확인 0이면 1로 변경 후 큐에 넣기, 1이면 무시, -1이어도 무시 모든 토마토가 익었는지와 며칠이 걸렸는지는 배열을 돌며 확인 0인 부분이 있으면 -1출력 자료구조 토마토: int[][] Queue(BFS) 코드구..
링크: https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 아이디어 수빈이의 시작점을 시작으로 bfs x-1, x+1, 2*x 이 3가지 방향으로 이어지는 그래프로 생각 방문했던 수는 방문처리를 해주어 탐색하지 않기 몇번째 층인지 확인은 방문 처리와 동시에 이루어짐 전 요소의 방문 인덱스에 +1한 값을 현재 요소의 방문 인덱스에 저장 동생의 위치에 도착하는 경우가 발생하면 그 요소의 층을 따로 저장 다음 층 탐..
