문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17683? 2018 카카오 블라인드 3차 코딩 테스트에서 나왔던 문제단순 구현 문제라고 생각되는데, 생각보다 구현해야 하는 함수 부분이 많아서 잘 정리하는 게 중요했다. 또한 예외 케이스가 많은 문제여서 테스트 케이스를 잘 짜는 것이 중요했다. 문제 핵심 및 풀이 멜로디와 일치하는 곡 찾기의 문제 멜로디(m)가 곡(musicInfo) 안에 있는지 확인하는 과정은, 일반적으로는 문자열 비교로 하면 된다. 하지만 입출력 예시 3번에서 볼 수 있듯이 #이 문제가 된다. 일반적인 문자열 비교로 찾을 때는, m = "ABC" , musicInfo = "ABC#" 일 때, 조건 일치로 판단한다. 그래..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/150369? 2023년 카카오 블라인드에서 나온 따끈따끈한 최신 문제 이 문제를 실제 테스트로 봤으면 어땠을까? 문제 로직은 크게 어렵다고 생각 들진 않았지만 이상하게 푸는데 오래 걸렸다. 문제 핵심 및 풀이 제한사항 부분을 보면 집(n)의 개수가 최대 100,000개이고, cap은 50까지밖에 되지 않는다. deliveries와 pickups의 개수 또한 n과 같다. 해당 문제에서는 cap이 50밖에 되지 않는 것은 오히려 반복 횟수를 늘린다. 왜냐하면 50번밖에 담지 못하기 때문에 여러 번 왔다갔다 해야한다.. 그래서 완전탐색으로 해당 문제를 풀기에는 비효율적으로 보이고, 실제로 완전 ..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/77486 2021 Dev-Maching에서 나온 문제 카카오 기출문제만 풀다와서 그런진 모르겠는데, Level 3 치곤 쉽게 풀었다. 만약 카카오 코딩 테스트에서 나왔다면, Level 2 쯤 아니었을까? 문제 핵심 및 풀이 그림에서 보면 알 수 있듯이, 트리 구조가 형성되는 것을 알 수 있다. 그리고 해당 문제에서는 자신을 추천한 사람을 아는 것이 중요한데, parent [i] = k : i를 추천한 사람이 k이다. 이런 식으로 정의하도록 한다. 사람 이름 문자열을 매핑 여기서 생각해야 할 것은 트리의 각 노드들이 사람이름(문자열)이라는 점이다. 그래서 parent의 인덱스로 문자열을 사용..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42890? 카카오 코딩 테스트 문제 위주로 풀고 있는데, 어째 Level 2에 나오는 문제는 왜 전부 유형이 비슷한 거 같지? 문제 핵심 및 풀이 제한 사항 부분에서 문제의 유형을 알 수 있다. 고를 수 있는 선택지인 column이 최대 8개, 판별해야 할 row는 최대 20밖에 되지 않는다. 탐색 범위가 엄청 작은 것을 알 수 있어서, 이 문제는 완전 탐색으로 충분히 풀 수 있다는 것을 알 수 있다. 키 쌍이 될 수 있는 경우의 수 어떤 속성(column)의 조합이 후보키가 될 수 있는지는 속성 조합을 만들어보고, 직접 모든 row와 비교해 보는 수밖에 없다. 그렇기 때문에 결국엔 조합이..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72411 2021 카카오 블라인드 코딩 테스트에서 나온 문제. 자료구조 Map을 잘 알아야 풀 수 있는 문제 같다. Map을 사용하지 않고 다른 건 잘 모르겠다. 문제 핵심 및 풀이 메뉴(orders)의 개수가 최대 20개, 메뉴 조합(course)의 가짓수는 최대 10가지. 문제 풀이에 핵심이 되는 조합과 개수가 엄청 작기 때문에, 해당 문제는 완전 탐색으로 풀 수 있다. 여기서 문제가 되는 것은 메뉴 조합이 구성되는 방식이 "AB", "ABC" , "CDE", "A" 이렇게 정수가 아닌 문자열이기 때문에, 인덱스로 문자열을 사용하기 위해 자료구조 Map을 사용해야 한다. orders에서..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/17679 카카오 블라인드 코딩테스트 2018년도 문제. 코딩테스트 리뷰를 보니까 난이도 상 문제였다. 문제 핵심 및 풀이 해당 문제는 제한사항에서 완전탐색으로 가능하다는 것을 인지해야 한다. 핵심적인 구현은 2가지가 있다. 1. 2x2에 연결되어 있는 다른 2x2 블록이 같이 터질 수 있도록 하는 것. 2. 블록이 터진 후 비어있는 공간에 위에 있는 블록들이 떨어지는 것. 2x2 블록들이 연쇄적으로 사라지게 하기 일단 2x2 조건을 만족하는 블록들을 찾아내는 것은 쉽다. 무조건 2x2 고정이기 때문에 현재 좌표를 (i, j)라고 한다면 ( i , j ) == ( i , j+1 ) == ( ..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=cpp 카카오 기출문제 중 Level 2 난이도, 그림만 많지 문제를 이해하기에는 어렵지 않다. X는 칸막이로 치고, 그냥 5x5 맵에 P와 P 사이에 맨해튼 거리를 계산하면 된다. 문제 핵심 및 풀이 키포인트는 5 x 5 맵이 5개 있다는 점. 탐색 범위가 작아 완전 탐색이든 뭐든 시간적인 제약은 없다. 또한 핵심 아이디어는 이 문제가 그래프 탐색을 할 수 있다는 것. 그중에서 편한 방법은 BFS인데, 왜냐하면 BFS를 통해 최단거리를 쉽게 구할 수 있기 때문이다. 이 문제를 왜 BFS로 풀 수 있을까? 맨해튼 거리를 계산하는 것이기 때문이다. 두 점 A와 B의 ..
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72412?language=cpp 카카오 코딩테스트에 나온 문제. 문제 이해 자체는 어렵지 않다. 문제 핵심 및 풀이 1. 효율성 검사도 하기 때문에 시간복잡도가 중요하다. info의 크기가 50,000까지이고, query의 크기는 100,000까지이다. 이를 O(N)으로 계산한다고 했을 때, 5* 10^5 * 10^4 = 5억 정도라서 O(N)으로 탐색하기에는 아슬아슬하다. 그래서 최적화를 해야 하는 문제이다. 실제로 O(N)으로 푸니까 시간초과가 나온다. O(N)으로 풀었을 때의 시간 복잡도가 얼마인지 모르겠긴 하다. 2. 문자열 분리 해당 문제에서 info는 띄어쓰기를 통해 구분되어 있..