알고리즘
-
위상 정렬💡 - 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다. - 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다. 비순환 방향 그래프(DAG) - 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다. - 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다. 위상 정렬 동작 과정 진입차수(in_degree)가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 1) 모든 정점의 in_degree를 표시합니다...
[알고리즘] 위상 정렬위상 정렬💡 - 위상 정렬(Topological sort)는 비순환 방향 그래프에서 정점을 선형으로 정렬하는 것입니다. - 모든 간선(u,v)에 대해 정점 u가 정점v보다 먼저 오는 순서로 정렬이 됩니다. 비순환 방향 그래프(DAG) - 비순환 방향 그래프는 사이클이 없는 방향 그래프입니다. - 왼쪽 그림과 오른쪽 그림의 차이는 정점2에서의 간선차이입니다. 정점끼리 사이클이 생기면 비순환 방향 그래프가 아니게 됩니다. 위상 정렬 동작 과정 진입차수(in_degree)가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 1) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2) 새롭게 진입차수가 0이 된 노드를 큐에 삽입 1) 모든 정점의 in_degree를 표시합니다...
2023.04.26 -
위의 문제는 bfs를 활용해서 고슴도치가 비버의 집을 찾아가는 시간을 출력하는 문제입니다. 이 문제를 풀 때 고슴도치를 먼저 이동할지 물을 이동할지 고민을 하다가 저는 고슴도치를 먼저 이동하고 물을 이동하는 방식으로 풀어봤습니다. 이렇게 하면 물이 다음에 이동할 거리를 생각안해도되므로 고슴도치의 조건이 하나 줄어듭니다. R,C = map(int,s.readline().split()) graph = [list(map(str,s.readline().strip())) for _ in range(R)] v = [[0]*C for _ in range(R)] q = deque() 우선 진행에 필요한 데이터들을 미리 생성해두고 bfs함수와 조건들을 생성합니다. #비버 집 위치 저장 for i in range(R): ..
[백준] 3055 탈출 [Python]위의 문제는 bfs를 활용해서 고슴도치가 비버의 집을 찾아가는 시간을 출력하는 문제입니다. 이 문제를 풀 때 고슴도치를 먼저 이동할지 물을 이동할지 고민을 하다가 저는 고슴도치를 먼저 이동하고 물을 이동하는 방식으로 풀어봤습니다. 이렇게 하면 물이 다음에 이동할 거리를 생각안해도되므로 고슴도치의 조건이 하나 줄어듭니다. R,C = map(int,s.readline().split()) graph = [list(map(str,s.readline().strip())) for _ in range(R)] v = [[0]*C for _ in range(R)] q = deque() 우선 진행에 필요한 데이터들을 미리 생성해두고 bfs함수와 조건들을 생성합니다. #비버 집 위치 저장 for i in range(R): ..
2023.04.26 -
위의 문제는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용해서 푸는 대표적인 문제입니다. 먼저 다익스트라 알고리즘의 동작 과정을 간단하게 소개하면 다음과 같습니다. 출발 노드와, 도착 노드를 설정 알고 있는 모든 거리 값을 부여 (모를 경우 무한(아주 큰 값)으로 설정) 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리르 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다. 우선 순위 큐를 사용하여 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리고 ..
[백준] 1916 최소비용 구하기 [Python]위의 문제는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용해서 푸는 대표적인 문제입니다. 먼저 다익스트라 알고리즘의 동작 과정을 간단하게 소개하면 다음과 같습니다. 출발 노드와, 도착 노드를 설정 알고 있는 모든 거리 값을 부여 (모를 경우 무한(아주 큰 값)으로 설정) 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리르 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다. 우선 순위 큐를 사용하여 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리고 ..
2023.04.25 -
먼저 위의 문제는 그래프 탐색 문제로 dfs, bfs 방법으로 풀 수 있습니다. 저는 dfs를 활용해서 문제를 풀어봤습니다. 처음에는 접근하는 방법이 잘못됐는지 얼음의 개수를 판단하는 함수와 dfs 함수를 구현하고나서 연도를 구하는데 한참 헤맸습니다.. 우선 메인부분부터 작성을 하면 아래와 같습니다. N,M = map(int,s.readline().split()) year = 0 arr = [list(map(int,s.readline().split())) for _ in range(N)] dx =[0,1,0,-1] dy =[1,0,-1,0] ice_cnt=0 N과 M 입력을 받고 연도를 구할 때 필요한 year와 arr 배열을 이중행렬로 받아서 표시합니다. 얼음 주변의 0의 개수를 파악하기 위해 dx, ..
[백준] 2573 빙산 [Python]먼저 위의 문제는 그래프 탐색 문제로 dfs, bfs 방법으로 풀 수 있습니다. 저는 dfs를 활용해서 문제를 풀어봤습니다. 처음에는 접근하는 방법이 잘못됐는지 얼음의 개수를 판단하는 함수와 dfs 함수를 구현하고나서 연도를 구하는데 한참 헤맸습니다.. 우선 메인부분부터 작성을 하면 아래와 같습니다. N,M = map(int,s.readline().split()) year = 0 arr = [list(map(int,s.readline().split())) for _ in range(N)] dx =[0,1,0,-1] dy =[1,0,-1,0] ice_cnt=0 N과 M 입력을 받고 연도를 구할 때 필요한 year와 arr 배열을 이중행렬로 받아서 표시합니다. 얼음 주변의 0의 개수를 파악하기 위해 dx, ..
2023.04.25 -
프림(Prim) 알고리즘 프림 알고리즘은 인접한 정점 중 최소비용으로 이동가능한 정점을 선택하면서 방문하는 알고리즘입니다. 즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록합니다. 동작과정 최초 출발 정점에서 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 신장 트리에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 간선의 개수가 V-1개가 될 때까지 반복합니다. 모든 정점들이 간선으로 연결이 됐으면 종료합니다. 아래의 예제 그래프의 동작 과정을 그림을 통해 알아보겠습니다. 모든 과정을 통하면 위와 같은 그래프 형태를 나타냅니다. 프림(Prim) 알고리즘은 크루스칼..
[알고리즘] 최소 신장 트리(MST) : 프림 알고리즘프림(Prim) 알고리즘 프림 알고리즘은 인접한 정점 중 최소비용으로 이동가능한 정점을 선택하면서 방문하는 알고리즘입니다. 즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록합니다. 동작과정 최초 출발 정점에서 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 신장 트리에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 간선의 개수가 V-1개가 될 때까지 반복합니다. 모든 정점들이 간선으로 연결이 됐으면 종료합니다. 아래의 예제 그래프의 동작 과정을 그림을 통해 알아보겠습니다. 모든 과정을 통하면 위와 같은 그래프 형태를 나타냅니다. 프림(Prim) 알고리즘은 크루스칼..
2023.04.21 -
스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..
[알고리즘] 최소 신장 트리(MST) : 크루스칼 알고리즘스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..
2023.04.21 -
위 문제는 주어진 입력을 받았을 때 PPAP 문자열인지 아닌지 구분하는 문제입니다. 처음에 이 문제를 봤을때 if문을 여러개 해서 케이스에 맞게 구현을 시도했었는데 고려해야할 사항들도 많고 입력 값이 길어질 때의 케이스를 구현하기가 어려워서 최대한 스택을 활용해서 풀어보기로 했습니다. 먼저 예를 들어 PPPAPAP를 하나씩 나눠서 입력받는다고 가정하고 하나씩 stack에 입력합니다. stack에 입력하다가 stack을 뒤에서부터 4개를 잘랐을때 그 문자열이 PPAP일경우 PPAP를 pop해주고 p를 append해줍니다. 처음에는 stack을 앞에서부터 자를려고 시도했었다가 성립이 안되는 몇가지 반례를 발견하고 뒤에서부터 자르는걸로 방법을 바꿨습니다. from sys import stdin as s s =..
[백준] 16120 PPAP [Python]위 문제는 주어진 입력을 받았을 때 PPAP 문자열인지 아닌지 구분하는 문제입니다. 처음에 이 문제를 봤을때 if문을 여러개 해서 케이스에 맞게 구현을 시도했었는데 고려해야할 사항들도 많고 입력 값이 길어질 때의 케이스를 구현하기가 어려워서 최대한 스택을 활용해서 풀어보기로 했습니다. 먼저 예를 들어 PPPAPAP를 하나씩 나눠서 입력받는다고 가정하고 하나씩 stack에 입력합니다. stack에 입력하다가 stack을 뒤에서부터 4개를 잘랐을때 그 문자열이 PPAP일경우 PPAP를 pop해주고 p를 append해줍니다. 처음에는 stack을 앞에서부터 자를려고 시도했었다가 성립이 안되는 몇가지 반례를 발견하고 뒤에서부터 자르는걸로 방법을 바꿨습니다. from sys import stdin as s s =..
2023.04.21 -
뱀 문제는 큐를 활용해서 뱀의 길이를 가지고 자신의 몸에 닿는지의 여부를 확인하는 것이 키 포인트입니다. 또한, 방향 전환에 사용하는 dx, dy의 개념과 정해진 N x N 크기를 벗어나면 종료되는 코드를 활용하면 코드를 짜기 수월해집니다. 우선 N * N 의 크기 배열에 0으로 다 값을 넣어줍니다. 그리고 사과의 개수 K만큼 반복문을 돌려주면서 arr배열에 사과의 위치를 1로 업데이트 시켜줘서 사과의 위치를 찾기 쉽게 만들어줍니다. 위의 코드에서 dx, dy는 방향을 정해줄 때 중요한 방법입니다. 많은 문제에서 이 부분이 활용될 수 있으니 알아두면 좋을 것 같습니다! dx, dy를 위아래로 잘라서 봐야하는데 위아래로 잘라서 4등분을 할경우 처음 dx = [0] , dy = [1] 이됩니다. dy만 1이..
[백준] 3190 뱀 [Python]뱀 문제는 큐를 활용해서 뱀의 길이를 가지고 자신의 몸에 닿는지의 여부를 확인하는 것이 키 포인트입니다. 또한, 방향 전환에 사용하는 dx, dy의 개념과 정해진 N x N 크기를 벗어나면 종료되는 코드를 활용하면 코드를 짜기 수월해집니다. 우선 N * N 의 크기 배열에 0으로 다 값을 넣어줍니다. 그리고 사과의 개수 K만큼 반복문을 돌려주면서 arr배열에 사과의 위치를 1로 업데이트 시켜줘서 사과의 위치를 찾기 쉽게 만들어줍니다. 위의 코드에서 dx, dy는 방향을 정해줄 때 중요한 방법입니다. 많은 문제에서 이 부분이 활용될 수 있으니 알아두면 좋을 것 같습니다! dx, dy를 위아래로 잘라서 봐야하는데 위아래로 잘라서 4등분을 할경우 처음 dx = [0] , dy = [1] 이됩니다. dy만 1이..
2023.04.18