이 문제의 분류는 그리디 알고리즘과 우선순위 큐를 활용해서 푸는 문제입니다. 그리디 알고리즘만 사용하고 우선순위 큐를 사용하지 않는다면 시간초과가 나서 우선순위 큐를 사용하는 방법으로 구현해봤습니다. 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은 강의..

이 문제는 얼핏하면 dfs, bfs처럼 보여서 나도 처음에는 dfs로만 구현을 했었다. 하지만 dfs로 구현하면 값이 커질수록 반복되는 구간이 증가하기때문에 당연히 시간초과가 났었고 이를 고치기 위해 dp를 이용한 방법을 추가시켰다. 처음에는 dp를 어떻게 적용해야하는지가 감이 안와서 주변 친구들에게 도움을 받아서 이해를 하게 되었다. 이 문제를 시작점에서부터 도착점으로 가는 경로의 수를 구하는 문제에서, 임의의 점(x, y)에서 도착점 까지의 경우로 세분화 하여 구한다면, 그 어떤 경로로 (x, y)에 도착 하기만 해도 그 때부터의 경우의 수는 다시 구할 필요가 없다. 이 관점으로 코드를 구현해보자. 우선 처음에 dfs만 구현해서 시간초과가 난 코드이다. from sys import stdin as s..

저는 위의 문제를 다이내믹 프로그래밍을 활용해서 풀어봤습니다. 주어진 N의 크기와 M이 커질수록 시간이 급속도로 증가하기 때문에 dp로 값을 저장해 주고 필요한 연산만 걸쳐서 원하는 값을 출력하는 것이 시간에 걸리지 않기 때문에 dp를 활용했습니다. 우선 배열의 크기 N과 합의 횟수 M 을 입력받습니다. #입력 값 n = 배열의 크기 n*n , m = 합을 구해야하는 횟수 n,m = map(int,s.readline().split()) arr=[list(map(int,s.readline().split())) for _ in range(n)] #dp를 [1][1]시작하기위해 n+1로설정 dp=[[0]*(n+1) for _ in range(n+1)] dp는 알아보기쉽게하기위해 1,1부터 시작하려고 범위를 n..

이 문제는 기본적은 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 =..