이 문제의 분류는 그리디 알고리즘과 우선순위 큐를 활용해서 푸는 문제입니다. 그리디 알고리즘만 사용하고 우선순위 큐를 사용하지 않는다면 시간초과가 나서 우선순위 큐를 사용하는 방법으로 구현해봤습니다. k = int(s.readline()) #우선 순위 큐 저장 배열선언 heap =[] #출력값들을 저장할 배열선언 answer= [0] * (k+1) lecture = [list(map(int,s.readline().split())) for _ in range(k)] #강의를 시작시간과 끝나는시간 기준으로 정렬 lecture.sort(key=lambda x:(x[1],x[2])) 강의를 시작시간과 끝나는시간으로 정렬하고 heap에 넣어야 새로운 강의를 넣을 때 마다 비교가 가능하므로 정렬해준다. #1은 강의..

이 문제는 기본적은 bfs문제에서 살짝 꼬아서 낸 문제입니다. 저는 처음 문제를 읽고 풀 때 N*N 배열을 N*K 배열로 글을 잘 못 읽고 풀어서 indexerror가 많이 발생했었는데 다시 제대로 읽어보니 N*N배열이고 K는 바이러스의 종류라는 것을 깨달았습니다.. bfs,dfs 문제를 풀 때에는 각 행,열의 변수와 문제에서 주어지는 조건 변수들을 잘 정리하고 문제를 풀기 시작하면 도움이 될 것 같습니다. #N,K의 입력을 받음 N,K = map(int,s.readline().split()) #각 행을 graph 이중배열에 저장 graph=[list(map(int,s.readline().split()))for _ in range(N)] # S,X,Y의 값 입력 받음 S,X,Y = map(int,s.re..

위의 문제는 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): ..

위의 문제는 최소 비용을 구하는 문제로 다익스트라 알고리즘을 활용해서 푸는 대표적인 문제입니다. 먼저 다익스트라 알고리즘의 동작 과정을 간단하게 소개하면 다음과 같습니다. 출발 노드와, 도착 노드를 설정 알고 있는 모든 거리 값을 부여 (모를 경우 무한(아주 큰 값)으로 설정) 출발 노드부터 시작하여, 방문하지 않은 인접 노드를 방문, 거리르 계산한 다음, 현재 알고있는 거리보다 짧으면 해당 값으로 갱신한다. 현재 노드에 인접한 모든 미방문 노드까지의 거리를 계산했다면, 현재 노드는 방문한 것이므로, 미방문 집합에서 제거한다. 도착 노드가 미방문 노드 집합에서 벗어나면, 알고리즘을 종료한다. 우선 순위 큐를 사용하여 지금까지 발견된 가장 짧은 거리의 노드에 대해서 먼저 계산할 수 있으며, 더 긴 거리고 ..

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

위 문제는 주어진 입력을 받았을 때 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에 저장해서 마지막에 최대 카운트를 가져올 수 있는..