note

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net from collections import deque MAX = 100000 n, k = map(int, input().split()) queue = deque() queue.append(n) visited = [0] * (MAX + 1) while queue: q = queue.popleft() mv = [q + 1, q - 1, 2 * q] if q == k: pri..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 7576번 문제의 3차원 버전이다 3차원이라는 것만 신경 써주고 똑같이 풀면 된다 pypy3로 제출함 from collections import deque m, n, h = map(int, input().split()) tomato = [[] for _ in range(h)] for i in range(h): for j in range(n): data = list(map(i..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 미로 찾기랑 비슷한 문제다 처음엔 BFS를 동시에 돌려야 하나.....? 하고 혼자 엄청 고민했는데 그냥 큐에 있는 걸 전부 돌리기만 해도 된다는 걸 깨달음 맨 마지막 좌표에서 끝나는 것이 아니기 때문에 결과값은 최대값! 처음 시작을 1로 하기 때문에 결과값은 -1 해주기! from collections import deque m, n = map(int, input().split(..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이코테 교재에 있던 문제이기도 하고 어느 정도 그래프 탐색 문제에 익숙해져서 빠르게 풀었다 역시 사람은 복습이 중요하고 꾸준히 공부해야 한다,,, 이 문제 처음 풀었을 땐 답이 도무지 안 나왔는데 다시 푸니까 쉽게 풀림 from collections import deque n, m = map(int, input().split()) miro = [[] for _ in range(n)] for i in range(n): data =..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net pypy3로 제출함. 드디어 dfs와 bfs가 익숙해졌따......! # dfs def dfs(x, y): if x = m or y = n: return False if list[y][x] == 1: list[y][x] = 0 dfs(x+1, y) dfs(x-1, y) dfs(x, y+1) dfs(x, y-1) return True else: return False t = ..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 리스트 돌면서 해당 데이터가 1이면 상하좌우 살피면서 그래프를 탐색한다. 코드가 매우 너저분한 느낌,,, # dfs n = int(input()) list = [[] for _ in range(n)] for i in range(n): data = input() for j in range(n): list[i].append(int(data[j])) def dfs(x, y): if x ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net bfs 먼저 풀고 dfs 풀었다 # bfs from collections import deque n = int(input()) m = int(input()) com = [[] for _ in range(n+1)] for i in range(m): data = input().split() com[int(data[0])].append(int(data[1])) com[int(data[1])].append(i..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net from collections import deque n, m, v = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): data = input().split() graph[int(data[0])].append(int(data[1])) graph[int(data[1])]...

스택 (LIFO) stack = [] stack.append(5) stack.append(2) stack.append(3) stack.append(7) stack.pop() stack.append(1) stack.append(4) stack.pop() print(stack) # 최하단 원소부터 출력 print(stack[::-1]) # 최상단 원소부터 출력 - 별도의 라이브러리 없이 리스트의 append(), pop() 메서드 이용 큐 (FIFO) from collections import deque # 큐 구현을 위해 deque 라이브러리 사용 queue = deque() queue.append(5) queue.append(2) queue.append(3) queue.append(7) queue.pop..

구현 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정' -> 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념 -> 프로그래밍 문법 숙지, 라이브러리 사용 경험을 늘려야 함. · 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 · 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 메모리 제약 사항 - C/C++에서 변수의 표현 범위 (int 4바이트, long 8바이트 -> 파이썬 X, 자바 BigInteger, C++ 외부 라이브러리 필요) - 파이썬에서 리스트 크기 (데이터의 개수 1000 -> 메모리 4KB / 백만 -> 4MB / 천만 -> 40MB) 채점 환경 - 파이썬은 C/C++에 비해 동작 속도 느림. 1초에 2,000만 번의 연산을 수행한다고 가정하..