본문 바로가기

🧩 Algorithm17

다이나믹 프로그래밍 (Dynamic Programming) Goal 1. 다이나믹 프로그래밍 이해하기 2. Top-down과 bottom-up 방법 알아보기 다이나믹 프로그래밍(Dynamic Programing)이란? 다이나믹 프로그래밍이란 어떤 문제가 주어졌을 때 그 문제를 더 작은 단위의 문제들로 쪼개서 작은 문제부터 풀어나가는 방법이다. 더 작은 단위로 쪼개진 문제를 풀어서 얻은 결과로 원래 문제의 해답에 점점 더 가까워지는 방식이다. 이 알고리즘의 헛점은 문제를 작은 단위로 쪼갤 수 있을 때만 사용할 수 있다는 것이다. 다이나믹 프로그래밍 알고리즘을 사용하는 가장 흔한 예제가 바로 피보나치 숫자이다. 피보나치 숫자는 그 전에 오는 두 숫자를 계속해서 더해 나가기 때문에 n번째 숫자를 알아내기 위해선 처음부터 계속 더해오면 된다. 두 숫자씩 더하는 작은 단.. 2023. 6. 13.

그리디 알고리즘(Greedy algorithm)이란? Goal 1. 그리디 알고리즘에 대해 알아보기 2. 예시 문제 풀어보기 그리디 알고리즘이란? 그리디(Greedy)란 단어는 탐욕이란 뜻을 가지고 있다. 그래서 그냥 쉽게 생각해서 코딩 문제를 풀 때 욕심쟁이처럼 지금 현재 가장 좋은 선택, 가장 최적의 선택만 하면 된다! 나중에 어떻게 되든간에 일단은 제일 최선의 선택을 계속 해나가면서 전체적으로도 그냥 최적의 선택이었기를 바라는 것이다. 예제 문제 (백준 5585번) 잔돈을 주는데 거스름돈 개수가 가장 적에 만들어보는 문제이다. 잔돈으로는 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 무한개가 있다고 생각하면 된다. Hint 1. 개수가 가장 적으려면 금액이 큰거부터 주면 될까 작은거부터 주면 될까? 해결 # 문제에서 준 입력값은 내야할 금액이므.. 2023. 5. 12.

[LeetCode] 2181번: 기존 연결 리스트 수정하기 Hint 1. 어떻게 하면 포인터 2개를 이용해서 기존 리스트를 원하는 결과로 수정할 수 있을까? 2. 포인터 1개는 수정하는 노드 위치에 (a), 다른 하나는 리스트 전체를 확인하는 용도(b)로 이용해보자! 3. 움직이는 포인터b가 그 다음 0에 도달할 때까지 숫자들을 수정하는 포인터a 위치에 더하면 된다. 4. 마지막 노드는 null에 연결되도록 바꿔야한다. LeetCode 2181번: Merge Nodes in Between Zeros (풀어보기) class Solution: def mergeNodes(self, head: Optional[ListNode]) -> Optional[ListNode]: # 포인터 2개 만들기 # now = 덧셈할 포인터 위치 # pointer = 리스트 전체를 확인할 .. 2023. 4. 30.

[LeetCode] 1828번: 원 안의 점 개수 Hint 1. 원과 점들의 최대 개수가 각각 500개이기 때문에 for문 2개를 사용해서 일일이 비교해도 된다 2. Follow up에 O(n)으로 풀어보라고 되어있지만 이건 나중에 도전...^^ LeetCode 1828번: Queries on Number of Points Inside a Circle (풀어보기) class Solution: def countPoints(self, points: List[List[int]], queries: List[List[int]]) -> List[int]: # points를 x, y 순서로 작은 숫자부터 큰 숫자까지 정렬한다 points = sorted(points, key=lambda x: (x[0],x[1])) answer = [] for query in que.. 2023. 4. 28.

