1부터 100까지 더해보자

오랜만에 알고리즘 공부를 해보자 아주 간단한 알고리즘이다 1부터 100까지 혹은 n부터 m까지의 더하는 알고리즘이다. 솔직히 아주 간단하다. 하지만 여러 방법으로 접근해보자 그게 목적이다 ㅎㅎㅎ 일단 우리가 흔히 쓰는 1부터 100까지의 합이다 소스를 보자 int sum = 0; for (int i = 1; i <= 100; i++) { sum += i; } System.out.println(sum); 흔히 쓰는 방법이라 따로 설명은 생략하겠다. 참고로 자바8에선 더 간단해졌다. System.out.println(IntStream.rangeClosed(1, 99).sum()); 위와 같이 하면 된다. 하지만 여기서는.. Read More

퀵 정렬 (quick sort)

퀵정렬 (quick sort) 이번엔 퀵정렬을 알아 보겠다. 퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다. 위키출처 이라고 한다. 말그대로 빠른 정렬 방식이다. 위키 출처 일단 설명을 해보자 만약 6, 3, 8, 7, 9, 2, 1, 5 이런 리스트가 있다고 가정하자! 그럼 일단 왼쪽에 있는걸 피벗으로 잡자 6을 피벗으로 잡는다. 그리고 또한 left도 6 이라고 정하고 맨 오른쪽에 있는걸 right라 정하자 그럼.. Read More

BFS(너비 우선 탐색)

너비 우선 탐색 너비우선탐색이란 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. –위키피디아 출처 깊이우선탐색은 스택을 이용하지만 너비우선탐색은 큐를 이용한다. 말은 간단하다. 한번살펴보자 1에서 시작을 한다면 인접한 정점으로 이동한다. 1에서 인접한 정점은 2와3이다. 그래서 1->2, 1->3으로 이동한다. 그리고 2의 인접한 정점은 4밖에 없다. 2->4 다음은 3의 인접한 정점은 5,6,7 이다 3->5, 3->6, 3->7 이렇게 이동한다. 코드를 보자. static int[][] BFS = { {0,0,0,0,0,0,0,0}, {0,0,1,1,0,0,0,0}, {0,1,0,0,1,0,0,0}, {0,1,0,0,0,1,1,1},.. Read More