S2U3 코딩 테스트 준비 회고
[의사코드(pseudocode)]
🎰 문제를 해결할 때 대충 생각하고 해결하지 않도록 해야한다. 잡아둔 문제 해결의 틀을 자연어로 먼저 작성해놓으면 실제로 구현하기가 수월해진다. 그것이 의사코드이다. 자연어 자체로, 혹은 if / while등 자바 문법을 섞어가며 작성해도 된다.
원래도 주석으로 틀을 잡아두고 작업을 하긴 했지만, 조금 더 올바른 의사코드를 작성할 수 있게 되었다. 최대한 로직의 틀을 많이 잡아두고, 조건도 설정해두고 그걸 구현하는 식으로 코드를 작성하게 되었다.
[시간복잡도(Time Complexity)]
🎰 연산 횟수의 변경에 따라 소요 시간이 얼마나 증가하는지를 시간복잡도로 표현한다. 시간복잡도의 표기법에는 세 가지가 있다. 빅오(최악의 경우), 빅오메가(최선), 빅세타(평균)이다. 프로그램 실행 시 소요되는 최악의 경우를 고려한다면 그에 맞는 대응이 가능하기 때문에 주로 빅오 표기법이 사용된다.
여러가지 시간복잡도가 있지만 크게 다섯가지를 늘어놓자면, O(1), O(n), O(log n), O(n²), O(2^n).
예) O(1) 배열(arr)과 index(n)을 입력받아 arr[n]을 리턴하는 경우
O(n) for문과 같은 반복문
O(log n) BST 탐색
O(n^2) 이중 for문
O(2^n) 피보나치 구현
얼마 전 프로그래머스에서 문제를 풀다가 효율성 기준을 통과하지 못 하는 일이 있었다. 처음엔 리스트를 이용해서 풀었더니 시간복잡도가 O(n^2)까지 늘어났다. 그런데 자료구조를 HashMap으로 바꾸어 풀었더니 최대 시간복잡도가 O(n)까지 줄어들었다. 같은 답이 나와도 성능이 달라질 수 있다는 걸 직접 확인해보니 확 와닿았다. 그 후로 꼼꼼히는 아니어도 대충 데이터 크기를 확인하는 습관이 생겨...가고있다. 자료구조에 따라 더 빠르게 처리를 할 수 있다니 신기하다.
2022.11.26 - [공부기록/JAVA] - 코드가 짧다고 효율이 좋은 것은 아니다.
코드가 짧다고 효율이 좋은 것은 아니다.
프로그래머스 42576번 [완주하지 못한 선수] 문제를 풀었다. 두 개의 배열이 주어지는데, participant 배열에는 참가자 전원이, completion 배열에는 완주한 인원이 들어있다. 이 중 완주하지 못한 사람
ddorimeo.tistory.com
[탐욕(Greedy)]
🎰 Greedy는 현재 상황에서 최적의 답안을 찾고, 조건에 부합하는 지 검사한 후 문제가 해결될 때까지 과정을 반복한다. 탐욕 알고리즘은 항상 최적의 답안을 주지는 못 한다. 주어진 상황만을 고려해서 최적을 찾는 과정을 반복해가며 문제의 최적 해를 찾는 방식이기 때문에, 다른 방법이 더욱 최적일 수 있다. 어떤 경우에도 최적인 방법을 찾는다면 동적 계획법을 사용하는 것이 좋다.
탐욕 알고리즘의 대표 격인 동전 문제를 풀었는데, 동전 단위가 아닌 수로 실행을 했을 때 최적의 해가 구해지지 않았다. 그 때 들었던 생각이 탐욕 알고리즘은 당장 주어진 상황에서만 최적의 답을 찾는 건데 이런 경우에는 어떻게 하지?라는 것이였다. 그 해가 최적인지를 확인하고 아니라면 다시 다른 방법을 선택해야 하는 경우에는 동적 계획법을 사용해야 하는구나...라고 지금은 생각해본다. 어떤 제한이 있는 문제에 그리디가 어울리는 것 같다. 이부분은 조금 더... 살펴봐야겠다. DP 문제도 풀어봤는데 알고리즘은 정말이지~~~ 아직 적용하는 게 감이 잘 안 온다.
[implementation - Simulation]
🎰 내가 생각한 로직을 빠르고 정확하게 구현해내기. 문법을 정확히 알아야 하고, 문제 조건에 맞는 코드를 정확히 구현해야한다. 복잡한 과정과 조건 사항을 빠트리지 않고 구현하는 것이 시뮬레이션 유형이다.
시뮬레이션 유형의 문제(?)는 풀어보지 않았지만 코드가 길어지는 경우에 정확하고 빠른 코드 작성이 어려운 경우가 있다고 한다. 문제 뿐만 아니라 그냥 API를 작성할 때도 내가 생각해둔 로직을 정확하고 간결하게 작성하는 게 정말 어려웠는데... 역시 많이 연습해보는 게 중요하겠다!
[완전 탐색(Brute-Force Algorithm)]
🎰 가능한 모든 경우를 탐색해보아야 하는 경우 사용한다. 단독 사용이라기 보다는 방법론이기 때문에, 어떠한 문제를 해결하기 위해 완전 탐색 기법을 사용하는 것이다. 주로 순차검색, 선택정렬, 버블정렬, BFS, DFS, DP에 활용된다. 문제가 복잡하면 매우 비효율적이므로 너무 큰 규모의 문제에는 사용하지 않아야한다. 정확도를 조금 희생하더라도 더욱 효율적인 알고리즘을 사용한다. 아 순열/조합에도 완전탐색이 활용된다.
"알고리즘 사용"이라는 건 참 헷갈린다. 어떤 알고리즘은 방법론이고 어떤 알고리즘은 활용하는 거고🫠 처음엔 완전 탐색이라는 건 따로이고 BFS는 또 따로고 이렇게 된 줄 알았는데 완전 탐색을 활용한 것이 위에 써둔 활용기법들이였다. 이런 애매한ㅠㅠㅠ 내가 아직 문제 유형에 따른 풀이방법을 잘 익히지 못 해서인 것 같다. 이 글도 나중에 읽었을 때는 과거의 나를 귀여워하면서 웃음이 나오기를,,ㅎㅎ
[이진 탐색(Binary Search Algorithm)]
🎰 이진 탐색 알고리즘은 경우의 수를 절반으로 줄여가며 << | >> 데이터를 탐색한다. 데이터가 정렬된 상태에서 사용할 수 있다. 이진탐색 트리(BST)와 헷갈릴 수 있는데, BST는 정렬된 트리구조이고 알고리즘은 해결 방법이다! 배열에만 구현할 수 있고, 정렬된 상태에서만 사용 가능하기 때문에 정렬되어있지 않다면 정렬 후 사용하는 것은 효율이 높지 않다.
이진 탐색 트리는 자료구조 때도 정리를 해보았어서 많이 이해가 된 상태였다. 비슷한 느낌으로 반절을 나누어 더 큰지 작은지를 비교해서 범위를 줄여가고 줄여간다니 데이터가 커질수록 효율이 좋을 것 같다. 하지만 아직 이진탐색을 사용하는 문제는 풀어보지 않은 것 같아서 구현에는 감이 오지 않는다. 얼른 프로그래머스 레벨을 높여서 더 많은 알고리즘 문제를 접해보고싶다!
[Algorithm with Math (순열 / 조합)]
🎰 순열은 순서에 상관 없이 선택한 것이지만, 조합은 순서에 상관이 있다. 예를 들어 순열의 개념으로 보면 {1,2} 와 {2,1}은 다르지만 조합은 같다고 본다. 재귀를 사용한 DFS탐색을 통해 구현하는 것이 가장 안정적이다. 한 경로를 끝까지 탐색하고, 다시 나와서 다른 경로, 나와서 다른 경로 ... 다만 조합은 요소가 같고 순서가 달라도 같은 것으로 취급하므로, 방문 처리를 해주면서 처리해야한다.
순열과 조합은 정말 예전에 배운 거라 완전히 잊고 있었는데... 알고보니 얼마 전에 프로그래머스에서 푼 삼총사 문제가 순열과 조합 문제였다는 사실..!!! 나도 모르게 문제를 풀었다. 물론 3개만 뽑으면 되는 거라서 그냥 아무 생각 없이 3중 반복문을 사용하긴 했지만.. 무튼 재귀를 통해서 순열/조합을 구하는 것은 흐름을 이해하기 전에는 너무너무 어려웠는데 그래도 몇 번 반복해서 보니까 흐름이 이해되었다. 그래도 여전히 어려운 건 사실이다ㅠ 그래도 DFS 구현에 대해 좀 더 깊은 이해를 할 수 있어서 기쁘다.
🟠 Unit 3. 코딩 테스트 준비를 마치고!
너무너무너무너무너무 어려웠던 유닛🤯 알고리즘을 활용하는 건 하루아침에 되지 않는 것을 알기 때문에 좌절스럽진 않다. 그래도 이전보다는 여러 문제를 접해가고 있으니까!! 그래도 문제를 풀면서 감조차 오지 않는 건 좀 좌절스럽ㄷㅏ.. 우선 문제점은 1. 문제를 보면서 어떤 알고리즘을 활용해야 될 지 잘 모르겠다는 것 2. 어떤 걸 활용할 지 알아도 쉽사리 구현을 하지 못 하겠는 점이다. 많이 접해보는 것이 정답인 걸 알고 있지만😵💫 자료구조 알고리즘 똑똑이가 되는 것은 역시 쉬운 길이 아니구나. 유형에 맞는 구현을 어떠한 틀에 맞춰서 진행하는 게 정답인가 싶긴 하다. 엔지니어님도 그렇게 힌트를 주셨다. 당장 이걸 못 해서 마음이 조급하거나 하진 않지만, 까먹지 않게 문제를 자주 그리고 많이 풀어보고 나중에 시간이 날 때 책도 같이 읽으면서 준비를 해야겠다고 생각했다. 정말 며칠 안 보면 풀었던 문제도 다 까먹어버릴 것 같은 느낌이 호악 온다ㅎㅎ 여느때와 다름없이 꾸준히 해나가자는 생각을 하면서,,,,,, 코딩 테스트 준비 회고 끝