[LeetCode] 876번: 연결 리스트 Goal 1. 연결 리스트 이해하기 2. 가장 간단한 연결 리스트 알고리즘 문제 풀어보기 연결 리스트(Linked List)란? 연결 리스트란 리스트 안에 있는 항목들이 그 다음 순서로 오는 항목과 연결되어 정해진 순서로 묶여 있는 리스트 구조를 말한다. LeetCode 876번: Middle of the Linked List (풀어보기) Hint 1. head라는 연결 리스트 구조의 정의 : head.val = 현재 위치의 수 head.next= 다음 연결된 리스트 2. 총 개수가 1개일 때는 현재 위치와 중간 지점의 위치가 같다 3. 연결된 리스트의 개수가 하나씩 늘어날 때마다 현재 위치와 중간 지점의 위치가 어떻게 변하는지 생각해보자 4. 총 개수가 홀수일 때와 짝수일 때 현재 위치와 중간 지점의 .. 2023. 3. 11.

[LeetCode] 226번: Invert Binary Tree Hint 1. DFS 알고리즘 사용해야함 2. 왼쪽과 오른쪽에 자식 노드가 있다면 바꿔치기 해주면 됨 LeetCode 226번: Invert Binary Tree (풀어보기) class Solution: def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]: def dfs(root): # 노드인지 확인. 노드가 아니라면 None 값이기 때문에 not을 해줘야 True가 됨 if not root: return root# 노드가 아니기 때문에 바꿔치기 안하고 그냥 반환 dfs(root.left)# 왼쪽 노드의 자식 노드 뒤집기 dfs(root.right)# 오른쪽 노드의 자식 노드 뒤집기 # 왼쪽 노드와 오른쪽 노드 바꿔치기 root.le.. 2023. 3. 10.

[LeetCode] 2236번: 트리 구조 Goal 1. 트리 구조 이해하기 2. 가장 간단한 트리 구조 알고리즘 문제 풀어보기 트리 구조란? 트리 구조란 노드(Node)와 자식노드(Child Node)로 구성된 구조를 얘기한다. 가장 흔히 보는 트리 구조는 바이너리 트리 구조(Binary Tree)로 각 노드가 왼쪽 오른쪽으로 자식노드 2개를 가진 형태다. LeetCode 2236번: Root Equals Sum of Children (풀어보기) Hint 1. root라는 트리 구조의 정의 : root.val = 현재 노드의 수 root.left = 현재 노드의 왼쪽 자식노드 root.right= 현재 노드의 오른쪽 자식노드 2. root.val이 현재 노드의 수라면 root.left 노드의 수를 구하려면? (정답은 밑에 하이라이트하면 보임) .. 2023. 3. 9.

[백준] 10808번: 알파벳 개수 Hint 1. 알파벳 개수는 총 26개로 정해져 있다. 2. ord()을 사용하면 알파벳을 아스키 숫자로 변환할 수 있다. 3. ord('a')는 97이다. 백준 10808번: 알파벳 개수 (풀어보기) # 알파벳 개수를 셀 수 있게 미리 0으로 된 리스트를 만들어 준다 alphabet = [0 for i in range(26)] for char in input(): # ord('a')는 97이기 때문에 97을 빼면 alphabet 리스트에서 0번째로 값을 추가할 수 있다 alphabet[ord(char) - 97] += 1 # 리스트는 join을 써서 string 형태로 합칠 수 있다. 이때, 리스트에 들어있는 값들은 string이어야 한다 print(' '.join(map(str, alphabet))) 2023. 3. 6.

[백준] 1927번: 최소 힙 Hint 1. 힙 자료구조 이용하기 (힙이란?) 2. 힙에서 heappop()을 하면 가장 작은 값이 반환 됨 백준 1927번: 최소 힙 import heapq import sys n = int(sys.stdin.readline()) heap = [] # 힙 만들기(리스트랑 만드는 법은 똑같음) for i in range(n): num = int(sys.stdin.readline()) if num == 0: # input 숫자가 0 이면 현재 힙에 들어있는 최소값 출력하기 print(heapq.heappop(heap) if heap != [] else 0) # 힙이 비어있지 않을 때만 heappop() 하기 else: heapq.heappush(heap, num) # 힙에 숫자 넣기 2023. 2. 28.

이전 1 2 다음

티스토리툴바