코딩하는 오리

[문제] 모든 부분 집합을 리턴하라 · 입출력 예 num_list return [1, 2, 3] [[3], [1], [2], [1, 2, 3], [1, 3], [2, 3], [1, 2], []] [풀이] 입력값으로 트리를 구성하고, 트리를 DFS하는 문제로 풀이할 수 있다. 경로 (path)를 만들어 나가면서, 인덱스를 1씩 증가하는 형태로 깊이 우선 탐색을 진행하였다. 별도의 종료 조건이 없기 때문에, 탐색이 끝나면 저절로 함수가 종료된다. 입력받은 숫자 배열로 만들 수 있는 모든 부분 집합들이 정답이기 떄문에, dfs를 진행할 때마다 결과 배열에 값을 추가하고, 이를 반환하는 형태로 문제를 풀었다.

[문제] 중복 문자가 없는 가장 긴 부분 문자열의 길이를 리턴하라 · 입출력 예 string return "abcabcbb" 3 (abc) "bbbbb" 1 (b) "pwwkew" 3 (wke) [풀이] 1. 슬라이딩 윈도우와 투 포인터 사이즈 조절 def lengthOfLongestSubstring(s: str) -> int: used = {} max_length = start = 0 for index, char in enumerate(s): if char in used and start

[문제] 자연수 N이 주어진다. N을 이진수로 바꿔서 출력하는 프로그램을 작성하시오. · 제한사항 1. 자연수 N은 1이상, 100,000,000,000,000이하이다. 2. N을 이진수로 바꿔서 출력하며, 이진수는 0으로 시작하면 안된다. · 입출력 예 N return 53 110101 [풀이] 1. Me n = int(input()) def binary(num: int) -> str: print(bin(num)[2:]) binary(n) bin 메소드를 사용하여 입력받은 수를 이진수로 변환하고, 이진수로 변환할 경우 앞에 '0b'가 붙기 때문에 리스트 슬라이싱을 이용하여 '0b'를 제거하였다. 이 문제 출제의 요점인 재귀함수 호출을 통해 다른 방법으로 풀어볼 수 있을 것 같다.

[문제] 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. · 제한사항 1. 정수 N은 0보다 크거나 같고 12보다 작거나 같다. · 입출력 예 N return 10 3628800 0 1 [풀이] 1. Me n = int(input()) def factorial(n: int) -> int: if n == 1: return 1 elif n == 0: return 1 else: return n * factorial(n-1) print(factorial(n)) 일반적인 팩토리얼 풀이법을 사용하여 문제를 풀었다. 재귀함수 호출을 통해 팩토리얼을 계산하고, n이 1 또는 0일 경우 1을 반환한다.

[문제] 2에서 9까지 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라 · 입출력 예 digits return "23" ["ad", "ae", "af", "bd", "bf", "bf", "cd", "ce", "cf"] [풀이] 1. 모든 조합 탐색 -> 가능한 경우를 모두 조합하는 형태로 전체를 탐색한 후 백트래킹하면서 결과를 조합할 수 있다. 입력값 digits를 자릿수로 쪼개어 반복하고, 숫자에 해당하는 모든 문자열을 반복하며 문자 단위로 재귀 탐색을 진행한다. 문자를 조합해 만들 수 있는 길이는 입력값의 길이와 동일하므로, 해당 조건을 재귀함수의 종료 조건으로 설정하고, 조건에 맞지 않을 경우 dfs를 반복 수행한다.

[문제] 1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하라. (연결되어 있는 1의 덩어리 개수를 구하라) · 입출력 예 grid map return 11110 11010 11000 00000 1 11000 11000 00100 00011 3 [풀이] 1. DFS로 그래프 탐색 이와 같이 작성하였을 경우, grid를 dfs 함수 호출시마다 넘겨주어야 하고, 함수 호출 시 매번 self.가 따라 붙는다. 2. DFS로 그래프 탐색 (중첩함수 사용) DFS 탐색을 하는 dfs 함수는 동서남북을 모두 탐색하며 재귀호출한다. 이동하고자 하는 곳이 육지가 아닌 경우에 return 하도록 설정해 줌으로써 연결되어 있는 섬을 구할 수 있다. 이 함수에서 이미 방문했던 곳(grid[i..

[문제] 매일의 화씨 온도(˚F) 리스트 T를 입력받아, 더 따뜻한 날씨를 위해서는 며칠을 더 기다려야 하는지를 출력하라 · 입출력 예 T [73, 74, 75, 71, 69, 72, 76, 73] return [1, 1, 4, 2, 1, 1, 0, 0] [풀이] 1. 스택 값 비교 -> 현재의 인덱스를 계속 스택에 쌓아두다가, 이전보다 상승하는 지점에서 현재 온도와 스택에 쌓아둔 인덱스 지점의 온도 차이를 비교 하여, 더 높다면 스택의 값을 pop()으로 꺼내고, 현재 인덱스와 스택에 쌓아둔 인덱스의 차이를 정답으로 처리한다. def dailyTemperatures(T: list[int]) -> list[int]: answer = [0] * len(T) stack = [] for i, cur in en..