본문 바로가기

알고리즘

[코딩인터뷰] 알고리즘 시간 복잡도 분석 방법 알고리즘 시간 복잡도 분석 방법 코딩 테스트는 시간 제한이 있습니다. 이미 구현한 전략이 제한된 실행 시간 안에 풀 수 없다는걸 깨닫고 다른 전략을 시도할 시간은 없습니다. 따라서 문제를 어떻게 풀까 고민하다 떠올린 아이디어가 실행 시간 안에 해결할 수 있는지를 가늠할 줄 알아야, 잘못된 구현을 하는 불상사를 피할 수 있습니다. 내가 구현할 알고리즘 전략이 주어진 실행 시간 안에 동작할 수 있는지를 간단하게라도 가늠할 줄 알아야 합니다. 일반적으로 10의 8승, 1억번 이상 의 연산 시간이 필요한 전략은 코딩 테스트 문제에 일반적으로 주어지는 '1초' 라는 제한된 실행 시간 안에 해결할 수 없습니다. 특히나 Python 는 타 언어에 비해 실행 시간이 더 걸리는 편이라 제한된 실행시간 안에..
[코딩인터뷰] 깊이 우선 탐색 Depth first search (DFS) 깊이 우선 탐색 Depth first search (DFS) 깊이 우선 탐색 (DFS) 는 너비 우선 탐색과 함께 코딩 테스트 출제 빈도가 높은 전략입니다. DFS 는 그래프에서 A 노드를 방문하고, 방문한 A 노드와 연결된 B 노드를 방문하고, 방문한 B 노드와 연결된 C 노드를 방문하는 과정을 반복해서 그래프의 모든 노드를 방문합니다. 너비 우선 탐색과 달리 굉장히 직관적인 탐색 방법입니다. DFS 을 사용하여 그래프를 탐색할 때 무한 반복을 조심해야 합니다. 만약 그래프에 사이클이 있다면 무한히 탐색을 반복하게 됩니다. 따라서 이미 방문한 노드를 기록하고 탐색할 때 방문했는지 안했는지를 확인해야 무한 반복을 피할 수 있습니다. DFS 전략으로 푸는 대표적인 문제 유형 노드 사이 간 거리가 다른 최단..
[코딩인터뷰] 너비 우선 탐색 Breadth first search (BFS) 너비 우선 탐색 Breadth first search (BFS) 너비 우선 탐색 (BFS) 는 코딩 테스트 출제 빈도가 높은 전략입니다. 그래서 반드시 알고 있어야 하고 문제에 활용 가능할지 판단할 수 있어야 합니다. BFS 는 이름 그대로 너비를 우선하여 탐색하는 전략입니다. 그래프에서 각 노드를 방문하면서 방문한 노드와 연결된 노드들을 큐에 추가하고 빼면서 각 노드를 한 번씩 탐색하게 됩니다. 각 탐색을 진행하면서 문제가 요구하는 정답 찾아 가게 됩니다. BFS 는 전략 특성상 '노드 방문 여부'를 체크하지 않으면 무한 반복에 빠질 위험이 있습니다. 따라서 BFS 로 문제를 풀 때는 노드의 방문 여부를 체크하는 코드가 반드시 필요합니다. BFS 전략으로 푸는 대표적인 문제 유형 노드 사..
[코딩인터뷰] 백트래킹 Back tracking 백트래킹 Back tracking 백트래킹 (Back tracking)은 문제 해결 전략 중 하나로, 가능한 모든 경우의 수를 탐색하는 전략인 브루트 포스(Brute force) 전략에서 특정 조건을 만족하지 못하는 경우의 수들을 탐색 범위에서 제외시키며 탐색하는 전략입니다. 브루트 포스 전략은 모든 경우의 수를 전부 탐색하지만 백트래킹 전략은 특정 조건을 만족하지 못하는 경우의 수를 탐색에서 제외하기 때문에 브루트 포스 전략보다 탐색 효율이 좋습니다. 백트래킹 전략은 재귀적으로 조건을 만족하는지 검토하면서 정답을 완성합니다. 정답을 완성하는 과정 중 조건을 만족하지 못하는 경우의 수와 관련된 경우의 수들을 탐색 범위에서 제외시킵니다. 첫 정답이 완성되면 전 상태로 되돌리고 다른 가능한 경우의 수를 탐색..

티스토리툴바