프로그래머스 알고리즘 문제

약 2주의 시간에 걸쳐 프로그래머스 1레벨, 2레벨 문제 총 95문제를 풀고 그 느낌을 적어보고자 한다.

Lv2 치고는 쉬운 문제였는데 나는 규칙성을 파악을 못해서 풀긴 풀었는데 좀 복잡한 방식으로 풀었다. 문제의 핵심은 그림을 그려서 순서를 적다보면 나온다.

얼핏 보면 brute force 로 전체를 탐색하면 되는 쉬운 문제같아 보이지만, 효율성 체크에서 fail 하기 때문에 아예

풀긴 풀었는데 bitmask 로 풀진 않은 문제. 그렇지만 다른 사람의 풀이를 보고 비트연산의 간단함과 효율성에 감탄하고 bitmask를 이용해 부분집합을 만드는 새로운 알고리즘을 배웠다.

괄호 문제 -> 스택 사용거의 공식이라 스택을 사용해서 푸는 것 까진 성공했는데 다른 사람의 풀이를 보니 내꺼보다 훨씬 간단

다익스트라를 사용하지 않는다면 모든 테스트케이스가 풀리지 않는 문제이다.나는 DFS 를 이용하여 짧은 경로를 찾는 식으로 풀었는데 모든 테스트케이스를 통과하려면 다익스트라를 사용해야 해서 직접 공부해서 풀었다.

해쉬를 사용하면 되는 문제로, 나는 JS의 Map() 을 사용해서 풀었다.

전형적인 queue 를 사용하는 문제이다.문제 자체는 큐를 사용하면 그렇게 어렵지 않으나, 최적화는 조금 어려웠다.

문제를 도대체 어떻게 풀어야 할지 감이 안와서 풀이를 보고 푼 문제이다.

곱해서 카펫의 크기가 되는 수를 찾는, 즉 약수 관련 문제다.문제를 풀긴 했지만 좀 복잡하게 풀어서 다른 사람의 풀이로 고쳤다.

탐욕법(greedy) 문제인데, 접근법을 몰라서 풀이를 참고해서 풀었다. 핵심은 의외로 스택을 사용하는 것이다. (상상도 못함)

순열 문제이다.가능한 순서를 모두 조합한 후 탐험된 던전의 개수가 가장 큰 것을 리턴한다.

힘들었던 문제인데 결국 시간을 들여서 해결했다. 핵심은 달팽이 패턴의 규칙성을 찾아서 적용하는 것이다.

클래식한 greedy 문제이다.핵심은 내림차순 정렬을 한 후, 무거운 사람부터 태우고 무게가 남으면 가벼운 사람을 태우는 것이다.

크게 어렵진 않았지만 좌표 변환은 복습할만 한것 같아서 써본다.

규칙을 도저히 모르겠어서 그냥 재귀로 사전을 통째로 만들어서 인덱스를 반환했다.

정말 많이 고민했지만 마지막 3개의 테스트케이스가 런타임 에러가 나서 다른사람의 풀이를 참고한 문제.그런데 생각보다 간단해서 놀랐다.

이 문제는 Dynamic programming 으로 풀어야 하는 문제이다.다이나믹 프로그래밍은 사실 단어 뜻과는 다르게 "기록하는 프로그래밍"이다.

이 문제는 Dynamic programming 으로 풀어야 하는 문제이다. 즉 기록해 나가야 한다.

Lv1 중에서 가장 헤맸던 문제이다. 풀긴 풀었는데 중복되는 코드도 있고 썩 마음에 들지 않아서 다른 사람들의 풀이를 찾아봤다.

처음엔 DFS 로 풀었는데, 효율성을 통과하지 못해서 BFS 로 바꾸었다.

고민하다가 사람들의 질문에서 힌트를 얻어서 푼 문제이다.핵심은 내림차순 정렬 시 배열의 두 수를 붙여서 비교하는 것이다.

나는 실제로 합집합과 교집합을 만든다음 갯수를 셌는데 그럴 필요가 없었다.

이건 솔직히 코딩문제라기보다는 수학문제에 가까운 문제였다.좀 많은 시간이 걸렸지만 그래도 엑셀에 숫자를 적어가면서 규칙을 찾아서 해결했다.

핵심은 미리 걸리는 일수를 계산하는 것이다.

풀긴 풀었는데 비효율적인 방법으로 풀어서 다시 풀어보았다. 처음 풀었을 때는 좀 멍청하게 풀었다.

이 문제도 사실 수학문제에 가까운 문제라고 느꼈다.패턴을 파악하면 되는건데 아무리 생각해도 떠오르지가 않아서 다른 사람의 풀이를 보았다.

첫 3레벨 문제를 풀어보았다. 첫 문제부터 정말 어려웠다. 특히 내가 몰랐던 backtracking 알고리즘을 새로 배워야 풀 수 있는 문제였다.