문제 15961 - 회전 초밥 접근 투 포인터 문제이다. start, end 두 개의 변수를 이용하여 배열을 한 바퀴 돌면 된다. start ~ end 사이에 있는 초밥을 먹는다고 생각하면 된다. start가 0부터 시작해서 n-1까지 돌면 모든 경우의 수를 확인한 것이다. 안겹치는 초밥을 카운팅할 때 바로바로 확인하기 위해서 인덱...

문제 1520 - 내리막 길 접근 DFS와 DP를 이용하여 해결했다. 기본 아이디어는 재귀를 이용한 DFS이다. 여기까진 DFS에 대한 지식만 있다면 쉽게 생각해내고 구현할 수 있다. 0, 0 에서 시작해서 상하좌우 가능한 경로를 재귀적으로 수행하며, 최종 목적지에 도착하면 1을 리턴한다. 하지만 이 경우 board의 크기가 크기 ...

문제 16234 - 인구 이동 접근 어제의 아기 상어와 마찬가지로 BFS와 시뮬레이션이 결합된 문제이다. BFS 기본문제 중에 인접한 영역의 크기를 구하는 문제를 알고 있다면 생각보다 쉽게 접근할 수 있다. 문제에서 주어지는 l, r 조건에 맞는 인접 영역을 구하면 된다. 이 때 영역의 크기뿐 아니라, 영역에 속하는 좌표들도 구해와서...

문제 16236 - 아기 상어 접근 BFS로 접근하면 되는데, 조건이 제법 있는 시뮬레이션 문제이다. 다행히 시간제한은 넉넉해서 전수검사로 BFS를 돌렸다. 프로세스는 다음과 같다. 현재 위치에서 BFS를 수행한다. 잡아먹을 수 있는 물고기 중에 가장 가까운(같다면 문제에서 제시한 조건) 물고기를 찾는다. 잡아먹고 해당 ...

문제 9251 - LCS 접근 DP 문제이다. 문자열의 길이를 하나씩 늘려주면서 DP table을 채워나가면 된다. 문제에 주어진 예시로 확인해보자. S1 = ACAYKP S2 = CAPCAK 일 때, s1 = A s2 = C 이 때 LCS는 0. s1 = A s2 = CA 이 때 LCS는 1. …. s1 = A s2 = C...

문제 2470 - 두 용액 접근 정렬과 투 포인터를 이용하여 풀었다. 주어진 배열을 정렬한 후, 시작과 끝점을 잡고 하나씩 옮기며 비교해나갔다. 가장 앞을 start, 뒤를 end라고 했을 때, 둘 중에 어떤 것을 옮길지 정해야 했다. start+1과 end-1에 있는 수의 절대값을 비교하여 더 큰 쪽으로 이동해주었다. 예를 들어 ...

문제 1976 - 여행 가자 접근 BFS를 이용하는 문제이다. 조건은 생각보다 쉽다. 여행하고자하는 도시 중 하나를 정해서 BFS를 수행하고 여행하고자하는 도시들에 모두 방문했는지 체크해주면 된다. 문제에서 입력이 인접행렬로 주어져서, 그냥 인접행렬을 사용했다. 코드 파이썬 코드 from collections import...

문제 21761 - 초직사각형 접근 그리디 알고리즘이다. 4개 숫자의 곱을 최대화하는게 목적이다. 이 때 주어지는 카드 중에 K개만을 선택해야 한다. 결국 주어진 카드 중에 부피를 최대화할 수 있는 카드를 선택해야 한다. 이를 위해서 주어지는 카드들을 문자 A,B,C,D에 따라 나누고, 각 그룹별로 정렬해준다. 각 문자 그룹에서 가장 ...

문제 21756 - 지우개 접근 하나씩 확인하는 방식을 확인했다. 큐를 이용해도 될것 같은데, 그냥 간단하게 배열 두개를 이용해서 옮겨다녔다. 기준 배열에서 짝수번째 수들만 새로운 배열에 담아준다. 새로운 배열을 기준배열로 삼고 다시 이를 반복한다. 수가 한개 남을 때까지. 코드 파이썬 코드 n = int(input()) a...

문제 1427 - 소트인사이드 접근 간단한 문제이다. 입력 받은 숫자를 한 글자씩 분리한 다음 정렬해주면 된다. 코드 파이썬 코드 n = list(str(int(input()))) n.sort(reverse=True) print(int(''.join(n)))