728x90 알고리즘18 다익스트라 알고리즘(Dijkstra Algorithm) 안녕하세요. 옆집 컴공생입니다. 오늘은 다익스트라 알고리즘을 배워볼거예요. 다익스트라(Dijkstra Algorith)은 다이나믹 프로그래밍을 활용한 대표적인 최단경로(Shortest Path) 탐색 알고리즘입니다. 흔히 인공위성 GPS 소프트웨어등에 많이 이용된다고 하네요. 음의 간선을 포함할 수 없는데 현실에는 음의 간선이란 게 존재하지 않잖아요? 그러니깐 매우 현실적인 알고리즘 중 하나라고 할 수 있겠습니다. 다익스트라 알고리즘은 다이나믹 프로그래밍이나 그리디 알고리즘을 분류가 되는데요. 다이나믹 프로그래밍인 이유는 이러합니다. '최단거리는 여러 개의 최단거리로 이루어져 있다.' 너무 당연하게도, A -> B -> C -> D 로 가는 최단 걸이로 가는데 A -> C -> B 가 A -> B -> .. 2020. 6. 10. 에레스토테네스의 체 안녕하세요. 옆집컴공생입니다. 오늘은 범위 내에 소수를 전부 구해주는 에레스토테네스의 체를 배워 보겠습니다. 소수란 영어론 Prime Number(프라임 넘버) 라고 하는 '약수가 1과 자기자신 뿐인 수'를 의미합니다. 예로 들면 2,3,5,7 등이 있겠습니다. 간단한게 소수를 구하는 반복문을 볼까요? 다음 함수는 x가 소수이면 true , 합성수(소수가 아닌 수)이면 false를 반환해주는데요. 1과 x를 제외한 나머지 모든 수를 for 문으로 돌면서 나누어지는 체크해보는겁니다. 사실 이 방법은 굉장히 오래 걸리는 편인데요. 사실 소수를 판별하는데는 소수의 제곱근 까지만 체크를 해주면 됩니다. 왜일까요? 합성수를 20을 생각해봅시다. 20의 약수는 2, 4, 5 ,10 입니다.( 1과 자신은 제외했습니.. 2020. 6. 9. 다이나믹 프로그래밍(Dynamic Programming) 안녕하세요. 옆집 컴공생입니다. 오늘은 다이나믹 프로그래밍에 대해 배워 보겠습니다. DP 라고도 부르죠. 다이나믹 프로그램은 알고리즘 문제를 푸는 큰 축인데요. 꼭 익혀놓아야 하는 부분입니다. 컴퓨터적인 사고력을 물어보기에 적합하기 때문에 자주 출제되기 때문이라고 합니다. ▶다이나믹 프로그래밍이란 '하나의 문제는 단 한번만 풀도록 하는 알고리즘' 입니다. 한번 푼걸 다시 여러번 푸는건 비효율적이겠죠? 이런 알고리즘을 개선시키는 방안입니다. ▷분할 정복 기법(Divide and Conquer)은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다.(정렬과 같은 경우 다시 푸는 경우가 없습니다. 퀵정렬과 병합정렬이 빠른 이유입니다.) 예를 들어 피보나치 수열을 심각한 비효율성을 낳는데요. 피보나치 수열은 특정.. 2020. 6. 7. 이진 트리 구현과 순회(Traversal) ※이 글은 나동빈님 강의를 보고 복습용으로 작성하는 글입니다. https://blog.naver.com/ndb796/221233560789 19. 이진 트리의 구현과 순회(Traversal) 방식 기본적으로 가장 많이 사용되는 비선형 자료구조는 이진 트리(Binary Tree)입니다. 이진 트리는 트리 자... blog.naver.com 이진 트리(Binary Tree)는 굉장히 많이 사용되는 비선형 자료구조입니다. 비선형이란 선, 즉 일렬로 구현되지 않았다는 뜻입니다. 또 트리 자료구조를 활용한 대표적인 예시로 데이터의 탐색 속도 증진을 위해 사용되는 구조입니다. 이전 Heap Sort 에서도 다뤄 본 적이 있었습니다. https://com24everyday.tistory.com/101 힙정렬 저번주에.. 2020. 6. 5. 이전 1 2 3 4 5 다음 728x90
