분류 전체보기

[python] 백준 - 11048. 이동하기

🤔문제 해결 1. DP | silver1 2. 주어진 2차원 배열보다 한칸씩 더 큰 0으로 채워진 배열을 만든다. (한칸씩 더 많은 이유는 가장 윗줄과 가장 왼쪽줄도 비교해주기 위해서) 3. 현재 지점의 값(maze)과 그 점 이전의 값들(왼쪽, 왼쪽위, 위)중 큰 값(dp)을 더해서 (dp에) 값을 계속 쌓아 준다. 💨 다이나믹프로그래밍 문제. BFS로도 간단히 풀 수 있지만 시간초과가 난다. 💻소스 코드 N, M = map(int, input().split()) maze = [list(map(int, input().split())) for _ in range(N)] # 가장 윗줄과 가장 왼쪽줄도 비교를 해줘야 하기 때문에 한칸씩 더해서 만들어준다. dp = [[0] * (M + 1) for _ in ..

[python] SWEA - 4261. 빠른 휴대전화 키패드

🤔문제 해결 1. D5 | 이게 왜 D5? 2. 키패드 리스트나 딕셔너리를 만든다. 3. 각각의 단어들을 한글자 한글자 체크한다. 4. 단어 안의 한글자가 누른 키패드의 문자 안에 포함되어 있지 않으면 체크를 멈추고 5. 모두 통과하면 카운트를 세어준다. 💨 D5라서 재귀함수를 통해 가능한 모든 단어를 구하고 포함관계를 구해줬는데 틀렸다. 혹시나 해서 단순하게 접근했더니 쉽게 풀렸다. D5가 아닌거 같다... 💻소스 코드 keypad = { '2': ['a', 'b', 'c'], '3': ['d', 'e', 'f'], '4': ['g', 'h', 'i'], '5': ['j', 'k', 'l'], '6': ['m', 'n', 'o'], '7': ['p', 'q', 'r', 's'], '8': ['t', '..

[python] SWEA - 1238. [S/W 문제해결 기본] 10일차 - Contact

🤔문제 해결 1. D4 | BFS 2. 주어진 인풋값으로 인접리스트를 만든다. 3. 똑같은 노드를 탐색하는 것을 막기 위해 방문여부를 확인할 visited 리스트, BFS에서 같은 깊이에서 가장 큰 숫자를 기억해둘 result를 만들고 deque를 이용해 BFS 탐색을 한다. 4. 재귀 함수를 이용해서 BFS의 깊이마다 result의 값을 갱신해준다. 5. 마지막으로 갱신된 result 를 출력 💨 💻소스 코드 from _collections import deque def contact(current_q): global result # 마지막 연락받은 사람들 중 가장 큰 값 result = max(current_q) # 다음 연락 받을 사람들이 들어갈 리스트 next_q = deque() # 현재 연락받..

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