싸피

[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 - 1868. 파핑파핑 지뢰찾기

문제 해결 1. D4 | BFS 2. 클릭이 가능한 부분('.')을 찾아서 클릭을 할지 말지 결정한다 (1) 주변(8방향)에 지뢰가 한개도 없다면 클릭! (2) 하나라도 있으면 건너 뛴다 3. 클릭을 했다면 그 지점의 주변에 지뢰가 아닌부분을 가지고 BFS탐색을 한다. (1) 주변지점을 기준으로 또 그주변에 지뢰가 없으면 계속 퍼져나가면서 탐색한다 (2) 지뢰가 하나라도 있으면 그 지점은 더 나아가지 못한다. 4. 클릭 했을 때 마다 카운트를 세어주고 5. 나머지 클릭이 안된부분을 찾아서 더해주면 끝 💨 처음에 주변에 지뢰가 하나도 없는 지점을 다 찾아놓고 시작하려 했지만 시간이 오래걸릴 거 같아 찾으면서 가는 방식을 선택했다. 다 풀고보니 그렇게 해도 될거같다. 소스 코드 from _collection..

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

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