먼저 위의 문제는 그래프 탐색 문제로 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, ..

Disjoint Set 분리 집합 분리 집합은 서로소 집합이라고도 합니다. 용어의 의미처럼 분리 집합은 다음과 같은 특징을 가진다. 전체집합 U에 대해, U의 분리 집합 A, B는 다음 조건을 만족한다. - A, B는 U의 부분집합이다. - A, B는 공통 원소를 가지지 않는다. - A, B의 합집합이 곧 전체집합 U이다. (A, B에 속하지 않는 U의 원소가 없어야 한다.) Union-Find 알고리즘 union-Find 알고리즘은 그래프 알고리즘 중 하나로 서로소 집합, 상호배타적 알고리즘이라고도 불립니다. 여러 노드가 존재할 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘입니다. 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어집니다. 동작과정 노..

프림(Prim) 알고리즘 프림 알고리즘은 인접한 정점 중 최소비용으로 이동가능한 정점을 선택하면서 방문하는 알고리즘입니다. 즉, 인접 리스트를 사용한 정점들 간의 연결 관계가 필요하며, 이미 방문한 정점들에 대한 visit 정보를 기록합니다. 동작과정 최초 출발 정점에서 연결되어 있는 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 신장 트리에 포함된 모든 정점들과 연결된 간선들 중 가중치가 최소인 것을 선택해서 신장 트리에 추가합니다. 간선의 개수가 V-1개가 될 때까지 반복합니다. 모든 정점들이 간선으로 연결이 됐으면 종료합니다. 아래의 예제 그래프의 동작 과정을 그림을 통해 알아보겠습니다. 모든 과정을 통하면 위와 같은 그래프 형태를 나타냅니다. 프림(Prim) 알고리즘은 크루스칼..

스패닝 트리(Spanning Tree) 그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다. 위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다. 스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다. 최소 스패닝 트리(MST) 최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다. 위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다. 이렇게 최소 신장 트리를 효율적으로 찾..

오늘은 벌써 입소한 지 2주가 지나 2주 차 알고리즘 시험을 보는 날이다. 2주 차 알고리즘 범위는 이분 탐색, 분할 정복, 스택, 큐, 우선순위 큐였고 시험 문제로는 분할 정복 1문제, 스택 1문제, 우선순위 큐 1문제 였고 시험시간은 총 1시간 30분이었다. 처음에 각각의 문제 난이도를 살펴본 후 가장 낮은 난이도부터 공략할 생각이었지만 세 문제 모두 골드수준의 난이도였기 때문에 비교적 할만하다고 생각한 스택문제를 도전했다. 처음에는 여러가지 조건을 달아서 원하는 결과 값을 추출할 수 있도록 도전해 봤는데 그 안에 세부사항을 작성하기가 까다로워서 바로 방법을 바꿨다. 여기까지 오는데 시간은 벌써 30분이 지나서 한 문제라도 풀자는 조급한 마음에 스택문제를 1시간 정도 소요했지만 뭔지 모를 이유 때문에..

위 문제는 주어진 입력을 받았을 때 PPAP 문자열인지 아닌지 구분하는 문제입니다. 처음에 이 문제를 봤을때 if문을 여러개 해서 케이스에 맞게 구현을 시도했었는데 고려해야할 사항들도 많고 입력 값이 길어질 때의 케이스를 구현하기가 어려워서 최대한 스택을 활용해서 풀어보기로 했습니다. 먼저 예를 들어 PPPAPAP를 하나씩 나눠서 입력받는다고 가정하고 하나씩 stack에 입력합니다. stack에 입력하다가 stack을 뒤에서부터 4개를 잘랐을때 그 문자열이 PPAP일경우 PPAP를 pop해주고 p를 append해줍니다. 처음에는 stack을 앞에서부터 자를려고 시도했었다가 성립이 안되는 몇가지 반례를 발견하고 뒤에서부터 자르는걸로 방법을 바꿨습니다. from sys import stdin as s s =..

뱀 문제는 큐를 활용해서 뱀의 길이를 가지고 자신의 몸에 닿는지의 여부를 확인하는 것이 키 포인트입니다. 또한, 방향 전환에 사용하는 dx, dy의 개념과 정해진 N x N 크기를 벗어나면 종료되는 코드를 활용하면 코드를 짜기 수월해집니다. 우선 N * N 의 크기 배열에 0으로 다 값을 넣어줍니다. 그리고 사과의 개수 K만큼 반복문을 돌려주면서 arr배열에 사과의 위치를 1로 업데이트 시켜줘서 사과의 위치를 찾기 쉽게 만들어줍니다. 위의 코드에서 dx, dy는 방향을 정해줄 때 중요한 방법입니다. 많은 문제에서 이 부분이 활용될 수 있으니 알아두면 좋을 것 같습니다! dx, dy를 위아래로 잘라서 봐야하는데 위아래로 잘라서 4등분을 할경우 처음 dx = [0] , dy = [1] 이됩니다. dy만 1이..

이 문제는 우선 순위 큐를 활용해서 푸는 문제입니다. 처음에는 어떤 방식으로 큐에 넣어서 가장 많이 포함하는 부분을 구하는지와 두번째 값 기준으로 오름차순 정렬을 하는 부분에서 시간을 많이 소요했습니다. 우선 list에 입력값을 받아 sorted함수를 통해서 첫번째 값을 기준으로 오름차순 정렬을 한다음, lambda함수를 사용해서 두번쨰 값 기준으로 정렬을 한번더 해줍니다. 아래 코드는 위에 정렬된 h_o 리스트에서 각 선분의 길이가 철로의 길이(d)보다 긴 값들을 제거해주는 코드입니다. 위의 코드는 파이썬에서 우선순위 큐에 자주사용하는 heapq 를 사용해서 heap 리스트에 h_o_list 리스트값을 하나씩 넣고 heap의 길이의 최대값을 answer에 저장해서 마지막에 최대 카운트를 가져올 수 있는..