Algorithm Problem/Python

[python] 프로그래머스 - 문자열 압축(2020 KAKAO BLIND RECRUITMENT)

🤔문제 해결 1. Lv2 2. 리스트를 만들어 문자열을 1개, 2개, ... , n/2개 까지 쪼갰다. 문자열이 abcabcabcabcdededededede 라면 [['a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'a', 'b', 'c', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', 'd', 'e', ''], ['ab', 'ca', 'bc', 'ab', 'ca', 'bc', 'de', 'de', 'de', 'de', 'de', 'de', ''], ['abc', 'abc', 'abc', 'abc', 'ded', 'ede', 'ded', 'ede', ''], ['abca', 'bcab', 'cabc', 'dede', 'dede',..

[python] SWEA - 1389. 케빈 베이컨의 6단계 법칙

🤔문제 해결 1. S1 | 그래프 이론, 그래프 탐색, 너비 우선 탐색, 플로이드-와샬(?) 2. 인접리스트를 만든다! 3. 베이컨수와 그 때의 사람을 저장할 변수 생성 4. 한사람씩 모두 BFS 탐색 5. visited에 저장된 숫를 모두 합치면 베이컨 수가 나온다. 6. 비교를 통해 가장 작은 베이컨수를 가진 사람을 답으로 출력한다. 💨 제목만 보고 어려운 문제인줄 알았는데 BFS를 모두 돌아주면 해결된다. 💻소스 코드 import sys from _collections import deque N, M = map(int, input().split()) # 인접 리스트 생성 adj = {x + 1: [] for x in range(N)} for i in range(M): s, e = map(int, s..

[python] 백준 - 1074. Z

🤔문제 해결 1. 재귀,분할정복 | S1 2. 모두 쪼개려고 하는경우 메모리초과 혹은 시간초과가 발생한다. 3. 내가 찾고자하는 행과 열이 포함된 박스만 찾아서 재귀함수를 실행시킨다. 4. 여기서 각 박스의 첫 숫자를 구한다. (1) 예를 들어 사이즈가 8인 박스의 첫숫자는 0이다. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 박스를 쪼개면 (2) 각 박스의 첫 숫자는 0, 16, 32, 46 이다. (3) 왼쪽 위 박스는 그대로, 오른쪽 위 박스는 첫숫자에 (size//2)**2*1 값을 더해준다. (4) 왼쪽 아래 박스는 첫숫자에 (size//2)**2*2 값을, 오른쪽 아래 박스는 첫숫자에 (size//2)**2*3 값을 더해준다. 5. 박스의 크기가 2가 되면 찾고자 하는 행과 열을 찾..

[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() # 현재 연락받..