효과는 굉장했다!

2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys # 굳이 모든 구역을 예시처럼 1구역, 2구역 ,3구역으로 만들 필요는 없다. # 생각의 전환 -> 그냥 0으로 만들어주면서 아파트 개수만 세주면 된다. # 총 단지수는 answer의 길이 def house_map(x,y): global cnt house[x][y] = '0' # 들어온 house[x][y] == 1 이므로 0 으로 만들어주면서 바로 cnt ..

2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def maze_serach(x,y): dx = [1,-1,0,0] dy = [0,0,-1,1] queue = deque([[0,0]]) # 시작점 while queue: # queue가 빌 때까지 x, y = queue.popleft() # 현재 위치에서 4가지 방향으로 위치 확인 for i in range(4): nx = x + dx[i] ny =..

1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 알고리즘 분류 자료 구조 우선순위 큐 SOLUTION import sys import heapq N = int(sys.stdin.readline()) heap = [] for _ in range(N): x = int(sys.stdin.readline()) if x > 0 : heapq.heappush(heap, x) elif x == 0: if heap == []: print(0) else: print(heap[0]) heapq.heappop..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 SOLUTION import sys from collections import deque def bfs(): queue = deque([N]) while queue: now = queue.popleft() # 왼쪽에서 뺴는 이유 작은 수 부터 차례대로 조사 해야함 if now == K: print(location[now]) break for value in (now-1, now+1..

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 플로이드-와샬 SOLUTION import sys from collections import deque def bfs(realationship, start_node): num = [0] * (N+1) # 각각 노드가 몇번의 케빈 베이컨 수인지 측정을 위해 구현 queue = deque([start_node]) # deque를 이용해 시간복잡도 줄임, q.pop..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 알고리즘 분류 분할 정복 재귀 SOLUTION import sys N, r, c = map(int, sys.stdin.readline().split()) # r = 행, c = 열 result = 0 while True: if N = middle: if c >= middle: # 오른쪽 아래 구역 result += ((N-..

Softeer 제한시간: C/C++(1초), Java/Python/JS(2초) | 메모리 제한: 256MB 수퍼바이러스가 숙주의 몸속에서 0.1초당 P배씩 증가한다. 처음에 수퍼바이러스 K마리가 있었다면 N초 후에는 총 몇 마리의 수퍼바이러스 softeer.ai SOLUTION import sys K, P, N = map(int, sys.stdin.readline().split()) # pow() 계산시 mod값 설정을 하여 시간단축을 시킨 후 K를 곱한 값이 1e9+7 을 넘어갈 수 있기 때문에 한번더 1e9+7로 나눈 나머지 값을 구한다 # 0.1초당 P배씩 증가하므로 N*10을 해준다 print(K*pow(P, N*10, int(1e9+7)) % int(1e9+7)) ※ Softeer 바이러스 문제..

Softeer 제한시간 : C/C++/Java/Python/JS(1초) | 메모리 제한 : 256MB GINI는 현대자동차그룹에서 개발한 네비게이션이다. GINI는 너무나도 뛰어나 목적지에 도착하는 시간을 예측할 수 있다. 어느 날 태범이는 세 softeer.ai SOLUTION import sys from collections import deque def shower(): # 소나기 이동 global rain tmp = [] for x, y in rain: for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

Softeer 제한시간 : C/C++(1초), Java/Python/JS(2초) | 메모리 제한 : 256MB 남북으로 흐르는 개울에 동서로 징검다리가 놓여져 있다. 이 징검다리의 돌은 들쑥날쑥하여 높이가 모두 다르다. 철수는 개울의 서쪽에 softeer.ai SOLUTION import sys N = int(sys.stdin.readline()) stone_height = list(map(int, sys.stdin.readline().split())) # Dynamic Programming 이용 dp = [1] * N for i in range(1,N): for j in range(i): if stone_height[i] > stone_height[j]: # 현재보다 높은 돌을 밟아야 하므로 dp[i]..

11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 SOLUTION import sys from collections import deque def bfs(node): queue = deque([node]) while queue: node = queue.popleft() for i in graph[node]: if visit_list[i] == 0: queue.append(i) vi..