algorithm

[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..

[python] SWEA - 1249. [S/W 문제해결 응용] 4일차 - 보급로

문제 해결 1. D4 | BFS 2. 각 지점에서 걸리는 시간 리스트(인풋 값)와, 각 지점까지 가는데 걸리는 누적 시간 리스트를 가지고 시작한다. 3. 전에 방문 여부와 상관없이 각 지점에서 상하좌우 4방향을 탐색하며, 현재까지 걸린 시간과 다음칸에서 소모할 시간을 더한 값이 다음 칸까지 걸리는 시간보다 작으면 그 칸으로 이동한다. 4. 모든 가능성을 다 탐색하고 리스트의 마지막지점을 출력한다. 🐱‍💻 원래는 다익스트라 알고리즘으로 힙큐를 사용해서 풀려고 했는데 생각이 안나서 BFS 랑 최솟값 리스트를 활용해서 풀었다. 소스 코드 from _collections import deque for tc in range(1, 1 + int(input())): n = int(input()) maps = [lis..

[python] SWEA - 2819. 격자판의 숫자 이어 붙이기

문제 해결 1. D4 | 재귀를 이용한 DFS 2. 시작점을 하나 선택하고 dfs함수 실행 3. 선택한점에서 4방향 탐색(인덱스 범위 이내) 후 해당 지점의 숫자를 더해가며 dfs재귀함수실행 4. 숫자의 길이가 7이 되면 함수를 종료하고, 결과 리스트에 넣어준다.(여기서는 중복을 피하기위해 set을 사용) 5. 모든 경우의 수를 탐색 후 답을 출력 💨 D4라고 하기엔 조금 쉬운 문제였다. 소스 코드 def dfs(number, x, y): # 길이가 7이 되면 result에 값을 추가하고 break if len(number) == 7: result.add(number) return # 상하좌우 4방향을 탐색 for k in range(4): nx = x + dx[k] ny = y + dy[k] # 리스트..

[python] SWEA - 5550. 나는 개구리로소이다

문제 해결 1. D4 | 카운팅을 조건에 맞게 잘해주는 것 2. 주어진 울음소리를 하나하나 담을 수 있는 배열이나 딕셔너리를 만들고 하나하나 더해준다. 3. 울음소리가 완성됐을 때(croak가 1 이상일 때) 다음에 c가 나온다면 c는 이전 울음소리의 반복이므로 -1 해준다. (🔼🔼🔼이 문제의 핵심 🔼🔼🔼) 4. 문제가 없다면 카운팅된 숫자가 전체 개구리의 숫자이지만 5. 울음소리의 순서가 맞지 않거나, 완성이 불가능한 울음소리라면 -1로 답을 출력해주면 된다. 💨 처음 문제 풀 때 울음소리 하나가 완성되면 이전까지 나와있는 c의 갯수로 카운팅을 했었는데 정답이 아니다 (50개 맞음) 여기서 중요한건 패턴인데 울음소리가 완성되고 다음에 c가 나온다면 (바로 다음이 아니더라도) 그것은 이전 개구리 울음소리..

[python] SWEA - 7465. 창용 마을 무리의 개수 / 10200. 구독자 전쟁

1. 창용 마을 무리의 개수 문제 해결 D4 | DFS, BFS, 그래프 1. 주어진 정보로 인접리스트를 만든다. 2. 보통의 그래프 탐색이라면 시작점하나로 BFS나 DFS 탐색을 하고 끝나지만 여기서는 모든 노드를 탐색해야 하므로 3. BFS탐색을 하는 while문을 for문으로 감싸서 모든 노드를 탐색한다. 4. for문을 통해 큐에 들어가는 노드는 한 무리의 시작점이므로 카운트를 세어준다. 🌦 처음 실패는 while 문 안에 for 문을 넣어 시간초과가 났다는 것이다. 여기서 for 문을 바깥으로 꺼내주고 시간초과는 해결, 두번째 실패는 for문을 N까지 돌려서 났다. N+1로 고쳐서 통과했다. 소스 코드 from _collections import deque for tc in range(1, 1 ..