우주에서 글을 적어본다

[오늘의 학습 키워드 및 문제]- 프로그래머스의 "멀리 뛰기" 문제를 풀었다.- 오늘도 DP(다이나믹 프로그래밍) 문제인데 조건이 어제와 하나 달랐다.[나의 코드]def solution(n): d = [0] * (n + 1) d[1] = 1 if n > 1: d[2] = 2 for i in range(3, n + 1): d[i] = d[i - 1] + d[i - 2] return d[n] % 1234567어제의 문제와 달리 점화식을 직접 찾아야 했다.근데 이 정도 문제는 점화식을 쉽게 구할 수 있고, 무려 어제 피보나치 문제와 같다.d[1] = 1 → 경우의 수가 하나밖에 없다.d[2] = 2 → 얘는 두 개뿐이다.d[3], d[4..

[오늘의 학습 키워드 및 문제]- 프로그래머스의 "피보나치 수" 문제를 풀었다.- 이 문제는 본래 재귀 함수로도 DP로도 풀 수 있다. 근데 오늘 주제가 DP이므로 DP로 풀었다.- DP는 그리디의 한 종류로 안 그래도 어렵고 싫은데, 코테에 자주 나오는 듯하여 슬프다...[나의 코드]def solution(n): d = [0] * (n + 1) d[1] = 1 d[2] = 1 for i in range(3, n + 1): d[i] = d[i - 2] + d[i - 1] return d[n] % 1234567코드를 이해하기 위해서는 메모이제이션 기법을 알아야 한다.메모이제이션 기법은 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모..

[오늘의 학습 키워드 및 문제]- 프로그래머스의 "큰 수 만들기" 문제를 풀었다. - 오늘도 어김없이 그리디(Greedy)다. - (아리아나 그란데 노래 중에 그리디라는 노래 좋은데) [나의 코드]def solution(number, k): answer = [] for num in number: while k > 0 and answer and answer[-1] 나의 생각 과정은 다음과 같다. ① k개만 빼면 되니까 k를 while문의 종료 조건으로 둬야겠다. ② 순서.. 숫자의 순서가 안 바뀌니까 스택 또는 큐로 구현해 봐야겠다, ③ 뭐가 더 필요한데 그걸 모르겠다. 근데 그리디 문제다 보니까 어떻게 하면 되겠다 이게 보인다. 손으로 그려가며 하면 되는데 올리기 귀찮으므로..

[오늘의 학습 키워드 및 문제]- 프로그래머스의 "구명보트" 문제를 풀었다.- 주제는 그리디(Greedy)이고, 내가 잘 못하는 알고뤼듬이다.[나의 코드]def solution(people, limit): answer = 0 people.sort() start = 0 end = len(people) - 1 while start 처음에는 아무 생각 없이 for문으로 풀었다. 정렬해서 가벼운 것부터 더해서 확인했다.그런데 점점 이상함을 느꼈다. '안 되는데?'를 느낀 순간 바로 반례를 찾아보았다.예를 들어 [40, 50, 50, 60]와 같은 배열을 생각해 보면, 작은 거부터 확인하면 답이 3이 나온다.근데 답은 2가 나와야 한다. (40, 60), (50, 50) ..

[오늘의 학습 키워드 및 문제]- 백준의 "단지번호붙이기" 문제를 풀었다.- 오늘 주제는 DFS/BFS로 까다로운 문제는 아니었다.[나의 코드]# BFS 풀이from collections import dequen = int(input())graph = [list(map(int, input())) for _ in range(n)]dx = [-1, 0, 1, 0]dy = [0, 1, 0, -1]def bfs(x, y): q = deque() q.append((x, y)) graph[x][y] = 0 count = 1 while q: x, y, = q.popleft() for i in range(4): nx = x +..

[오늘의 학습 키워드 및 문제]- 백준의 "촌수계산" 문제를 풀었다.- 너비 우선 탐색과 깊이 우선 탐색 두 방식으로 모두 풀어볼 수 있다.[나의 코드]# DFS 풀이n = int(input())a, b = map(int, input().split())m = int(input())graph = [[] for _ in range(n + 1)]visited = [0] * (n + 1)result = []for _ in range(m): x, y = map(int, input().split()) graph[x].append(y) graph[y].append(x) def dfs(v, count): count += 1 visited[v] = True if v == b:..

[오늘의 학습 키워드 및 문제]- 프로그래머스의 "모음사전" 문제를 풀었다.- 오늘 주제는 완전 탐색이다.- 조건에 맞는 모든 조합을 생각하려고 하니 라이브러리를 쓸 수도 있지만 재귀함수로 구현했다.[나의 코드]def solution(word): vowels = ['A', 'E', 'I', 'O', 'U'] vowel_dict = {} idx = 1 def find(current, length): nonlocal idx if length > 5: return if current: vowel_dict[current] = idx idx += 1 ..

[오늘의 학습 키워드 및 문제]- 리트코드의 "Prefix and Suffix Search" 문제를 풀었다.- 완전 탐색이 주제인데 조건만 아니었으면 완전 탐색으로 안 풀어도 된다.- 입력이 [[["apple"]],["a","e"]] 이면, apple 쪽이 단어고, a/ e 쪽이 접두사, 접미사이다. 접두사, 접미사의 길이가 서로 다를 수 있다는 건지 잘 모르겠는데 난 다를 수도 있다고 생각하고 풀었다.[나의 코드]# 1차 시도class WordFilter: def __init__(self, words: List[str]): self.words = words def f(self, pref: str, suff: str) -> int: idx = -1 for ..

[오늘의 학습 키워드 및 문제]- 백준의 "숫자 카드 2" 문제를 풀었다.- 어제와 비슷한 같은 입력의 비슷한 문제였다.- 오늘도 여러 가지 풀이 방법으로 풀어봤다.[나의 코드]# 첫 번째 풀이n = int(input())given = list(map(int, input().split()))m = int(input())holded = list(map(int, input().split()))result = {}for num in given: if num not in result: result[num] = 1 else: result[num] += 1for num in holded: if num in result: print(result[num], end=..

[오늘의 학습 키워드 및 문제]- 백준의 "숫자 카드" 문제를 풀었다.- 오늘 주제는 "이분 탐색"이다.- 근데 오늘 문제는 세 가지 방법으로 풀어봤다. 더 있을지 모르겠는데 암튼 세 개다.[나의 코드]# 첫 번째 풀이n = int(input())given = set(list(map(int, input().split())))m = int(input())holded = list(map(int, input().split()))for num in holded: if num in given: print(1, end=" ") else: print(0, end=" ")다음 코드는 집합(Set)을 이용하여 푼 풀이다.아마 이 코드가 가장 직관적이고 바로 떠올릴 수 있는 코드일 것이..