이것저것 코딩하는 블로그

1. 다익스트라 알고리즘 다익스트라 알고리즘은 가중치가 있는 그래프에서, 특정 시작점에서 다른 모든 정점으로 가는 최단거리를 각각 구해주는 알고리즘이다. 이는 특정 지점까지의 거리 = A까지 가는 거리 + A에서 특정 지점까지 소요되는 거리 라는 아이디어를 기반으로 한다. 과정을 살펴보면 다음과 같다. 1) 거리 배열을 최댓값으로 초기화하고, 출발지의 값만 0으로 설정한다. 2) 현재 방문하지 않은 정점 중 가장 거리 값이 작은 지점을 선택한다. 3) 해당 지점과 인접한 지점들의 거리를 갱신한다. 4) 모든 지점이 선택될 때 까지, 2와 3을 반복한다. 다음 그래프를 통해 살펴보자. 자세한 설명은 다음 링크를 참고하면 된다. 많은 도움을 받았다. https://www.codetree.ai/missions..

1. BFS란? BFS는 너비 우선 탐색으로, 그래프를 층별로 탐색하는 것이다. 자세히 얘기하자면, 한 노드를 방문했을 때 그 노드의 모든 자식 노드를 방문해야 다음 노드로 갈 수 있다. 이 과정을 루트 노드부터 시작해서 모든 리프 노드를 방문할 때까지 반복한다. DFS와 달리 모든 리프 노드를 방문했다면 탐색이 끝난 것이므로 (맨 아래층에 있으므로) 종료한다. 예제를 통해 살펴보자. 다음과 같은 그래프를 너비 우선 탐색으로 탐색하고자 한다. 먼저 루트 노드인 9를 방문한다. 이후 9의 자식 노드인 8과 6을 방문한다. 자식 노드를 방문했으면, 자식 노드 중 가장 왼쪽으로 이동해 그 노드의 자식들을 모두 방문한다. 여기서는 5와 2가 된다. 이후 오른쪽 노드로 이동해 자식을 방문한다. 여기서는 1이 된다..

1. DFS란? 깊이 우선 탐색(DFS)는 의미 그대로 깊이를 우선으로 하여 탐색하는 것이다. 자세히 얘기하자면, 루트 노드에서 시작해서 자식 노드로 이동한다 (보통 왼쪽 노드로 이동한다). 이동한 자식 노드에서 다시 자식 노드로 이동한다. 이 과정을 자식 노드가 없을 때까지 (리프 노드에 갈 때까지) 반복한다. 리프 노드에 도달하면, 리프 노드의 부모 노드로 가서 다시 오른쪽 자식을 방문한다. 오른쪽 자식에서 위에서 했던 과정을 반복한다. 이 재귀적인 방문을 탐방이라고 하겠다. 이렇게 모든 노드를 방문할 때까지 탐방을 완료하면 search가 끝난다. 그래프를 예를 들어보자. 위와 같은 그래프가 있다고 할때, 깊이 우선 탐색으로 탐색해보자. 루트에서 왼쪽으로 계속 이동하며 리프 노드가 나올 때까지 가므로..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/scheduling-meeting-room/introduction 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 하나의 회의실이 있고, n개의 회의 요청이 들어왔다. 각 회의의 시작 시간과 끝 시간이 주어져 있으며, 한 회의가 시작되면 도중에 그만둘 수 없고, 한 회의가 끝나는 직후에 동시에 다른 회의가 시작될 수 있다. 적절하게 회의 요청을 수락하여 최대로 많은 회의가 진행되도록 만들어보자. 이 문제는 회의 끝 시간을 기준으로 정렬하여 가장 빨리 끝나는 회의 중 겹치지..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/fractional-knapsack/introduction 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai knapsack 문제를 변형한 문제다. 다른 조건은 동일하다. 단, 보석을 쪼개어 담을 수 있다는 점이 차이점이다. 보석을 쪼개어 담을 수 있을 때, 가장 가치가 높도록 보석을 담는 문제다. 1. 풀이 이 문제는 knapsack 문제와 달리 동적계획법으로 접근할 수 없다. 보석을 어떻게 쪼개느냐에 따라 결과가 달라지기 때문이다. 그리디 (Greedy) 알고리즘으로 접..

0. 문제 link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-number-pass/description 코드트리 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 주어진 숫자를 쪼개어 암호를 만들려고 한다. 암호를 만드는 과정은 다음과 같다. 1. 숫자를 1, 2, 3, 4의 합으로 바꾼다. 2. 숫자의 합에서 사용된 숫자를 일렬로 나열한다. 일례로, 3을 활용하면 1+1+1 = 111 2+1 = 21 1+2 =12 3 = 3 4개의 암호를 만들 수 있다. 숫자 n이 주어졌을 때 만들 수 있는 암호의 가짓수를 구해보자. 1. 풀이 이는 ..