알고리즘 기초

### 알고리즘이란?

고대 페르시아의 수학자 알콰리즈미에서 유래되어 문제를 해결하기 위한 여러 동작들의 모임.

알고리즘을 이용하기 위해서는 복잡한 구조의 코드를 정확하게 구현할 수 있는 구현력이 필요하다.

 

### 알고리즘의 조건

- 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.

- 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.

- 입력 : 정의된 입력을 받아들일 수 있어야 한다.

- 출력 : 답으로 출력을 내보낼 수 있어야 한다.

- 유한성 : 특정 수의 작업 이후에 정지해야 한다.

- 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

 

깊이우선탐색 (Depth First Search)

- 그래프 탐색 방법의 한가지로 한 경로로 탐색하다 특정 상황에서 최대한 깊숙하게 들어가서 확인 후 다시 돌아가 다른 경로로 탐색하는 방식.

- 일반적으로 재귀함수를 이용하여 구현, Stack을 이용하여 구현하기도 함.

- 구조상 Stack Overflow에 유의해야함.

- 그래프 알고리즘에서 기초가 되는 탐색 방식으로 반드시 숙지가 필요함

- 활용 : 백트래킹, 단절선 찾기, 단절점 찾기, 위상정렬, 사이클 찾기 등

 

DFS의 순서

1. 체크인

2. 목적지에 도달했는가 (dp 리턴)

3. 연결된 곳을 순회

4. 갈 수 있는가? (dp 체크)

5., 간다.

6. 체크아웃

 

너비우선탐색 (Breadth First Search)

- 그래프 탐색 방법의 한가지로 시작노드에서 시작하여 인접한 노드를 먼저 탐색하는 방식.

- 일반적으로 Queue 자료구조를 이용하여 구현.

- 그래프 알고리즘에서 기초가 되는 탐색 방식으로 반드시 숙지가 필요함.

- BFS 활용 : 최단경로 찾기, 위상 정렬 등

 

BFS의 순서

1. 큐에서 꺼내옴

2. 목적지에 도달했는가?

3. 연결된 곳을 순회

4. 갈 수 있는가?

5. 체크인 & 큐에 넣음.

 

정렬된 데이터의 특성.

- 정렬은 데이터의 크기 정보(값)를 위치 정보(인덱스)로 확장시킴.

- 정렬된 데이터에서 어떤 위치의 데이터 값을 알면, 그 데이터 앞의 데이터와 뒤의 데이터의 크기를 유추 할 수 있음.

- 정렬된 데이터에서 동일 값을 가지는 데이터는 반드시 인접함

- 데이터 중 K번째로 작은(큰) 값에 빠르게 접근 가능

- 데이터의 속성값이 여러 가지인 경우 정렬의 기준이 여러 가지가 될 수 있음.

 

1. 유일성 검사 / 중복 제거 : 인접한 데이터와의 비교만으로 유일성 검사 및 중복 제거가 가능

2. 빈도 구하기 : 정렬된 데이터를 한번씩만 확인하면 각 숫자의 빈도 수를 확인 가능

3. 합집합 / 교집합 구하기 : 정렬된 두 데이터 집합에서도 정렬된 데이터의 특징을 이용.

4. 이분 탐색 : 찾고자 하는 데이터의 범위를 1/2로 줄여나가며 탐색

5. Compare 함수의 활용 : 표준 라이브러리의 정렬은 Compare 함수를 이용하여 정렬 기준을 재정의하여 사용

- Comparable을 상속하는 방식

class Person implements Comparable<Person>{
//class Person {
	int num;
	int count;
	int timeStamp;
	
	public Person(int num, int count, int timeStamp) {
		this.num = num;
		this.count = count;
		this.timeStamp = timeStamp;
	}
    
	@Override
	public int compareTo(Person o) {
		if(this.num < o.num) {
			return -1;
		}
		// 0 = Same = 바꾸지 않음.
		else if (this.num == o.num) {
			return 0;
		}
		// 1 = wrong order
		else {
			return 1;
		}
	}
}

- Comparator 객체를 생성하는 방식

list.sort(new Comparator<Person>() {
	@Override
    public int compare(Person o1, Person o2) {
    	if(o1.count < o2.count) {
    		return -1;
    	}
    	else if (o1.count == o2.count) {
    		if(o1.timeStamp < o2.timeStamp) {
    			return -1;
    		}
    		else if (o1.timeStamp == o2.timeStamp) {
            	return 0;
            }
            else {
            	return 1;
            }
    	}
    	else {
    		return 1;
    	}
    }
});

 

관련 문제

- 3425 고스택

- 3055 탈출

- 1062 가르침

- 1713 후보추천하기

- 1103 게임

- 1039 교환

- 1920 수 찾기

- 9663 N-Queen

- 1759 암호 만들기

- 2580 스도쿠

- 1339 단어 수학

- 15686 치킨 배달