알고리즘 설계 패러다임이란 주어진 문제를 해결하기 위해 알고리즘이 채택한 전략이나 관점을 말한다.


무식하게 풀기


'무식하게 푼다'라는 말은 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미한다. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘들을 가리켜 흔히 "완전 탐색"이라고 한다.



재귀 호출과 완전 탐색


재귀 호출(=재귀 함수)이란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 말한다.


재귀 함수에는 '더 이상 쪼개지지 않는' 최소한의 작업에 도달했을 때 답을 곧장 반환하는 조건문(='거저 사례')을 포함해야 한다.

ex) if(n==1) return 1;


재귀 호출은 기존에 반복문을 사용해 작성하던 코드를 다르게 짤 수 있는 방법을 제공해 준다. 기존의 코드에 비해 재귀 호출을 통해 얻을 수 있는 별다른 이득은 없지만, 문제의 특성에 따라 재귀 호출은 코딩을 간편하게 해 줄 수 있는 강력한 무기가 된다.


재귀 호출을 이용하여 풀 수 있는 문제

1) 소풍 - 학생들을 두 명씩 짝 지어 주되, 친구인 학생들끼리만 짝을 지어줄 수 있는 방법의 갯수.

2) 게임판 덮기 - 격자 모양의 게임판에 ㄴ자 형식의 블록을 알맞게 삽입할 수 있는 경우의 개수.




최적화 문제(Optimization Problem)


문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제들을 통칭해 최적화 문제라고 합니다.


최적화 문제를 해결하는 방식 중 하나는 완전 탐색이다.


최적화 문제를 완전 탐색으로 풀 수 있는 문제 


1) 외판원 문제 - n개의 도시를 한 번씩 돌아서 돌아오는 데 걸리는 최소 거리.

2) 시계 맞추기 문제 - 


'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

알고리즘이 존재가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 따라서 알고리즘의 정확한 증명은 각종 수학적인 기법을 기반으로 되야한다.


수학적 귀납법과 반복문 불변식



수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법.


귀납법은 크게 3가지로 나뉜다.

  • 단계 나누기 = 증명하고 싶은 사실을 여러 단계로 나눈다.

  • 첫 단계 증명 = 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 

  • 귀납 증명 = 첫 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다.

알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문에, 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법.


반복문 불변식 = 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는지..


불변식을 이용한 반복문의 정당성은 다음과 같이 증명한다


  • 반복문 진입시에 불변식이 성립함을 보인다.

  • 반복문 내용이 불변식을 깨뜨리지 않음 보인다. 시작할 때 불변식이 성립하면, 끝에서도 성립한다

  • 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음 보인다.

*불변식이 깨졌을 때 프로그램을 강제 종료함으로써 알고리즘에 문제가 있는지 없는지를 판단할 수 있다. 다만 엄청나게 많이 실행되는 반복문 안에 단정문을 배치하는 것은 삼가는 것이 좋다.


귀류법



귀류법은 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법.


알고리즘의 결과가 최선임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선의 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명한다.


비둘기집의 원리



10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.




'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

1.비슷한 문제를 풀어본 적이 있던가?



형태가 비슷하거나 관련된 문제를 풀어 본 적이 있다면 이전에 적용했던 방법과 비슷한 접근 방법을 사용할 거라고 예측할 수 있다. 따라서 기존에 접했던 문제가 온전히 경험이 되기 위해 그 원리를 완전히 이해하고 변형할 수 있어야 한다. 


2. 단순한 방법에서 시작할 수 있을까?



비슷한 문제를 본 적이 없거나, 비슷한 문제의 해법이 곧장 적용되지 않는다면 "무식하게 풀 수 있을까?"라는 질문으로 시작한다. 이렇게 만든 단순한 알고리즘에 효율적인 자료 구조를 사용하거나, 계산 과정에서 같은 정보를 두 번 중복으로 계산하지 않는 등의 최적화를 적용해서 충분히 빨라질 때까지 알고리즘을 개선하는 식으로 문제를 풀 수 있다.


3. 내가 문제를 푸는 과정을 수식화할 수 있을까?



손으로 간단한 입력, 예를 들어 문제에 주어진 예제 입력을 직접 해결해보는 것. 자신이 문제를 해결한 과정을 공식화해서 답을 만드는 알고리즘을 만들 수 있는 경우가 흔히 있고, 그렇지 못하더라도 이 과정에서 알고리즘이 어떤 점을 고려해야 하는지를 알게 된다.


4. 문제를 단순화할 수 없을까?



주어진 문제의 좀더 쉬운 변형판을 먼저 풀어보는 것. 문제의 제약 조건을 없애거나, 계산해야 하는 변수의 수를 줄일 수도 있으며, 다차원의 문제를 1차원으로 줄여서 표현할 수도 있다. 단순화된 문제의 해법이 원래 문제의 해법에 대한 직관을 제공할 수 도 있고, 이것을 직접적으로 이용해 원래 문제를 풀 수도 있다.


5.그림으로 그려볼 수 있을까?



