4년의 학부생활은 마쳤고 취업을 위해서 할 수 있는 것들 중 하나인 coding Test 준비를 해보려고 합니다. coding Test는 어쩌면 가장 개발자다운 면접이라고 생각합니다. 또 가장 흔하게도 보이는 방식이면서도 가장 어려운 방식이기도 합니다. 무엇이든 짧은 시간에 이루어내는 것이 어렵습니다. 하지만 이 어려운 걸 이번 기회에 해보려고 합니다. 뭐든 노력해서 안되는 것은 없다.
- 자료구조 공부 및 문제 풀이
- 빅오 표기법 (big-O nation) 익히기
- 알고리즘 공부 및 문제 풀이
- 알고리즘 분석
다음과 같은 순서로 진행하려고 합니다.
1. 자료구조(Data structure) 공부 및 문제 풀이
앞으로 공부할 자료구조는 Array, String, Stack, Queue, Priority Queue, Deque, Hash 정도 입니다. 자바로 coding test를 준비할 예정이기 때문에 이론 공부 -> 자바 내장 클래스의 메소드 공부 -> 백준 문제 풀이 순서로 진행할 예정입니다.
- 이론 공부 간단 요약
Array: 배열의 구조와 특징, 탐색 및 정렬 알고리즘
String: 문자열의 처리 방법, 다양한 문자열 메소드
Stack: LIFO 구조, 다양한 활용 예시
Queue: FIFO 구조, 일반 큐와 원형 큐의 차이점
Priority Queue: 우선순위 큐의 개념과 활용
Deque: 양쪽 끝에서 삽입과 삭제가 가능한 자료구조
Hash: 해시 테이블의 원리, 충돌 해결 방식- 자바 내장 클래스 간단 요약
Array: Arrays 클래스의 메소드 (정렬, 검색 등)
String: String 클래스의 주요 메소드
Stack: Stack 클래스 (push, pop, peek 등)
Queue: Queue 인터페이스와 LinkedList 또는 ArrayDeque 구현
Priority Queue: PriorityQueue 클래스
Deque: Deque 인터페이스와 ArrayDeque 클래스
Hash: HashMap, HashSet 클래스의 메소드백준 문제 풀이의 경우에는 하루 평균 3~5문제 풀 예정입니다.
2. 빅오 표기법 (big-O nation) 익히기
알고리즘 공부하기 앞서서 빅오 표기법을 공부하려고 합니다. 해당 표기법은 알고리즘에서 가장 기초가 되는 부분으로 알고리즘의 시간 복잡도, 공간 복잡도를 나타낼 수 있는 수학적 기법입니다. 공부해야하는 이유는 효율성 평가, 최적화, 문제 해결, 면접 준비에 필요하고 필수적이기 때문입니다.
효율성 평가: 알고리즘의 성능을 평가하고 다른 알고리즘과 비교할 수 있습니다.
최적화: 성능을 개선하기 위해 어떤 부분을 최적화해야 하는지 이해할 수 있습니다.
문제 해결: 특정 문제에 적합한 알고리즘을 선택하는 데 도움을 줍니다.
면접 준비: 많은 코딩 테스트 인터뷰에서 알고리즘의 복잡도를 물어보므로 필수적인 지식입니다.기본 개념 정리 후 실제 코드를 보면서 시간 복잡도, 공간 복잡도를 구해보면서 공부할 예정입니다.
3. 알고리즘 공부 및 문제 풀이
앞으로 공부할 알고리즘에 종류에서 정렬(quick sort, merge sort), 탐색(binary search, DFS, BFS), 재귀, DP, Graph를 공부할 예정입니다. 해당 공부는 이론 공부 -> 백준 문제(실버) -> 백준 문제(골드) 순서로 진행할 예정입니다. 하루 평균 3~5문제정도 풀이할 예정입니다.
- 이론 공부 간단 요약
-
정렬 알고리즘
- 퀵 정렬: 평균 O(n log n), 분할 정복 방식.
- 병합 정렬: O(n log n), 안정적인 정렬.
-
탐색 알고리즘
- 이진 탐색: O(log n), 정렬된 배열에서 특정 원소 찾기.
- DFS (깊이 우선 탐색): 재귀적 또는 스택을 이용한 탐색.
- BFS (너비 우선 탐색): 큐를 이용하여 레벨별 탐색.
-
재귀
- 자기 자신을 호출하여 문제를 해결하는 기법.
- 기본 구조와 종료 조건 이해.
-
동적 프로그래밍 (DP)
- 문제를 더 작은 하위 문제로 나누어 해결.
- 메모이제이션 또는 타뷸레이션 기법 사용.
-
그래프
- 그래프 표현 방법 (인접 행렬, 인접 리스트).
- 그래프 탐색 (DFS, BFS)과 최단 경로 알고리즘 이해.
4. 알고리즘 분석
알고리즘 분석은 주어진 문제를 해결하기 위해 작성한 코드의 성능을 평가하는 과정입니다. 이를 통해 알고리즘의 효율성을 이해하고, 최적화할 수 있는 기회를 제공합니다. 앞으로의 알고리즘 분석은 다음과 같은 방법으로 진행할 예정입니다:
-
시간 복잡도 계산
- 코드의 실행 시간이 입력 크기에 따라 어떻게 변화하는지를 분석합니다.
- 반복문이나 재귀 호출의 횟수를 세고, Big O 표기법으로 표현합니다.
- 예를 들어, 중첩 반복문이 있는 경우 O(n2)로 표현할 수 있습니다.
-
공간 복잡도 계산
- 코드가 사용하는 메모리의 양을 분석합니다.
- 변수, 배열, 객체 등에서 사용하는 메모리의 양을 고려합니다.
- 재귀 호출로 인해 사용하는 스택 메모리를 포함하여 평가합니다.
-
다른 사람의 코드 분석
- 다른 사람의 알고리즘을 분석하여 다양한 접근 방식을 배웁니다.
- 코드의 시간 복잡도와 공간 복잡도를 이해합니다.
- 자신의 코드와 비교하여 개선할 수 있는 부분을 찾아봅니다.
이러한 단계들을 통해 알고리즘 분석의 기초를 다지고, 문제 해결 능력을 향상시키는 데 중점을 둘 것입니다. 알고리즘의 성능을 체계적으로 평가함으로써, 더 효율적인 코드 작성과 문제 해결 전략을 개발할 수 있도록 노력하겠습니다.
happy new year :)
