개요
작년 11월 말 2024 KAKAO WINTER INTERNSHIP를 지원하고 코딩 테스트를 보았었습니다. 비록 통과는 못했지만 5시간 동안 문제해결을 위해서 여러 가설을 세우면서 많은 노력을 들였던 탓에 많은 여운이 남았습니다.
몇 주전 프로그래머스에서 코딩 테스트 문제가 공개되어서 각 문제마다 어느 알고리즘이 중점으로 사용되었는지 확인하기 위하여 다시 한번 풀어보았습니다.
문제해결 및 후기
- 1번 문제는 생략하겠습니다.
- 언어는 javascript를 사용하였습니다.
2번
사용한 알고리즘 및 자료구조 : 그래프 / BFS와 같은 그래프 탐색
문제를 해결하기 위하여 크게 다음과 같이 나뉘었습니다.
- 그래프 구하기
- 루트 노드
- 각 모양 그래프 갯수 구하기 (도넛, 막대, 8자)
그래프를 구할 때 저 같은 경우 방향 그래프로 값이 주어졌으므로 들어가는 노드의 정보와 나가는 노드의 정보를 담는 클래스를 하나 만들어서 그래프의 정보를 지정하였습니다.
위의 그래프 정보를 이용하여 문제 내에서 주어지는 그래프 중 루트 노드의 특징과 연계하여 루트 노드가 무엇인지 알아내었습니다.
그 다음 루트 노드를 제외한 모든 노드를 BFS와 같은 그래프 탐색을 이용하여 문제에서 제시된 각 모양의 그래프의 특징을 잘 활용하여 각 모양 그래프의 갯수를 구해놓았습니다.
이 때 주의할 점은 시험 중 재귀로 그래프 탐색을 구할 경우 채점 시 특정한 문제에서 컴파일 에러가 발생하기 때문에 그래프 탐색을 구현 할 때 스택 및 큐 등 자료구조를 이용하여 구현해야합니다.
아마 컴파일 에러가 발생하는 이유는 노드의 갯수가 1,000,000이므로 재귀로 구현 할 시 메모리 초과로 인한 컴파일 에러가 발생한걸로 생각이 듭니다.
3번
사용한 알고리즘 및 자료구조 : 순열 및 조합 / 완전 탐색 / 투포인터
문제를 해결하기 위하여 크게 다음과 같이 나뉘었습니다.
- 조합을 이용하여 고를 수 있는 주사위를 고르기
- 고른 주사위의 승수를 구해서 그 중 최고 승수 찾기
우선 순열 조합 알고리즘을 이용하여 A가 n개 중 n / 2개를 고를 수 있는 주사위를 주사위의 배열의 index로 나타내어 나열하였습니다.
그러고 나서 고른 주사위와 고르지 않은 주사위를 매개로 받아서 모든 주사위를 굴려서 나올 수 있는 합의 수를 완전 탐색을 이용하여 배열로 담아주었습니다.
그 이후 완전 탐색으로 담은 후의 승수를 알기 위해서 해당 배열을 오름차순으로 정렬을 해주었습니다.
그 다음 투포인터를 이용해서 각 주사위마다 승수를 구해 많은 승수를 구해주면 됩니다. 위를 정확히 구하기 위해 이 문제에서 많은 시간 및 노력을 쏟은 것 같습니다. 여기서 중요한 점은 나와 상대 모든 승수를 구하는 것이 아닌 나의 승수만 포커싱해서 구했습니다.
승수를 구할 때 다음과 같은 경우의 수를 고려하였습니다.
- 내가 이길 때
- 상대가 이길 때
- 둘 다 비길 때
4번
주기고 싶은 4번 문제와의 10선
해결할려고 시도했던 알고리즘 및 자료구조 : DP / 이분 탐색 / 배열 / 해쉬
위의 문제 중 가장 어려웠다고 생각했던 문제였습니다. 이 포스팅을 쓴 현재 75%만 맞추었기 때문에 지금까지 시도한 방법만 정리해보겠습니다.
첫번째 시도
초기에 주어지는 카드를 제외하고 코인의 수 만큼 카드를 고르는 방식을 착안해서 해당 카드에서 짝이 있는 인텍스를 미리 구한 다음 DP를 이용하여 각 라운드마다 최대로 구할 수 있는 쌍의 갯수를 구해보았습니다.
그러나 어느 특정한 부분에서 오답이 나왔었고 다시 한번 생각해보았습니다.
두번째 시도
카카오 블로그에서 나온 풀이를 참고하여 각 코인마다 소비할 수 있는 카드를 분류한 뒤 각 라운드 마다 코인의 갯수가 주어지면 최대 몇 쌍을 지닐 수 있는지 확인해보는 방법으로 변경해 보았습니다.
위의 방법으로 제출한 결과 75% 정도 정답률이 나왔습니다.
5번
사용한 알고리즘 및 자료구조 : DP
평소에 DP 문제를 많이 풀었었다면 쉬웠을 문제라고 생각이 듭니다.
삼각형이 1개일 때와 0개일 경우의 수를 미리 넣은 다음 삼각형이 홀수일 경우과 짝수일 경우의 갯수를 생각하고 특히 짝수일 경우 윗 삼각형이 없는 경우과 있는 경우의 수로 다시 나뉘어서 경우의 갯수를 생각하였습니다.
- 홀수
- 짝수
- 윗 삼각형이 있는 경우
- 윗 삼각형이 없는 경우
위의 경우의 수의 규칙을 파악하여 점화식으로 변환시켜 삼각형이 2n + 1 일 때의 경우의 수를 구하였습니다.
