클라우드 낚시꾼

코딩 테스트란 무엇인가 - 코딩 테스트는 누가 실시하는가? 아마 필자를 포함한 개발자 꿈나무들이 "어디에서 일하고 싶어요?"라는 질문을 들으면, 대부분 "네카라쿠배요!"라고 답할 것이다. 보통의 기업들은 스펙, 면접 등으로 유능한 인재를 선별한다. 하지만, IT 대기업은 조금은 생소한 방식으로 유능한 인재를 선별하는데 그것이 바로 알고리즘 코딩 테스트다. - 코딩 테스트를 왜 실시할까? 코딩 테스트는 여러 가지 환경, 변수를 다 배제하고 문제를 해결하는 능력 자체를 평가하기 위해 실시한다. 기업 입장에서도 실무 환경에서 직접 프로그램을 개발하는 능력을 평가하고 싶을 것이다. 하지만, 그 환경이 회사마다, 사람마다 천차 만별이기 때문에 정확한 개발 능력을 평가하기 쉽지 않다. 코딩 테스트 공부법 코딩 테스..

시간 복잡도의 분류 위의 모토에 따르면, 시간 복잡도는 아래와 같이 3가지로 분류된다. 1. 최악 경우 시간 복잡도(worst case) 모든 입력에 대해서 기본 연산이 수행되는 최대 횟수 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해서 기본 연산이 수행되는 최소 횟수 3. 평균 경우 시간 복잡도(average case) 모든 입력에 대해서 기본 연산이 수행되는 평균 횟수 예제로 순차 탐색 알고리즘 각 시간 복잡도를 구해보자. 1. 최악 경우시간 복잡도(worst case) 모든 입력에 대해 가장 마지막에 탐색을 성공하는 N 2. 최선 경우 시간 복잡도(best case) 모든 입력에 대해 가장 첫 번째에 탐색을 성공하는 1 3. 평균 경우 시간 복잡도(average case) 평균 ..

대표적인 점근적 표기 대표적인 점근적 표기는 위와 같다. 사실, 말로는 이해하기 너무 어렵다. 점근적 표기에 대해서 더 알아보자. O(Big-O)-표기 (최악의 시간 복잡도) - O(Big-O) 표기의 정의 모든 n >= n0에 대해서 cg(n) >= f(n)인 양의 상수 n0와 c가 존재한다면, f(n) = O(g(n))이다. - O(Big-O) 표기의 의미 n0와 같거나 큰 모든 n에 대해서 f(n)은 cg(n)보다 크지 않다는 의미이다. 즉, f(n)은 cg(n)에 절대 미치지 못하며, 이때 g(n)을 f(n)의 상한이라고 한다. - f(n) = O(g(n))의 의미 n이 증가함에 따라 g(n)은 f(n)이 절대 미치지 못하는 점근적 상한이다. - Big-O 표기법을 찾는 방법 다항식에서 계수를 제..

BFS를 쉽게 말하자면? 위 그래프의 시작 노드는 1 이고, 숫자가 낮은 노드부터 탐색한다고 가정하자. 이 가정 아래, 그래프를 가장 가까운 노드부터 탐색하면 1 -> 2 -> 3 -> 5 -> 4 -> 6 라는 결과를 얻을 수 있다. 이것이 BFS이다. BFS의 가장 주요한 모토는 "그래프를 가까운 노드부터 탐색하자." 라는 것을 잊지 말자! BFS 알고리즘 먼저, BFS를 구현하기 위해서는 FIFO 구조인 큐(Queue) 자료구조를 사용해야 한다. 인접한 노드를 반복적으로 큐에 넣게되면, 자연스럽게 먼저 들어온 것이 먼저 나가게 되어 가까운 노드부터 탐색을 진행하게 된다. 알고리즘의 정확한 동작방식은 아래와 같다. 1) 탐색 시작 노드를 Queue에 Enqueue 하고 방문 처리한다. 2) Front..