Computer Science/Algorithm 썸네일형 리스트형 How to learn the algorithm? Learning algorithms is a crucial skill for any programmer. Algorithms are the set of rules that help in solving a problem in a finite number of steps. Here are some tips on how to learn algorithms in programming. 1. Start with the basics: Before diving into complex algorithms, start with the basics. Learn about data structures like arrays, linked lists, queues, and stacks. Understand how they wo.. 더보기 시간복잡도 개념 1 시간 복잡도 나타나는 수 1(constant) : 입력자료의 수에 관계없이 일정한 실행시간 갖음 Log N : 입력자료의수에 따라 시간이 점점 시간이 조금씩 증가함 - 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤때 나타나는 유형. 예) 효율이 좋은 검색 알고리즘.. 이 뭐가 있드라. 이진탐색 같은 것 - Log2n N(Linear) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우- 입력자료 각각에 일정량(시간)이 할당되는 경우 N Log N : 이것은 주로 큰문제를 일정한 크기를 갖는 문제로 쪼개고(Log N), 다시 그것들을 하나로 모으는 경우에 나타남 (N). 예) 효율 좋은 정렬 알고리즘. quick sorting, heap sorting 등. link: http://wr.. 더보기 Hashing 이란? 1. (Hashing)이란 무엇인가? - 해싱(hashing)이란 한마디로 말해서 많은 양의 데이터(data)들을 그보다는 작은 크기의 테이블(table)로 대응 (mapping)시켜 저장할 수 있도록 하는 일종의 데이터 관리 기법이다. 데이터들을 저장하거나 찾을 때 인덱스 (index)라는 또다른 데이터 스트럭쳐(data structure)를 이용하는 대신, 각 데이터들이 테이블의 어느 영역에 위 치할 것인가를 결정해주는 해쉬함수(hash function)를 사용하여 일정한 시간 내에 데이터들을 효과적으로 찾을 수 있도록 해주는 것이 바로 해싱이다. 따라서 데이터들은 순차적으로 저장되는 것이 아니라 테이블 전 영역에 걸쳐서 고루 분포하게 되며, 저장된 데이터를 찾을 때에도 해쉬함수를 사용하면 곧바로 그.. 더보기 알고리즘 강좌 7회 백 트래킹 백 트래킹(Backtracking : 되추적)의 개념부터 살펴보자. 백트래킹을 한마디로 말하자면... “몽땅 다 찾아본다” 라는 말로 요약이 가능하다. 여기다 살을 조금 붙이면 “답에 될 수 있는 것을 몽땅 다 찾아본다” 라는 말로 확장할 수 있다. 백트래킹의 개념은 이 말 그대로다. 답이 될 만한 것들을 모두 다 뒤져봐서 그 중에서 답을 찾는 알고리즘이 바로 백트래킹이다. 이러한 백트래킹은 몇가지 특징을 가진다. 1. 함수의 재귀호출을 이용해 구현한다. 2. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 대체로 수행하는데 시간이 오래 걸린다. 3. 모든 가능성을 몽땅 뒤져보는 것이기 때문에, 백트래킹으로 풀 수 없는 문제는 별로 없다. 이 특징들을 대충 살펴보자. 1번에 나온 것처럼 백트래킹은.. 더보기 알고리즘 강좌 6회 - 그리디 #2 - 5. 그리디의 실제 #3 이번에도 그리디를 이용해서 효과적으로 풀 수 있는 문제를 알아보자. 그래프 G가 있을때, 한 정점에서 다른 모든 정점으로 가는 경로를 구하는 알고리즘을 아는가? 이것은 Dijkstra(다익스트라)라고들 부르는 방법이다. 이 알고리즘은 그래프가 있을때 두 정점사이의 최단거리를 구할때 꽤나 유용하다. 서론은 이 정도로 하고, 본격적으로 이 알고리즘을 알아보자. 다익스트라 알고리즘은 지난회에서 배웠던 MST와 좀 비슷하다. 다음과 같은 그래프(저번에 나왔던)을 보자. A에서 다른 정점으로 가는 최단 경로들을 구해보자. 일단 A를 선택한다. 그리고 A를 집합 Y에 넣는다. 그다음 A에서 가장 가까운 정점 B를 선택하고, B를 집합 Y에 넣는다. 그러면 Y = {A, .. 더보기 알고리즘 강좌 5회 - 그리디 #1 - 1. 그리디(Greedy)란? 이번에 우리가 공부해 볼 알고리즘은 그리디(Greedy)이다. 간단히 그리디에 대해 알아보면, 어원 그대로 상당히 탐욕적임을 느낄 수 있을 것이다. 그리디 알고리즘의 핵심은, 몇번의 선택을 하면서 답을 찾아내는데, 그 선택은 전에 결정했거나 앞으로 결정할 선택을 고려하지 않고, 그 당시의 상황에서만 가장 최적인 해를 취하는 것을 의미한다. 이런 과정을 거치기 때문에 그리디 알고리즘은 또 다른 중요한 특징을 가진다. 각 선택들은 부분적으로는 최적일지 모르나 전체적으로 보면 최적이 아닐 수도 있다는 점이다. 그래서 그리디 알고리즘을 쓸 때는 ‘전체적으로도 최적이 되는가?’ 라고 한 번 다시 생각해 봐야한다. ...이렇게 말해놓으면 무슨 소린지 잘 모르는 사람.. 더보기 알고리즘 강좌 4회 - 다이나믹 #3 - 7. 연습문제 풀이 자, 지난번 강좌에 나왔던 연습문제는 푸셨는가? 그럼 풀이법에 대해 설명하도록 하겠다. 이 문제도 동적계획법으로 풀린다.(당연하지.. 동적계획법 강좌에 나온 문젠데) 풀이법은 1차원 Up sequence문제와 별로 다를 것이 없다. 우선 이차원 배열 L(2차원 버젼이므로)을 다음과 같이 잡는다. L[i , j] = i행 j열에 있는 숫자로 끝나는 오름차순 수열의 최대길이 1차원 버젼과 별로 다르지 않다. 그럼 점화식은? L[i , j] = 1 L[i , j] = maximum( L[k1 , k2] + 1 ) 역시 1차원 버젼과 다를것은 별로 없다.(음.. 그러고 보니 "다를것이 없다"라는 말을 지난 강좌에서부터 너무 많이 쓰고 있는 듯..-_-) 그 전까지의 최대.. 더보기 알고리즘 강좌 3회 다이나믹 #2 - 4. 동적계획법의 실제 #3 자, 이번에도 역시 문제를 풀어봄으로서 동적계획법을 더 연습해 보자. 이번에 연습해 볼 문제도 역시 너무도 유명한 동적계획법 예제인 Knap sack문제이다. 설마 모르는 분이 있을까봐 문제설명을 드리자면. 소유권 이전 전문가(이하 도둑)가 직업인 동섭이는 어느 날 밤 귀금속 가게를 털었다. 숙련된 솜씨로 문을 따고 가게 안에 들어가 보니 오색찬란 금덩어리 은덩어리 보석덩어리 똥덩어리(엥~ 이건 아닌가) 등등 각종 덩어리들로 눈이 부실 지경이었다. 동섭의 마음 같아서는 몽땅 털어가고 싶지만 자신이 가져온 가방이 그렇게 큰 편이 되지 못했다. 그래서 가장 값을 높게 쳐주는 보석덩어리들만 가져가려고 한다. 동섭이 가장 비싸게 처분할 수 있도록 배낭을 채워주면 된.. 더보기 알고리즘 강좌 2회 알고리즘 강좌 2회 - 다이나믹 #1 - 1. 동적계획법의 특징 다이나믹 프로그래밍(dynamic programming : 이하 동적계획법) 이란 무엇일까. 이 역시 문제를 푸는 알고리즘의 일종이다. 다이나믹의 가장 큰 특징은 이것이다. "작은 문제들을 해결한 다음 이 결과들을 바탕으로 더 큰 문제의 해답을 찾는 방법이다." 물론 이 말 한마디만으로 동적계획법에 대해 알수는 없다. 동적계획법의 특징들을 하나씩 살펴보자. 우선, 동적계획법은 작은문제를 먼저 해결하고 그 결과를 저장한 다음, 나중에 그 결과가 필요할때 다시 계산하는 대신 저장된 결과를 이용한다. 탑을 쌓을때 밑둥부터 차근차근 쌓아가는 것 처럼, 그 전의 결과를 바탕으로 새로운 결과를 만들어 낸다. 이를 상향식 접근방법이라고 한다. 나중에 배.. 더보기 알고리즘 강좌 1회 알고리즘 강좌 1회 - 알고리즘 개론 - 1. 알고리즘 알고리즘을 한마디로 정의하면, "어떤 문제의 해답을 찾아주는 일반적인 단계별 절차" 간단한 예를 하나 들어보자. 여러분은 전화번호부에서 사람을 찾을때 어떻게 찾는가? 혹시 전화번호부의 첫장부터 끝장까지 넘겨가면서 원하는 사람의 이름을 찾는가?-_-;; 아마 정상적인 사회생활이 가능한 사람이라면 그런 미친짓은 하지 않으리라 믿는다. 그러면 어떻게 찾는가? 그렇다. 여러분도 아시다시피 전화번호부에 있는 사람들의 이름은 가나다 순으로 정렬이 되어있다. "정동섭"이라는 인물을 찾고자 할 경우 전화번호부의 'ㅈ'항목을 찾은 다음, '정'으로 시작하는 사람들의 이름을 찾고, '동'이라는 글자가 이어지는 이름을 찾아낸 후, 마지막으로 '섭'을 찾으면 "정동섭"이.. 더보기 이전 1 다음
