알고리즘

[삼성 SDS] 2022 하계 알고리즘 특강 사전테스트 후기

🌳 테스트 정보 ✅ 총 5문제 ✅ 시간제한 없음(일주일 동안 알아서 풀면된다. 일주일 내내 푸는 것도 가능. 단, 한 문제당 2~3시간 정도 사용하는 것을 추천한다고 한다.) ✅ 언어(3가지): C, C++, Java 1, 2번은 구현 문제였고 체감 난이도는 실버 1~2였다. 구현 방법은 어렵지 않았지만 잘못 짜면 시간 초과가 발생하거나 놓치는 부분이 발생하기 쉬운 그런.. 3번은 잘 기억이 안 난다. 아마 보고 넘겼던 듯하다. 4번은 어떻게 풀지 한참 고민했는데 나중에 보니 최소 환승 알고리즘이라고 해서 이미 이 자체로 유명한 알고리즘이 있었다. 백준에 비슷한 문제가 있으니 풀어보면 좋을 것 같다. 🥇 [2021] 최소 환승 경로 🥇 [5214] 환승 🥈 [16166] 서울의 지하철 5번은 건드리지도 ..

DFS & BFS

DFS(Depth First Search) • 깊이 우선 탐색 • 스택 or 재귀함수 이용 • 동작 과정 1. 탐색 시작 노드를 스택에 넣고 방문 처리 2. 스택의 최상단 노드에 방문하지 않은 노드가 하나라도 있다면 그 노드를 스택에 넣고 방문 처리 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼냄 3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복 BFS(Breadth First Search) • 너비 우선 탐색 • 그래프에서 가까운 노드부터 우선적으로 탐색 • 큐 사용 • 특정 경로에서 최단거리 찾을 때 많이 사용 • 동작 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서 노드를 꺼낸 뒤 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리..

이분 탐색(Binary Search)