Algorithm Problem/Python

[python] SWEA - 1219. [S/W 문제해결 기본] 4일차 - 길찾기

🤔문제 해결 1. D4 | DFS 스택 2. 인접리스트를 만든다. 3. DFS 탐색을 한다. 4. 끝점을 만나면 answer = 1 아니면 그대로 answer = 0 을 출력한다. 💨 DFS 기본 문제 💻소스 코드 for _ in range(1, 11): tc, n = map(int, input().split()) # 인접 리스트를 만든다. # {1:[2,3], 2:[4,8]} # 1에서 2와 3으로 갈 수 있고, 2에서 4와 8로 갈 수 있다는 의미 adj_list = list(map(int, input().split())) adj = {x:[] for x in range(100)} for i in range(0, n*2, 2): s = adj_list[i] e = adj_list[i+1] adj[s]..

[python] SWEA - 1861. 정사각형 방

🤔문제 해결 1. D4 | DFS 2. 선택한 숫자와 +1, -1로 연결될 수 있는 구간을 찾는 방법을 사용 3. 처음 숫자를 선택하고 그 숫자보다 값이 1이 큰 숫자를 계속 찾는다 4. 그 숫자보다 값이 1이 작은 숫자도 계속 찾는다. 5. 찾은 작은 숫자 ~ 큰 숫자의 범위가 하나의 구간이 된다. 6. 값을 다른 숫자(ex. -10)으로 바꿔줘서 하나의 구간을 여러번 탐색하지 않게 한다. 7. 모든 구간들을 구하고 구간의 길이가 가장 긴 구간을 선택. 구간이 여러개라면 시작점이 가장 작은 숫자를 선택한다. (cnt_list는 시작점을 인덱스로 하고 값을 구간의 길이로 하는 리스트이다) 💨 하나하나 모든 숫자를 탐색해도 되지만 효율이 좋지 않을 것 같다. 💻소스 코드 dx, dy = [-1, 1, 0,..

[python] SWEA - 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기

🤔문제 해결 1. 💨 💻소스 코드 from itertools import chain # 답을 출력하기 위한 라이브러리 chain # 이중 리스트를 단일리스트로 바꿔준다. def findSqure(sx, sy): i, j = sx, sy # 아래로 쭉 내려가서 찾고 while i < n and maps[i][j]: i += 1 else: i -= 1 # 오른쪽으로 가서 찾고 while j < n and maps[i][j]: j += 1 else: j -= 1 # 행렬의 끝값을 찾았으면 그 행렬의 값을 전부 0으로 만들어준다. changeZero(sx, i+1, sy, j+1) result.append([i-sx+1,j-sy+1]) def changeZero(a,b,c,d): # 행 a - b, 열 c - ..

[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로

🤔문제 해결 1. D4 | MST - prim 2. 간선의 가중치를 값으로 하는 인접 행렬을 만든다 3. 최소 값을 갱신해줄 가중치 리스트, MST에 포함되지 체크하는 리스트, 부모노드 선택리스트를 만든다. (여기서는 모든 노드가 연결될 수 있기 때문에 부모노드는 필요하지 않을 수 있음) 4. 시작점을 선택(여기서는 0)하고 간선을 돌며 탐색한다 (1) 아직 MST에 포함되어 있지 않고, 가중치가 최소인 정점 u를 찾는다. (2) u를 MST에 포함시키고, 그 가중치를 결과값에 더해준다. (3) 가중치를 최솟값으로 갱신하기 위해 u에 인접하고 아직 mst가 아닌 정점(w) 중에서 key[w] > u-w 이면 갱신한다 5. 모든 노드를 선택할 때까지 4번을 반복한다. 💨 최소신장트리 알고리즘, 크루스칼과 ..

[python] SWEA - 1218. [S/W 문제해결 기본] 4일차 - 괄호 짝짓기

🤔문제 해결 1. D4 | 스택? 2. 괄호를 처음부터 하나씩 검사한다. 3. 왼쪽 괄호일 경우 스택에 넣는다. 4. 오른쪽 괄호일 경우 스택의 마지막에 있는 괄호와 비교하여 짝이 맞는지 검사한다. 5. 짝이 맞으면 통과 6. 아니라면 이 괄호들은 맞지 않는 괄호이다. 종료 💨 가볍게 스택을 연습하는 문제 💻소스 코드 def isRight(parenthesis): stack = [] for paren in parenthesis: # 왼쪽 괄호 if paren in parenthesis_list[0]: stack.append(paren) # 오른쪽 괄호 else: if stack: k = stack[-1] for i in range(4): # 괄호 네가지중 짝이 맞다면 통과 if k == parenthes..

[python] SWEA - 1226. [S/W 문제해결 기본] 7일차 - 미로1

🤔문제 해결 1. D4 | DFS 2. 시작점을 찾는다. 3. 스택을 활용하고 상하좌우 4방향 탐색(인덱스 범위 이내)을 한다. (1) 길('0')을 만날 경우 스택에 추가하고, 나중에 다시 탐색하는 것을 방지하기 위해 그 지점의 값을 바꿔준다. (2) 끝('3')을 만날 경우 미로가 가능하다는 의미 이므로 답을 1로 하고 탐색을 종료한다. 💨 DFS 기본문제이다. 💻소스 코드 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] for _ in range(10): answer = 0 n = int(input()) maps = [list(input()) for _ in range(16)] # 출발점 찾기 x, y = 0, 0 for i in range(16): for j in range(1..