Algorithm

[백준 -자바] 13549번 : 숨바꼭질3

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net "숨바꼭질" 문제들이 BFS로 풀이가 되는게 많아서 BFS로만 접근했다가 도저히 정답이 나오질 않았다... 그래서 참고 자료를 찾아보니 원래 이 문제는 단순한 BFS를 요구하는 문제가 아니다. 왜냐하면, BFS를 하기 위해서는 모든 간선의 가중치가 동일해야 한다는 전제 조건이 필요하기 때문이다. 이 문제는 가중치가 0인 간선이 있기 때문에 일반적으로는 단순한 BF..

[백준 - JAVA] 1748번 : 수 이어 쓰기 1

https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 문제 조건 파악 및 접근 자릿수만 구하면 되므로, 자릿수가 언제 바뀌는지만 확인해서 변경해준다. 1 ~ 9 => 1자리 10 ~ 99 => 2자리 100 ~ 999 => 3자리, 즉 i를 10 , 100 , ... 으로 나눴을때 몫이 0이면 자릿수가 바뀐다. 따라서 자릿수가 바뀔때마다 다음 나눠야 하는 수는 10을 곱해주고, 다음 더해줘야 할 자릿수는 +1을 해준다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 i..

[알고리즘-기초] 그래프 탐색(깊이 우선 탐색 - DFS)

그래프 탐색 그래프는 기본적으로 각 정점들이 어떠한 연관 관계를 갖고 있는지를 나타내는 자료구조 이다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로 연결된다. 각 컴퓨터나 네트워크 장비를 정점(vertex , node)로 연결을 간선(edge)로 본다면 그래프로 표현이 가능하다. ⓑ 경로 찾기 : 특정 위치 간 가장 짧은 경로 / 긴 경로를 그래프를 이용해 찾을 수 있다. 구글 맵 또한 이러한 응용을 한 것이며, 게임 내 NPC 등의 모델도 이를 통해 움직임..

[알고리즘-기초] 그래프 탐색(너비 우선 탐색 - BFS)

그래프 탐색 그래프는 기본적으로 각 정점들이 어떠한 연관 관계를 갖고 있는지를 나타내는 자료구조 이다. 그래프는 가장 기본적이고 유연한 구조로 관계를 나타낼 수 있다. 많은 문제들 중 그래프로 해결 가능한 문제가 50% 정도 된다고 이야기하는 엔지니어도 있다. (참고) 해결 가능한 문제들의 예시를 알아보자. 어떠한 것들이 특히 해결이 가능할까? ⓐ 네트워크 : 우리가 사용하는 컴퓨터는 인터넷으로 연결된다. 각 컴퓨터나 네트워크 장비를 정점(vertex , node)로 연결을 간선(edge)로 본다면 그래프로 표현이 가능하다. ⓑ 경로 찾기 : 특정 위치 간 가장 짧은 경로 / 긴 경로를 그래프를 이용해 찾을 수 있다. 구글 맵 또한 이러한 응용을 한 것이며, 게임 내 NPC 등의 모델도 이를 통해 움직임..

[알고리즘-기초] 힙(Heap) 정렬

힙 정렬 힙 정렬의 시간복잡도는 O(NlogN)으로 빠른 정렬에 속한다. 퀵 정렬은 최악의 경우 O(N^2)의 성능을 내지만, 힙 정렬은 안정적인 성능을 발휘한다. 또한 추가적인 배열을 사용하지 않아 메모리 측면에서도 이점을 보인다.(In Place정렬) 완전 이진트리에서 파생된 heap 특성을 사용하여 정렬하는 알고리즘으로 힙은 부모의 값이 자식의 값보다 항상 크거나 항상 작다라는 조건을 만족하는 완전이진트리 형태의 자료구조이다. 완전이진트리는 자식 노드를 왼쪽부터 채워나가는 형태의 자료구조이다. 힙의 개념 완전이진트리와의 차이점은 큰 값이 상위, 작은 값이 하위에 위치한 트리형 자료구조로써 부모-자식 관계가 일정해야 한다. 작은 값이 부모가 되는 힙 형태를 min-heap(최소 힙), 큰 값이 부모가..

[알고리즘-기초] 셸(Shell) 정렬

Shell Sort(셸 정렬)셸 정렬은 'Donald L. Shell' 이 제안한 방법으로, 삽입 정렬(Insertion Sort)를 보완한 방식이다.  삽입 정렬의 문제점은 무엇이 있을까? 삽입 정렬은 각 데이터가 삽입될 적절한 위치를 찾기 위해서 인접한 데이터와의 여러 번의 비교 과정을 거쳐야만 한다.즉, 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 그런데, 이 삽입 정렬은 Nearly Sorted 상태의 데이터라면 O(n)에 가까운 매우 빠른 성능을 보여준다는 장점이 있다.그래서 셸 정렬은 기존의 삽입 정렬을 수행하기 전에 전체 데이터를 Nearly Sorted 형태로 만들면 기존의 삽입 정렬을 그대로 처음부터 적용하는 것보다 더 ..

[알고리즘-기초] 삽입(Insertion) 정렬

삽입(Insertion) 정렬삽입 정렬은 현재 비교하고자 하는 target(타겟)과 그 이전의 원소들과 비교하며 자리를 교환(swap)하는 정렬 방법이다. 삽입 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그리고 이전에 다뤘던 선택 정렬과는 달리 삽입 정렬은 '안정 정렬'이다. 특성설명In-place 알고리즘Memory 상에서 필요 시 상호 위치만 변경될 뿐 추가적인 배열 생성이..

[알고리즘-기초] 선택(Selection) 정렬

선택(Selection) 정렬선택 정렬은 말 그대로 현재 위치에 들어갈 데이터를 찾아 선택하는 알고리즘이다. 좀더 정확하게 말하자면 무작위 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하는 것이다. 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다.그리고 '불안정 정렬'이다.  특성설명In-place 알고리즘Memory 상에서 필..

[알고리즘-기초] 버블(Bubble) 정렬

버블(Bubble) 정렬두 개의 인접한 원소를 비교하여 정렬하는 방식이다. 왜 Bubble 이라는 이름이 붙었는지 찾아보니 정렬 과정에서 원소의 이동이 마치 버블이 수면위로 올라오는 것 같다고 해서 버블(Bubble) 이라는 이름이 붙었다고 한다...  정렬 방식 중 가장 쉬우니 일단 버블 정렬에 대한 특징만 짚고 넘어가보자. 버블 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그..

[알고리즘-기초] 정렬 (개요)

1. 정렬 알고리즘 개요정렬(sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나이다.  숫자가 하나씩 적힌 카드가 10장 있다면, 이 카드를 오름차순으로 정렬해보자. 어떻게 이 카드들을 정렬할 수 있을까?보통 인간이라면 카드를 훑은 후 순식간에 숫자를 0부터 10까지 구성된 걸 확인하고 순차적을 나열할 것이다. 하지만 컴퓨터에게는 쉬운 작업이 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. 정..