1. 자료구조 및 알고리즘 7일차 수강하기
- BFS
- 백트래킹
2. 새롭게 알게된 지식
과제 1 : 부분 집합 https://leetcode.com/problems/subsets/
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
- 접근 :
DFS 가 더욱 적합하지만 BFS 를 배웠기 때문에 BFS 로 풀기
- 코드 구현 :
과제 2 : 코스 스케줄 https://leetcode.com/problems/course-schedule
LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
- 접근 :
DFS 를 사용하여 탐색, 탐색이 끝나면 해당 시작점을 방문 노드에서 삭제
- 코드 구현 :
과제 3 : DFS와 BFS https://www.acmicpc.net/problem/1260
1260번: DFS와 BFS
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사
www.acmicpc.net
- 접근 :
DFS 와 BFS 로 같은 문제 풀어 보기
- 코드 구현 :
import sys
from collections import deque
class Solution:
def __init__(self):
self.input = sys.stdin.readline
self.output = sys.stdout.write
self.dfs_visited = []
self.bfs_visited = []
self.dict = {}
def dfs(self, start : int, res = '') -> str:
res += str(start) + ' '
self.dfs_visited[start] = True
for next in self.dict[start]:
if not self.dfs_visited[next]:
res = self.dfs(next, res)
return res
def bfs(self, start : int) -> str:
Q = deque()
Q.append(start)
res = str(start) + ' '
self.bfs_visited[start] = True
while Q :
now = Q.popleft()
for next in self.dict[now]:
if not self.bfs_visited[next]:
res += str(next) + ' '
Q.append(next)
self.bfs_visited[next] = True
return res
def run(self):
N, M, V = map(int, self.input().split(' '))
self.dict = { i : [] for i in range(1, N+1)}
self.dfs_visited = [False] * (N + 1)
self.bfs_visited = [False] * (N + 1)
for _ in range(M):
a,b = map(int,self.input().split(' '))
self.dict[a].append(b)
self.dict[b].append(a)
for values in self.dict.values():
values.sort()
self.output(self.dfs(V) + '\n')
self.output(self.bfs(V) + '\n')
s = Solution()
s.run()
과제4 : 1, 2, 3 더하기 https://www.acmicpc.net/problem/9095
9095번: 1, 2, 3 더하기
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
www.acmicpc.net
- 접근 :
DFS 로 접근 하였지만, 실제 해결방법은 DP를 사용해야 함
- 코드 구현 :
과제5 : 암호 만들기 https://www.acmicpc.net/problem/1759
1759번: 암호 만들기
첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다.
www.acmicpc.net
- 접근 :
브루트 포스로 해당하는 모든 경우의 수를 찾음
- 코드 구현 :
'개발일지' 카테고리의 다른 글
3주차 WIL (0) | 2024.02.18 |
---|---|
심화 과정 8 일차 (0) | 2024.02.18 |
심화 과정 6 일차 (1) | 2024.02.15 |
심화 과정 5 일차 (0) | 2024.02.13 |
2주차 WIL (0) | 2024.02.09 |