컴퓨터 알고리즘- 알고리즘의 첫걸음
알고리즘이란?
-어떤 문제를 해결하기 위해 밟아야 하는 과정
-어떤 문제를 해결하기 위해 어떤 액션, 전략, 오퍼레이터를 사용하는 것
유형1
-문제는 있는데, 알고리즘이 없다.=>알고리즘 개발
유형2
-문제는 있고, 알고리즘도 있다. =>알고리즘 구현
알고리즘에 접근하려면...
1.기존에 알려진 알고리즘 학습
2.알고리즘 구현
3.문제를 해결하기 위한 자신만의 알고리즘 고민
접근하기 위해 고려할 점
1.문제 파악 : 무엇을 할 것인가?
2. 행동 고민 : 어떤 방식, 과정으로 해결할 것인가? : if , for 구문을 어떻게 배치할 것인가?
3.효율성 분석 : 제일 효율적인 방법은 무엇인가?(efficiency 분석)
어떤 알고리즘이 있을까?
1.1 최대 숫자 찾기
-카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법
-마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다.
-이렇게 찾는 방법을 순차 탐색이라고 한다. 즉, 카드를 한 장씩 차례대로 읽어 가며 찾는 방법
1.2 임의의 숫자 찾기
-최대 숫자 찾기처럼 머릿속에 85를 기억하고 바닥에 펼쳐진 카드를 차례대로 한 장씩 읽으며 85가 적힌 카드를 찾는다. (순차탐색 이용)
-그러나 10장의 카드가 오름차순으로 미리 정렬되어있다면?
->이진탐색트리(BST)
:오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이 과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘
:데이터가 많을 수록 효율적이다. 찾아야 할 수가 한 번에 반이 날아가기 때문에.
:데이터가 적으면 정렬에 오래걸린다. 순차 찾기 이용할 것
중간에 있는 카드 45와 85를 먼저 비교한다.
1.3 동전 거스름돈
-물건을 사고 거스름돈을 동전으로 받아야 한다면? 가장 적은 수의 동전으로 거스름돈 만들기
->일반적으로 거스름돈에 대해서 가장 큰 액면의 동전부터 차례로 고려한다.
이렇게 현재 순간에 최선의 선택을 하는 알고리즘을 그리디 알고리즘(탐욕적 알고리즘)이라고 한다.
쉽지만 항상 옳은 것은 아니다.
1.4한붓그리기
-종이에서 연필을 떼지 않고 그리는 한붓그리기 문제.
-한 포인트에서 갈 수 있는 모든 경우의 수를 따져 보고 최선의 선택을 하는 것
-현재 점에서 현재 점으로 돌아오는 사이클도 찾아야 함
1.5 미로 찾기
-현 위치에서 한 방향을 선택하여 이동하고, 길이 막혀 있으면 다시 되돌아 나오며, 다른 방향으로 다시 시도해 본다.
-가능하다면 지나갔던 곳을 표시해 놓고 다시 가지 않는다.
1.6 가짜 동전 찾기
-동전 더미 속에 약간 가벼운 가짜 동전이 섞여 있다. 양팔 저울만 사용하여 가짜 동전을 찾아내라.
-가능한 한 저울에 동전을 다는 횟수를 줄여야 한다.
동전더미를 반으로 분할하여 저울에 달고, 가짜 동전이 있는 더미에서 계속해서 반으로 나누어 저울에 단다.
1.7 독이 든 술단지
-희생되는 신하의 수를 최소한으로 하여 많은 술단지 중 독이 든 술단지를 찾아라
-일주일 후, 신하가 살아 있으면 맛보지 않은 단지에 독이 들어 있고, 죽는다면, 맛본 술단지에 독이 들어 있다.
->각 단지에 2진수를 0부터 차례대로 부여하고, 각 신하가 술 맛을 보면 1, 안 보면 0으로 하여 단지에 할당된 이진수대로 신하에게 술을 맛보게 한다. 신하가 모두 살았을 때, 일부만 살았을 때, 모두 죽었을 때 모든 상황에서 독이 든 술단지를 알 수 있다.
기억할 것!!
-순차 탐색 :주어진 순서에 따라 차례로 탐색한다.
-이진 탐색 : 정렬된 데이터에 대해서 중간에 있는 데이터를 비교하여 그 결과에 따라 같으면 탐색을 마치고, 다르면 작은 데이터가 있는 쪽 또는 큰 데이터가 있는 쪽을 같은 방식으로 탐색한다.
-탐욕법 : 가장 액면이 높은 동전을 항상 선택한다.
-다이나믹 알고리즘 : 현재 점에서 다음으로 이동 가능한 점을 선택할 때에는 반드시 사이클이 존재하여야 한다.
-분할 정복 알고리즘: 문제를 나누고 다시 풀기를 반복한다.
-2진수 활용 : 독이 든 술 단지 문제