문제에 관련된 그림을 그려 보는 것. 많은 사람들의 사고 체계는 숫자의 나열보다 기하하적 도형을 더 직관적으로 받을이기 때문.


6.문제를 분해할 수 있을까?



문제에 주어진 복잡한 조건을 더 단순한 형태를 갖는 조건의 집합으로 분해한다. 한 개의 복잡한 조건보다 여러 개의 단순한 조건이 다루기 쉽기 때문에 이 변형은 종종 유용하다. 


7.순서를 강제할 수 있을까?



순서를 뒤집는 방법의 연장선으로, 순서가 없는 문제에 순서를 강제해서 문제를 푸는 방법도 있다. 순서 강제 기법은 경우의 수를 셀 때도 유용하다. 특정 조건을 만족하는 답들의 수를 세는 문제를 흔히 볼 수 잇는데, 이때 까다로운 것은 한 가지 답을 두 가지 이상의 방법으로 만들 수 있을 때 이답들을 중복하여 세는 경우다. 



8. 특정 형태의 답만을 고려할 수 있을까?



순서를 강제하는 기법의 연장선으로 정규화 기법이 있다. 정규화란 우리가 고려해야 할 답들 중 형태가 다르지만 결과적으로는 똑같은 것들을 그룹으로 묶은 뒤, 각 그룹의 대표들만을 고려하는 방법. 




'3학년 > 알고리즘' 카테고리의 다른 글

6장 알고리즘 설계 패러다임  (0) 2018.11.22
5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15

솔직히 이해를 정확히 하고 푼 문제는 아니지만


책에 나와있는 공식이 제대로 되는 것 보고 그냥 구현만 해보았다.


맴찟 ㅠ




'3학년 > 알고리즘' 카테고리의 다른 글

5장 알고리즘의 정당성 증명  (0) 2018.11.22
문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15
백준알고리즘 15351번  (0) 2018.01.08
어거지로 푼 것 같다..


'3학년 > 알고리즘' 카테고리의 다른 글

문제 해결 전략 질문들  (0) 2018.11.16
백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15
백준알고리즘 15351번  (0) 2018.01.08
백준알고리즘 1931번  (0) 2018.01.08

평범한 재귀함수이다



'3학년 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 2294번  (0) 2018.01.16
백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15
백준알고리즘 15351번  (0) 2018.01.08
백준알고리즘 1931번  (0) 2018.01.08
백준알고리즘 1152번  (0) 2018.01.02

재밌어 보여서 해봤다


내 이름은 힘든 삶이였다.



'3학년 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 2870번  (0) 2018.01.15
백준 알고리즘 1003번  (0) 2018.01.15
백준알고리즘 15351번  (0) 2018.01.08
백준알고리즘 1931번  (0) 2018.01.08
백준알고리즘 1152번  (0) 2018.01.02
[알고리즘]최소편집거리 알고리즘  (4) 2017.11.03

다들 기초라고 하던대 나는 오래걸렸던 문제..


주요 풀이 과정은


먼저 받은 시간값들에 대해서 종료 시간을 기준으로 정렬+(종료 시간이 같다면 스타트를 빨리 하는 걸 우선)을 한 번 합니다.


그렇게 되면


1,1

1,2

2,2

2,3

3,3

3,4


같은 방식으로 시간이 들어와도 계산이 됩니다.






'3학년 > 알고리즘' 카테고리의 다른 글

백준 알고리즘 1003번  (0) 2018.01.15
백준알고리즘 15351번  (0) 2018.01.08
백준알고리즘 1931번  (0) 2018.01.08
백준알고리즘 1152번  (0) 2018.01.02
[알고리즘]최소편집거리 알고리즘  (4) 2017.11.03
[알고리즘]그리디 알고리즘  (0) 2017.10.02

'3학년 > 알고리즘' 카테고리의 다른 글

백준알고리즘 15351번  (0) 2018.01.08
백준알고리즘 1931번  (0) 2018.01.08
백준알고리즘 1152번  (0) 2018.01.02
[알고리즘]최소편집거리 알고리즘  (4) 2017.11.03
[알고리즘]그리디 알고리즘  (0) 2017.10.02
[알고리즘]분할 정복 알고리즘2  (0) 2017.09.26

코드

 

 

코드 실행 화면

 

 

코드 실행 화면을 만들기 위해 필요 없어 보이는 부분은 주석처리하고 getDistance 메소드 반환값을 void → int 형으로 만들었습니다.

 

<출처 : http://blog.naver.com/PostView.nhnblogId=ndb796&logNo=220870218783&parentCategoryNo=23&categoryNo=&viewDate=&isShowPopularPosts=true&from=search

>

 

 

 

  1. 2017.11.06 14:54

    비밀댓글입니다

  2. 2017.11.06 15:03

    비밀댓글입니다

  3. 2017.11.07 09:15

    비밀댓글입니다

  4. 자퇴할란다 2017.12.04 16:54

    초대장좀 주세요

+ Recent posts