Development/Algorithm

Development/Algorithm
정렬(Sorting) 알고리즘 O(n^2)
정렬 알고리즘 컴퓨터분야 전공을 했다면 한번쯤 반드시 들어봤을법한 "정렬" 에 관하여 얘기를 하고자 한다. 앞선 포스팅(이라고 해도 몇개월 전에 쓴..) 에서 잠깐 언급을 했었는데, 자세하게 보지않고 스쳐간 것 같아서 정리할 겸 글을 끄적여본다. 사실 간략하게 요약하면 "이진탐색(Binary Search)을 사용하기 위해 데이터를 정렬한다." 의 의미가 클 수 있다. 분산된 데이터는 자료를 참조하기가 어렵다. 예를 들어 100만개의 데이터가 있고, 맨 마지막에 데이터가 있다면, 원하는 데이터를 찾기 위해서는 100만개를 다 봐야할 수 있다. 그렇기 때문에 최악의 경우 n번 탐색을 해봐야 한다. 하지만 이진탐색을 사용하면 의 속도로 검색할 수 있다. 별로 체감이 안될 수 있는데, 다음 그래프를 보면 이해가..
→2016.04.01
Development/Algorithm
[주저리] 사천성 게임의 경로탐색
사천성(Shishen-sho) 한번쯤은 즐겨본 적이 있을 "사천성" 이라는 게임이다. 이 게임에서 가장 주된 기능이라고 하면 단연코 "경로탐색" 알고리즘일 것이다. 처음 문제에 접근할 땐 단순히 "두번이상 꺾이지 않는 경로만 탐색하면 되겠지!" 라고 생각했었는데, 이게 점차 갈수록 최적경로가 아닌 문제와 더불어 소거되는 경로를 표시하려면 좌표를 저장해야 하는데 그러한 사소한 문제부터 걸리기 시작한다. 일단 문제를 해결하기 위해서 접근가능한 방법은 아래와 같다. 1. DFS2. BFS3. Heuristic Path Finding 1. DFS(깊이-우선 탐색)가장 간단하고 직관적이다. 스택 혹은 재귀를 이용하여 다음 탐색할 대상을 찾고 거의 한쪽방향의 끝이 나올떄까지 주변을 탐색하다가, 해가 없을 경우다시 ..
→2016.02.28
Development/Algorithm
[알고리즘] 시간복잡도(Time Complexity)
이전 포스팅에서 알고리즘에 대한 개념을 설명했다. 그 중, 시간복잡도라는 개념이 나왔는데 밑의 그림을 예로 들었는데 이해가 쉬우리라 판단된다. 보이는 것처럼, "알고리즘"이 수행되는 시간이 시간복잡도이다. 비슷한 친구로 "공간복잡도" 라는 개념도 있는데, 반대로 "메모리"를 얼마나 사용하는지에 대한 용량의 개념이다. 데이터를 저장할 수 있는 메모리와 저장매체의 발전으로 인하여 메모리에 대한 개념 또한 그렇게 큰 범주가 되지 못하고 있다. 예컨데, 예전 프로그래밍에서 배열이나 동적할당을 최소화 하고 컴파일을 최소화하며.. 등등 메모리가 얼마 없던 시절의 최적화 하기 위한 행동들은 지금은 하지 않아도 된다. 다만, 최적화의 범주에서 볼 때 좋은 행동이라고 볼 수 있다. 시간복잡도의 그래프가 또 빠질 수 없는..
→2015.12.02
Development/Algorithm
[알고리즘] 알고리즘 종류 및 시간복잡도 정리
알고리즘(Algorithm) 이란? "문제를 해결하는 방법" 이다. 특히, 컴퓨터에서 알고리즘이란 거의 안 쓰이는 곳이 없을 정도로 널리 이용되고 있다. 어떠한 Input 데이터가 주어지면 이것을 사용하기 편하게 문제를 해결한 형태의 Output을 만든다. 여기서 계속 문제를 해결한다고 하는데, 컴퓨터에서 알고리즘을 사용하는 이유는 대개 다음과 같은 이유로 사용하게 된다. 자료구조 - 정렬, 탐색, 트리, 힙트리구조 - DFS, BFS그래프 - 최단거리정수론, 난수발생, 해석기하, 그래픽 등.대부분의 경우 "자료구조"와 관련된 알고리즘이 직접적으로 사용할 일이 많아서 주로 쓰게 된다. 간단하게 하나 하나 정리해보면 1. 자료구조(Data Structure) "정렬"에 관련된 알고리즘이 가득하다. 데이터를..
→2015.12.02

• 이전
• 1
• 다음