Do it 알고리즘 코딩테스트 하루코딩 5장 탐색 문제

 

 

 

이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.

 

# 13 연결 요소의 개수 구하기 

연결요소는 에지로 연결된 노드의 집합

 

ex) 1, 2, 5와 3, 4, 6 총 2개

 

DFS는 그래프 완전 탐색이므로, 한번의 DFS가 끝날 때 까지 탐색한 노드의 집합이 연결요소 1개이다.

즉 모든 노드를 탐색할 동안 DFS 횟수가 연결요소의 개수이다.

만약 그래프의 모든 노드가 연결 되어 있었다면 DFS 횟수는 1이다.

 

방향이 없는 그래프이므로 양방향 모두 인접 리스트로 표현

 

N=1,000이므로 O(n^2)인 알고리즘도 사용가능하다.

 

if(방문하지 않은 노드가 존재한다면) { // 각 연결요소의 방문 여부

count++;

DFS(i);

}

 

DFS(int i) {

if(visited[i] == true) { // 연결요소 내부의 노드 방문 여부

return; // DFS() 현재 노드 탐색 종료

}

}

 

#14 미로 탐색하기

서로 인접한 칸만 이동 // 즉, 상하좌우 4방향만 이동가능

dx, dy // 상하좌우 이동 방향 표현 배열

ex) 0 1 이면 아래로 이동

 

(1, 1) 에서 출발 // 인덱스 주의

 

N=100이므로 O(n^2)인 알고리즘도 사용가능하다.

 

최단경로 찾기 이므로 DFS도 가능하지만, BFS가 더 적절하다. // 재귀함수가 달고 있어야 하므로

 

1대신 횟수 기록하면 (1,1)에서 자기자신에 도달하는 최단 거리 // 활용가능

 

 Queue 는 LinkedList로 구현

 

BFS(0,0) // 최단 경로 탐색 실행

 

for(상하좌우 탐색) {

 if(유효한 좌표) {

  if(0이 아니면서 이미 방문한 노드X) {

  }

 }

}

 

공백 없는 문자열 분리 substring(j, j+1);

 

#15 원하는 정수 찾기

N개의 정수 안에 X라는 정수가 존재 여부

 

N = 10,000 // 데이터 셋의 크기(개수)

M = 10,000 // 질의의 개수

이므로 N^2인 알고리즘은 사용하지 못한다. 시간복잡도를 더 줄여야한다.

그러므로 이진탐색 사용하여 정렬 NlogN 먼저 후, 탐색 logN을 질의 M번 수행

 

Arrays.sort(A);// 배열 A를 오름차순으로 정렬, 시간복잡도 O(nlogn)

 

while(시작 인데스<=종료 인덱스) // 더 이상 탐색할 부분이 없을 때 까지, 즉 모든 데이터를 탐색할때까지 반복

 if(중앙값 > 데이터) { // 왼쪽 선택

 종료인덱스 = 중앙인덱스 - 1

}

else if(중앙값< 데이터) { // 오른쪽 선택

 시작인덱스 = 중앙인덱스 + 1

}

else { // 중앙값 == 데이터, 즉 찾았으므로

find = true;

break; // 반복문 종료

}