1. 개요코딩 테스트 문제를 푸는데 DFS에 관련한 문제들이 나왔다. 처음에는 DFS와 관련된 문제인지 모르기도 했고, 시간이 오래걸릴 것 같아 재귀 방식으로 구현을 하기가 싫어서 다른 방식을 고민하다가 결국에는 재귀 방식으로 해결하게 되었는데, 생각보다 측정된 시간이 그렇게 오래 걸리지도 않았고 오히려 다른 방식으로 하던 것의 시간이 더 오래 걸린 것을 보고 재귀 방식도 쓰기 나름이라는 생각이 들었고, 대표적으로 재귀 방식으로 구현하는 알고리즘인 DFS에 대해 좀 더 자세히 알아보게 되었다.2. DFSDFS란?그래프나 트리에서 시작 노드에서 깊이를 우선으로 하여 자식 노드들을 순서대로 탐색하는 알고리즘현재 노드에서 시작해 자식 노드로 계속해서 파고들며 탐색(깊이 우선) ㅡ> 더 이상 파고들 노드가 없다..

1. 개요매일 코딩 테스트 문제를 푸는데 최근 푸는 문제들 중에서 BFS를 써서 해결해야 하는 문제가 많았다. 이전에 한 번 공부한적 있는 내용이긴 하지만 시간이 조금 지나기도 했고, 기억도 잘 나지 않아서 복습도 하고 기록도 해둘 겸 정리글을 써보게 되었다. 무엇보다 그리 자세히 공부를 했던 것 같지는 않아서 이번에 자세히 짚고 넘어가고자 한다.2. BFSBFS란?그래프나 트리에서 루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법현재 노드의 모든 인접한 노드를 방문 ㅡ> 다음 레벨로 이동FIFO(선입선출) 특성 때문에 queue를 이용최단 경로 찾기에 활용모든 경로를 한단계씩 탐색노드 방문 여부에 대한 검사가 필요 (안 하면 무한루프 가능성 있음)시간 복잡도 O(V+E) ..

1. 개요최근 코딩 테스트 준비를 하면서 문제를 푼 다음에는 한번씩 다른 사람들은 어떤 식으로 코드를 작성했는지 확인해 보고 있다. 그런데 나는 for문의 증감 연산자를 사용할 때 후위 연산자를 주로 사용하는 편인데, 코드를 좀 깔끔하게 작성했다 싶은 사람들은 for문 안의 증감 연산자로 전위 연산자를 사용하는 경우가 많아서 이게 특별한 이유가 있는 것인지 의문이 가서 이에 대해 알아 보았다.2. 차이결론부터 얘기하자면 전위 연산자가 후위 연산자보다 조금 더 효율적이라고 한다. 이유에 대해 자세히 알아보기 위해 작동 방식을 나타낸 코드와 함께 알아보겠다.1. 전위 연산자i=i+1; // i의 값을 1만큼 증가시켜 저장return i; // 1만큼 증가된 i값을 반환전위 연산자의 작동 방식은 위의 간단한 ..

정렬 알고리즘정렬 알고리즘이란? : 배열과 같은 리스트에 저장된 요소들을 특정한 순서대로 재배치하는 알고리즘 정렬 알고리즘 선택 시 고려 사항- 시간 복잡도- 메모리 사용량- 안정성(stability)- 직렬 vs 병렬위와 같은 것들을 고려해야 하기 때문에 정렬 알고리즘 선택 이전에 정렬할 데이터의 양, 이미 정렬된 정도, 필요한 추가 메모리의 양 등을 고려해서 적절한 알고리즘을 선택하는 과정이 필요하다. 정렬 알고리즘 7가지1. 선택 정렬 (Selection Sort) : 선택된 값과 나머지 데이터를 비교하여 알맞은 자리를 찾는 알고리즘. (안정성 보장 X)ㅡ> 시간복잡도 worst, average, best : O(n^2)  2. 삽입 정렬 (Insertion Sort) : 데이터를 순회하면서 정렬이..