👾

목차 DFS의 개념 DFS의 장단점 DFS의 시간 복잡도 DFS의 구현 DFS(깊이 우선 탐색)이란? DFS(Depth-First Search) 또는 깊이 우선 탐색이라고 부름 그래프에서 깊은 부분을 먼저 탐색하는 알고리즘 스택 자료구조 또는 재귀 함수를 이용함 DFS의 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 존재하면 그 노드를 스택에 넣고 방문 처리를 합니다. 만약 방문하지 않은 인접 노드가 없다면 스택의 최상단 노드를 꺼냅니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. DFS의 장단점 장점 현재 경로 상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다. 목표 노드가 깊은 단계에 있을 경우 답을 빨리..

문제 링크: www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 설명 적록색약인 사람과 아닌 사람의 matrix를 따로 만들어서 생각합니다. 저는 적록색약의 matrix는 G를 모두 R로 바꿔서 문제를 풀었습니다. 각각의 matrix를 BFS를 이용해 상, 하, 좌, 우로 연결된 같은 색을 모두 탐색합니다. 이때 상, 하, 좌, 우 인덱스를 편하게 계산하기 위해 dx, dy를 정의해서 사용했습니다. 방문한 matrix의 원소는 0을 대입해서 방문 처..

문제 링크: 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를 수행하면 됩니다. 저는 (N + 1) X (N + 1) 크기의 matrix를 이용해 정점 간의 간선을 표시했습니다. 또한 dfs를 할 땐 방문한 노드를 1로 표현하고 bfs를 할 땐 0으로 표현해서 visited를 따로 초기화할 필요 없이 바로 사용할 수 있도록 했습니다. 소스코드 def dfs(v): # 방문 노드 1로 표현..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제 설명 모든 경우의 수를 DFS(깊이 우선 탐색)으로 확인해서 타겟 넘버를 만드는 경우를 셌습니다. 소스코드 answer = 0 def dfs(idx, numbers, total_sum, target): global answer n = len(numbers) # 마지막 원소까지 계산했다면 return if ..

문제 링크: www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 설명 면접자들을 서류 점수가 높은 순서대로 정렬한 뒤, 면접 점수에 대해 생각합니다. 서류 점수가 1등인 사람은 무조건 뽑히고, 2등인 사람은 1등보다 면접 순위가 높으면 뽑힙니다. 3등은 1, 2등보다 면접 순위가 높이면 뽑히고 나머지 사람들도 비슷하게 계산합니다. 따라서 서류 순위가 높은 순서대로 면접자를 정렬하고, 각 면접자들의 면접 순위가 면접 커트라인보다 더 높은..

문제 링크: www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 설명 만약 n이 1이나 3이 주어진다면, 2원과 5원으로는 거슬러 줄 수 없으므로 -1을 반환합니다. 나머지는 최소 개수의 동전으로 거슬러줘야 하므로 5원을 먼저 거슬러주는 방법을 선택했습니다. n을 5로 나눴을 때 나머지는 다음과 같이 5가지입니다. (x: n을 5로 나눈 몫) 나머지가 0일 경우 5원으로만 거슬러 줄 수 있으므로 answer = x 나머지가 1일 경우 5원을 하나 빼고 2원 3개를 추가해야 합니다. => 5x + 1 = 5(x - 1) + (2 * 3) 따라서 anwer = (x - 1) + ..

목차 Greedy 알고리즘 개념 Greedy 알고리즘 예시 Greedy 알고리즘 다른 문제들 그리디(Greedy) 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 방법 즉, 전후 결정에 관계없이 당시 "가장 최고"라고 생각되는 것을 선택해서 최적의 해를 구하는 방법 대표적인 예시로 MST(최소신장트리) 알고리즘, 다익스트라(Dijkstra) 알고리즘, 거스름돈 문제가 있다 그리디 알고리즘 쉬운 예시 점원이 계산을 마치고 거스름돈을 돌려주는 상황을 생각해봅시다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 충분히 많이 존재한다고 가정합니다. 손님에게 N원을 거슬러 줘야 할 때, 최소 개의 동전으로 거스름 돈을 줄 방법을 구하세요. 단, 거슬러 줘야 할 돈 N은 항상..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 풀이 이분 탐색으로 풀 아이디어가 도저히 안 떠올라서 다른 사람의 풀이를 참조해서 풀었다. (hyeon930님 풀이) 이분탐색으로 바위를 제거하는 것이 아니라, 이분 탐색을 이용해 각 지점 사이의 거리의 최댓값을 구해야 되는 문제였다. 문제를 다시 생각해보면, "각 지점 사이의 거리의 최솟값이 x가 될 수 있는가?"를 만족하는 x들 중에 최댓값을 찾는..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 풀이 나는 처음에 차량을 진입 시점이 빠른 순서대로 정렬해서 문제를 풀었는데, 다른 사람들의 풀이를 보니 진출 시점이 빠른 순서대로 정렬 후 문제를 푸는게 더 간단했다. 진출 시점이 빠른 순서대로 차량을 정렬한다. 1) 차량의 진입 시점이 camera보다 앞에 있다면(작거나 같다면) => 차량 경로가 camera 위치에 포함되므로 추가 카메라 설치 필요 없음 2) 차량의 진입 시점이 camera보다 뒤에 있다면(크다면) => 현재 차량의 진출 시점에 다른 카메라를 설치..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 풀이 Kruskal(크루스칼) 알고리즘을 이용해서 문제를 해결했다. 섬 사이에 다리 연결에 드는 비용이 적은 순서대로 costs를 정렬한다. set[i]를 초기화해준다. set[i]는 i번째 노드의 부모 노드를 저장하는 배열이다. 부모노드란 i번째 노드와 연결된 모든 노드 중에서 인덱스가 가장 작은 노드이다. 예를 들어 노드0과 노드1이 연결되면 set[0] = 0, set[1] = 0이 저장된다. 정렬된 costs를 모두 탐색할 때까지 다음을 반복한다. - 연..