문제 링크 1. 아이디어 정수 삼각형에서 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제로 삼각형의 높이가 최대 500이어서 DFS를 활용할 경우 시간 초과가 발생하게 된다. 해당 문제는 다이나믹 프로그래밍을 활용하면 해결할 수 있는데 특정 위치까지 오는데 거쳐간 숫자의 합이 가장 큰 경우는 해당 위치로 올...

문제 링크 1. 아이디어 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하는 문제로 k번째 수를 구하는 command가 여러번 등장하기에 원본 배열을 직접 수정하면 안된다. 따라서 주어진 구간을 별도의 임시 배열에 복사한 후 정렬을 수행하고 k번째 수를 구하는 과정을 반복해줬다. 2. 복잡도 ...

문제 링크 1. 아이디어 중심으로부터 2m, 3m, 4m 거리의 지점에 좌석이 하나씩 있는 시소에서 시소 짝꿍의 쌍을 구하는 문제로 해시맵을 활용해서 해결했다. weight 목록에서 동일한 몸무게가 주어질 수 있으므로 몸무게를 key, 수를 value로 먼저 전처리해줬다. 시소 짝꿍의 수는 각 몸무게 단위로 계산을 해줬는데 동일한 몸무게의 사...

문제 링크 1. 아이디어 문자열 s와 t에 대해 t가 s의 애너그램이면 true, 아니면 false를 반환하는 문제다. s와 t 모두 알파벳 소문자로만 이루어져 있으므로 카운팅 배열을 활용해 s에 등장한 알파벳을 카운팅 배열에서 더해주고, t에 등장한 알파벳을 카운팅 배열에서 빼주어서 최종적으로 카운팅 배열이 모두 0으로 이루어져 있으면 애너그...

문제 링크 1. 아이디어 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 두 수의 합이 target이 되는 쌍이 딱 하나 존재하며 이때 두 수의 인덱스를 찾는 문제다. 간단한 방법으로는 2중 반복문을 통한 브루트 포스로 해결할 수 있다. 바깥쪽 반복문이 두 수 중 앞쪽 인덱스를, 안쪽 반복문이 뒤쪽 인덱스를 찾아내는 방식으...

문제 링크 1. 아이디어 의상은 종류와 이름 두 가지로 구분되며 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있다. 코니가 최소 한 개의 의상은 입어야 할 경우 코니가 입을 수 있는 서로 다른 옷의 조합의 수를 구해야 한다. 해당 문제는 경우의 수를 구하면 해결할 수 있는데 같은 이름을 가진 의상이 존재하지 않으므로 모든 의상에 대해 각...

문제 링크 1. 아이디어 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return하는 문제로 동명이인이 있을 수 있다는 점에 주의해야 한다. 해시맵을 활용해 마라톤에 참여한 선수의 이름과 수를 세주고, 완주한 선수의 이름과 수...

문제 링크 1. 아이디어 N마리의 폰켓몬 중 N/2마리를 선택할 때 가장 많은 종류의 폰켓몬을 선택하는 문제로 N마리의 폰켓몬의 종류의 수를 구하면 간단하게 해결할 수 있다. N마리의 폰켓몬의 종류의 수가 N/2 보다 크거나 같은 경우 각 종류마다 한 마리씩 N/2 종류를 선택할 수 있으며, N마리의 폰켓몬의 종류의 수가 N/2 보다 작은 경우...

문제 링크 1. 아이디어 정수 number와 n, m에 대해 number가 n의 배수이면서 m의 배수이면 1을 아니면 0을 return 하는 문제로 배수여부는 두 수를 나누었을 때 나머지가 0인지 여부로 판단할 수 있다. 2. 복잡도 시간복잡도 공간복잡도 $O(...

문제 링크 1. 아이디어 전형적인 타일링 문제로 다이나믹 프로그래밍을 활용하면 해결할 수 있다. 가로 길이가 $N$ 인 바닥을 채우는 경우는, 가로 길이가 $N - 2$ 인 바닥을 채우는 경우들에서 오른쪽 끝에 타일을 가로로 배치한 경우이거나, 가로 길이가 $N - 1$ 인 바닥을 채우는 경우들에서 오른쪽 끝에 타일을 세로로 배치한 경우 중 ...