[Algorithm] - 위상정렬(Topological Sort)

[Algorithm] - 위상정렬(Topological Sort)

위상정렬이란위상정렬은 방향 그래프(Directed Graph)에서 노드 간의 순서를 정하는 알고리즘이다.특히, 순서가 정해져있는 작업(노드)들을 차례대로 수행(방문)해야 할 때 사용된다.예를 들어,컴파일러의 작업 순서 결정수강 과목 순서 정하기 (선수 과목 존재 시)빌드 시스템: 어떤 파일을 먼저 빌드해야 하는지 결정업무 순서 계획: 작업 간 의존 관계가 있을 때 순서 지정이 대표적인 예시다. 위상 정렬의 조건방향 비순환 그래프(DAG, Directed Acyclic Graph)이어야 한다.만일 노드 간 사이클이 존재한다면 위상정렬은 불가능하다.순서가 정해진 정점들을 선형적으로 나열해야한다. 위상정렬의 개념위상정렬은 진입차수(in-degree) 개념을 기반으로 동작한다.진입차수(in-degree)란, 어..

  • format_list_bulleted 알고리즘
  • · 2025. 4. 14.
  • textsms
[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

[BOJ] - 달이 차오른다, 가자. / 1194번 (Java)

[BOJ] - 달이 차오른다, 가자. / 1194번 (Java) [BOJ] - 달이 차오른다, 가자. / 1194번 (Java) 1. 문제 접근 문제의 궁극적인 목표는 '0'(출발지)에서 '가장 가까운 1'(도착지)로 갈 때, 이동 횟수의 최솟값을 구하는 것이다. 단, 몇가지 제약 사항이 존재한다. 벽으로는 절대 이동할 수 없다. 빈칸은 언제나 이동할 수 있다. 총 6개의 열쇠('a', 'b', 'c', 'd', 'e', 'f')가 존재하고, 각 열쇠는 6개의 문( 'A', 'B', 'C', 'D', 'E', 'F' )를 열 수 있다. 즉, 열쇠를 얻고, 문을 여는 것에 대한 탐색을 어떻게 할 것인지가 관건이다. 탐색을 진행하며 만나는 중요한 지점은 2가지다. 4방 탐색을 진행한 결과 문을 만난다. 4방..

  • format_list_bulleted 알고리즘
  • · 2024. 3. 27.
  • textsms
[BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java)

[BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java)

[BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java) [BOJ] - 녹색 옷 입은 애가 젤다지? / 4485번 (Java) 1. 문제 접근 [0, 0]에서 출발하여, [N-1, N-1]까지 이동하며 "최소 비용"을 구하면 된다. 해당 문제는 최소비용을 구하는 문제로, 다익스트라 알고리즘을 사용해도 되지만, 2차원 배열에서 다익스트라 알고리즘을 사용하는 걸 선호하지 않아 BFS로 접근했다. 중요한 점은 "이동하기 위해서는(`Queue`에 넣기 위해서는) 비용이 갱신 되어야한다"는 것이다. 다른 BFS들과 달리 방문 배열(`isVisited[]`)를 사용하지 않고, 현재 비용 + 다음 위치 비용이 이전의 비용보다 작을 경우 `Queue`에 삽입한다. // 비용 검증(갱신 할 필요가 있는가) ..

  • format_list_bulleted 알고리즘
  • · 2024. 3. 27.
  • textsms
[BOJ] - 평범한 배낭 / 12865번 (Java)

[BOJ] - 평범한 배낭 / 12865번 (Java)

[BOJ] - 평범한 배낭 / 12865번 (Java) [BOJ] - 평범한 배낭 / 12865번 (Java) 1. 문제 접근 DP를 적용하는 0/1 Knapsack 문제의 대표 문제 유형이다. 물품에는 2개의 요소가 있다 (`부피`, `가치`) 둘 중 부피를 기준으로 2차원 동적 테이블을 생성한다. 동적 테이블의 정의는 다음과 같다. dpTable[item][volume]: 부피 volume을 만족하는 item을 포함하는 최대 가치 0번 물품부터 N-1번 물품까지 탐색하며, 각 물품을 포함하며 얻을 수 있는 최대 가치를 구하면 된다. 2가지 경우가 존재한다. 물품을 넣을 수 없는 경우 물품을 넣을 수 있는 경우 먼저 물품을 넣을 수 없는 경우는 현재 물품의 부피가 고려 중인 부피보다 큰 경우이다. 따라..

  • format_list_bulleted 알고리즘
  • · 2024. 3. 27.
  • textsms
[BOJ] - RGB거리 / 1149번 (Java)

[BOJ] - RGB거리 / 1149번 (Java)

[BOJ] - RGB거리 / 1149번 (Java) [BOJ] - RGB거리 / 1149번 (Java) 1. 문제 접근 N개의 집에 대해 인접한 집이 서로 다른 색으로 칠해지도록 하는 경우의 수 중, 최소 비용을 구하면 된다. 1번 집의 경우는 3가지 색 모두 사용하여 칠할 수 있다. 2번 집의 경우 1번 집의 색이 아닌 2개의 색 중 하나를 골라 칠할 수 있다. 이후 집들도 모두 동일하다. 따라서, 각 집에 대해 특정 색으로 칠했을 때의 비용을 누적해가면서 최적해를 찾으면 되는 DP문제다. 2차원 DP 동적 테이블이 필요하다. 테이블의 크기는 3행(R, G, B) N열이 된다. // 0행: R // 1행: G // 2행: B dp = new int[3][N]; 첫 집의 경우는 모든 색 칠할 수 있으므로..

  • format_list_bulleted 알고리즘
  • · 2024. 2. 28.
  • textsms
[BOJ] - 1로 만들기 / 1463번 (Java)

[BOJ] - 1로 만들기 / 1463번 (Java)

[BOJ] - 1로 만들기 / 1463번 (Java) [BOJ] - 1로 만들기 / 1463번 (Java) 1. 문제 접근 N이 주어졌을 때, 1로 만들기 위한 연산의 최소 횟수를 구하면 된다. 연산을 1. 3으로 나누기, 2. 2로 나누기, 3. 1빼기 총 3가지가 존재한다. 해당 문제는 DP로 풀 수 있지만, 나의 경우에는 BFS를 통해 풀었다. N을 시작점으로, 도달할 수 있는 번호를 `Queue`에 넣으면서 진행했다. 나누기 연산의 경우, 나누어 떨어질 경우만 고려했고, 공통적으로 기존의 거리(`dist`)와 비교하여 짧은 경우에 한하여 `Queue`에 삽입했다. int currNum = q.poll(); if (currNum == GOAL) break; if (currNum % 3 == 0 &&..

  • format_list_bulleted 알고리즘
  • · 2024. 2. 28.
  • textsms