Kim-Baek 개발자 이야기

IT기업의 신입 채용을 위해 코딩 테스트 준비를 정말 많이 했었다. 인적성, NCS와 같은 필기테스트 공부는 거의 하지 않고 오로지 코딩테스트 알고리즘 공부만 했던 기억이 난다. 대학생때는 백준 온라인 저지 사이트의 알고리즘 문제를 풀었었다. 알고리즘 문제가 익숙하지 않던 대학생에게 한글로 된 문제와 사이트가 알고리즘 문제의 거부감을 많이 없애줬던 것 같다. 문제를 풀어볼수록 잘 하고 있나에 대한 의구심과 실력이 늘고있다는 느낌을 못받았었던 것 같다. 하지만 코딩테스트 시험을 보거나 알고리즘 테스트를 하다보면, 많이 성장했던 것을 느꼈던 것 같다. 대학생때는 C++로 알고리즘 문제를 풀었었는데, C++ 언어의 특별한 자신감이 있다거나 잘 아는 것은 아니였지만 그저 알고리즘 문제를 위해서 C++를 공부하고..

알고리즘 문제에서 정렬(Sort)는 중요한 기술이다. 여러가지 정렬 알고리즘이 있지만 기본적인 것 부터 하나하나 알아보자. 선택 정렬 (Selection Sort) 단순한 정렬 알고리즘 중 하나이다. 배열의 첫 번째 원소에서 시작하여 배열 전체를 훓으면서 작은(큰) 값을 찾아 첫 번째 원소와 바꿔준다. 이 작업을 (배열의 길이 - 1 ) 만큼 진행한다. 선택 정렬은 Best, Average, Worst Case 모두 O(N^2) 의 효율이다 - 원소를 바꾸는 횟수가 최대 n -1 이다. 즉 원소를 바꾸는 과정에서 많은 비용이 드는 경우에 효율적일 수 있다. - 선택 정렬은 다른 알고리즘에 비해 효율(performance) 가 좋지 않다. - stable을 만족하지 않는다. #include using na..

BFS는 너비우선탐색 이라고 블리는 Graph 알고리즘 중 하나이다. - BFS 는 일반적으로 Queue를 이용해 구현 - 시작 정점과 인접한 모든 정점을 방문하는 방법 - 얻어진 해가 최단 경로가 된다는 것을 보장 - 경로가 매우 길 경우에는 많은 저장 Memory 가 필요 C++를 이용해 BFS를 구현 #include #include #include using namespace std; vector* vertex; bool* checked; void bfs(int st); int main() { int n, m, s; int from, to; cin >> n >> m >> s; vertex = new vector[n + 1]; checked = new bool[n + 1]; for (int i = 0..