본문 바로가기
반응형

Algorithm283

위상 정렬 알고리즘 위상 정렬 (topological sorting) 방향 그래프에서 노드의 방문 순서를 찾는 알고리즘이다. 우리 일상에서 접할 수 있는 위상정렬의 한 예는 수업 커리큘럼이 있다. 내가 나온 학교의 예를 들면 c프로그래밍 > 고급 c 프로그래밍 > 자료구조 > 알고리즘 순으로 수강을 할 수있다. 즉 앞의 과목들은 선수과목이 되는것이다. 위 순서를 어기고선 수강을 할 수 없는데 이러한 순서를 찾는것이 위상정렬 알고리즘이다. 위상 정렬 알고리즘을 사용하기 위해선 사이클이 없는 방향 그래프여야 한다. 즉 A > B > C > A 로 돌아가는 방향을 갖는 그래프이면 안된다. 알고리즘은 간단하다. 1차원 배열로 그래프를 구현한다. 진입차수가 0인 그래프를 큐에 넣는다. 큐를 빼면서 해당 노드의 다음 노드의 진입차수를.. 2024. 2. 26.
[Python] 백준 2206번 - 벽 부수고 이동하기 (골드 3) 혼자 힘으로 풀었는가? O 알고리즘 분류 - BFS - 그래프 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하.. 2024. 2. 16.
[Python] 백준 14002번 - 가장 긴 증가하는 부분 수열 4 (골드 4) 혼자 힘으로 풀었는가? O 알고리즘 분류 - 다이나믹 프로그래밍 (DP) https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20.. 2024. 2. 5.
[Python] 백준 3055번 - 탈출 (골드 4) 혼자 힘으로 풀었는가? O 알고리즘 분류 - BFS https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 .. 2024. 2. 1.
반응형