effortDev

1. 대학교 수업시간표 짜기 문제

대학교에서 수강신청을 할 예정인데 최대한 많은 과목을 듣고 싶다.

하지만 시간이 한정적이고 시간이 겹치는 시간대에 동시에 두과목을 들을순 없다.

시간이 겹치지 않고 수강신청을 하되 가장 많이 과목을 들을수 있게 시간표를 짜고 싶다.

수강신청 가능 목록

시간이 일부 겹치기 때문에 이 수업들을 모두 듣지는 못한다.

하지만 되도록 많은 과목을 듣고싶다. 어떤과목을 신청해야 가장 많은 수업을 들을수 있을까?

1. 가장빨리 끝나는 과목을 고른다. 이 과목이 처음으로 신청해야할 과목이다.

2. 첫번쨰 과목이 끝난후에 시작하는 과목을 고르는데 마찬가지로 가장 빨리 끝나는 과목을 고른다. 

이 과목이 두번쨰로 신청해야 할 과목이다.

이런식으로 반복하면 정답을 얻을 수 있다.

자바가 오전 10시에 끝나니깐 가장 빨리 끝나는 과목이다. 자바를 먼저 신청해야 한다.

오전 10시 이후에 시작하고 가장 빨리 끝나는 수업을 다음으로 고릅니다. 안드로이드는 자바와 충돌하니까 안되고 IOS을 선택한다.

자료구조는 IOS와 충돌하니까 알고리즘을 고른다.

자바 IOS 알고리즘이 신청해야할 과목이다.

간단하다는 것 그것이 탐욕 알고리즘의 장점이다. 

각각의 단계에서 최적의 수를 찾아내면 된다.

과목 중에서 가장 빨리 끝나는 수업을 선택하는것이 목표이다.

국소최적해(locally optimal solution)을 찾음으로서

전역최적해(globally optimal solution)을 구하게 된다.

하지만 탐욕알고리즘이 항상 성공하는 것은 아니다.

2. 배낭채우기 문제

나는 탐욕스러운 도둑이다. 훔친 물건을 넣어 둘 배낭이 있는데 이 배낭은 35kg의 무게까지만 담을 수 있다.

배낭에 넣을 물건의 가격의 합을 최대한 크게 하고 싶다.

1. 가방에 들어갈 수 있는 것 중에서 가장 비싼물건을 고른다.

2. 가방에 들어갈수 있는 물건 중에 가장 비싼 것을 고른다. 

계속 반복한다.

하지만 이 알고리즘은 제대로 동작하지 않는다. 

예를 들어 내가 훔칠수 있는 물건이 3개가 있다.

배낭에는 35kg까지 들어간다. 에어컨이 30만원으로 가장 비싸니까 에어컨을 훔치면 다른것을 넣을 수 없다.

하지만 냉풍기와 자전거를 같이 훔치면 35kg이 되고 35만원이 된다.

분명히 탐욕 알고리즘은 올바른 답을 내놓지 못한다.

하지만 정답에 상당히 가까운 답이기도 하다.

3. 집합 커버링 문제

라디오 쇼를 시작했다고 가정

8개의 지역도시에 있는 모든사람에게 이 라디오 쇼를 들려주고 싶다.

하나의 방속국을 통해 청취할 수 있는 지역이 한정되어 있다.

전국에 흩어져 있는 대도시 라디오 방송국들을 방문해 라디오 쇼를 진행할 예정이다.

전국의 모든사람들이 최소한 한번은 쇼를 들을수 있도록 하려면 어떤 방송국을 방문해야 할지 계산해야 한다.

방속국을 방문하여 한번 쇼를 하는데 돈이 들기 때문에 최대한 적은 수의 방송국을 돌아야 한다.

일단 방송국 목록은 다음과 같다.

각 방송국 마다 커버할수 있는 지역이 서로 다르고 겹치는 지역이 있을 수도 있다.

8개의 지역도시 전체를 커버하는 가장 적은 수의 방송국의 집합은 어떻게 구해야 할까? 

1. 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 상관 없다.

2. 모든 도시에 방송이 될때까지 선택을 반복한다.

이것이 근사 알고리즘이다.

정확한 답을 계산하는데 시간이 너무 많이 걸린다면 근사 알고리즘을 사용할 수 있다.

근사알고리즘의 성능은 

1. 얼마나 빠른가?

2. 최적해에 얼마나 가까운가?

두가지로 판단한다.

탐욕 알고리즘은 다루기 간단할 뿐더러 그 단순함으로 인해 실행속도가 빠르기 때문에 좋은 선택이 될수 있다.

1. 파이썬의 set과 집합 표현

2. 근사 알고리즘을 사용한 집합 커버링 방송국 방송하기 구현

집합 커버링 문제를 풀기 위해서는 가능한 모든 집합을 계산해야 한다.

approximation1.py

다익스트라 알고리즘

1. 너비우선탐색 vs 다익스트라 알고리즘

이전 포스트에서 김포공항에서 마포대교까지 가는 가장 빠른길이 아닌 가장 짧은길, 즉 최단경로를 구했다.

가장 적은 수의 구간을 지나긴 하지만 구간을 지날때마다 시간을 측정해보면 더 빠른 경로가 있을 수 있다.

가장 빠른경로를 찾고 싶다면 어떻게 해야 할까?

다익스트라 알고리즘을 사용하면 최단시간 경로를 구할 수 있다.

다익스트라 알고리즘을 사용해서 출발점에서 도착점으로 가는 가장 최단시간 경로를 구해보겠다.

다익스트라 알고리즘의 4단계

1. 가장 가격이 싼 정점을 찾는다. 가장 가격이 싼 정점은 도달하는데 시간이 가장 적게 걸리는 정점을 말한다.

2. 이 정점의 이웃정점들의 가격을 조사한다. 

이 정점의 이웃정점에 대해 현재의 가격보다 더 싼 경로가 존재하는지 확인한다. 만약 존재하면 가격을 수정한다.

3. 그래프 상의 모든 정점에 대해 이러한 일을 반복한다.

4. 최종경로를 계산한다.

정점 B의 모든 이웃 정점에 대해 정점 B를 통과하여 정점 A에 도달하는데 걸리는 시간 계산한다.

정점 A로 가는 더 짧은 거리 (6분에서 5분으로 수정)

도착점까지 가는 더 짧은 거리 (무한대에서 7분으로 수정)

정점 B에 도달하는데 2분 걸린다.

정점 A에 도달하는데 5분 걸린다.

도착점에 도달하는데 6분 걸린다.

그래프의 각 간선은 어떤 숫자값을 가지는데 이 숫자를 가중치라고 한다.

가중치를 가지는 그래프를 가중그래프(weighted graph)

가중치가 없는 그래프를 균일그래프(unweighted graph) 라고 한다.

다익스트라 알고리즘은 방향성 비순환그래프 또는 사이클을 가진경우 가중치가 양수일때만 적용된다.

3개의 해시테이블을 사용해 구현하기

graph.pptx

dikstra_graph.py

1. 해시함수의 예 :

식료품 가게에 오늘 첫 알바를 시작했다.

손님이 물건을 사러오면 모든물건의 가격이 적혀있는 가격장부의 가격을 찾아봐야한다.

가격장부가 알파벳순서로 되어있지 않다면 모든가격을 하나씩 살펴봐야한다.

장부가 알파벳순서로 되어 있다면 이진탐색을 써서 apple가격을 찾을수 있고 이 경우 log n 시간이 걸림.

알파벳 순서로 되어 있지 않다면 단순탐색을 써야하므로 n 시간이 걸림

그런데 장부가 정렬 되어 있다하더라도 계속 물건에 대한 가격을 알려고 장부를 봐야한다면 힘이 든다.

가격을 찾고 있는 동안 손님이 밀려온다. 모든 물건의 이름과 가격을 알고 있는 동료가 있다면 장부따위를 찾아볼 필요가 없다.

동료에게 물어보면 바로 대답해주니깐

동료인 철수는 모든 항목에 대해 O(1) 실행시간 만에 가격을 알려준다. 가격장부의 리스트가 아무리 많아도 상관 없다. 

그리고 이진탐색보다 빠르다.

가격장부를 배열로 구현할수 있다.

배열에 있는 각각의 항목은 두개의 항목으로 이루어짐 

하나는 물건의 이름, 하나는 가격이다.

해시함수를 사용하면 된다.

2. 해시함수란?

해시함수는 문자열을 받아서 숫자로 반환하는 함수이다.

해시함수는 문자열에 대해 숫자를 할당합니다.

해시함수는 일관성이 있어햐 한다. 

apple을 넣었을때 4를 반환한다면 apple을 넣을때마다 반환되는 값은 항상 4이어야 한다.

그렇지 않으면 해시함수로의 역할을 할 수 없다.

다른단어가 들어가면 다른숫자가 나와야 합니다. 

예를 들어 어떤 단어를 넣어도 1만 나온다면 좋은 해시함수가 아니다.

가장 좋은 경우는 서로 다른 단어에 대해 모두 서로 다른숫자가 나와야 한다.

해시 함수는 문자열에 대해 숫자를 할당하는 것이다.

해시함수에 apple을 넣는다. > 해시함수는 3을 반환한다.

apple의 가격은 배열의 3번 인덱스 위치에 저장합니다.

해시함수에 milk을 넣는다. > 해시함수는 0을 반환한다.

milk의 가격은 배열의 0번 인덱스 위치에 저장합니다.

4. 너비 우선 탐색

너비우선탐색을 사용하면 두항목간의 최단경로를 찾을 수 있다.

4.1 너비우선탐색을 사용( 김포공항 ~ 마포대교 )

그래프 알고리즘을 사용한다.

김포공항에서

1단계로 갈수 있는 곳은 100번 버스타기와 200번 버스타기이다.

2단계로 갈수 있는 곳은 지하철타기, 201번 버스타기, 202번 버스타기 이다.

3단계로 갈수 있는 곳은 마포대교, 지하철타기 이다.

알고리즘을 통해 마포대교까지 최단경로가 3단계라는 것을 알게 되었다.

최단 경로 문제(shortest-path problem) 라고 한다.

즉 가장 짧은 것을 찾아야한다.

1. 문제를 그래프로 모형화한다.

2. 너비우선탐색으로 문제를 푼다.

4.2 너비우선탐색을 사용( 지팡이 사기 )

나는 지팡이를 사려고 한다.

누가 지팡이를 가졌는지 확인해봐야한다.

질문 1. 정점 A에서 정점 B로 가는 경로가 존재하는가?( 지팡이를 판매하는 사람이 있는가? )

질문 2. 정점 A에서 정점 B로 가는 최단경로는 무엇인가?( 누가 가장 가깝게 지팡이를 파는가? )

1촌 관계부터 확인해야한다.

내가 지팡이를 사기위해서는 해리, 해르미온느, 론 부터 먼저 지팡이를 파는지 확인해야 한다.

너비우선탐색은 단순히 A에서 B로 가는 경로를 찾는것이 아닌 최단경로를 찾을 수 있다.

파이썬 코드

1. 확인할 사람의 명단을 넣을 큐를 준비

2. 큐에서 한 사람을 꺼낸다

3. 이사람이 지팡이 판매자인지 확인한다.

4. if 지팡이 판매자가 맞다면 end

   else 지팡이 판매자가 아니라면 그 사람의 이웃을 모두 큐에 추가한다.

론부터 시작해서 론이 지팡이 판매자가 아니면 론의 이웃 지니를 추가한다.

론 > 해리 > 해르미온느 > 지니 > 볼드모트가 나오게 된다.

graph.pptx

bfs.py

퀵정렬은 분할정복전략이다.

배열이 비어있거나 원소가 하나인 배열은 정렬할 필요가 없다.

원소가 2개이면 ex) 40 10 -> 10 40

첫번째 원소와 두번째 원소를 비교해 교환한다.

원소가 3개이면  

ex) 40 20 10 

배열에서 원소 하나를 고른다. 고른원소는 기준원소(pivot)라고 한다.

( 40 pivot 지정 )

기준원소(pivot)를 기준으로 기준원소보다 작은원소와 큰원소를 분류한다.

( 40보다 작으므로 왼쪽으로 분류 20 10 40 )

기준원소보다 작은숫자로 이루어진 하위배열 [20, 10]

기준원소 [40]

기준원소보다 큰 숫자들로 이루어진 하위배열 []

1. 기준원소 고른다.

2. 배열을 기준 원소보다 작은원소의 배열과 기준원소보다 큰 원소의 배열 두개의 하위배열로 분할

3. 하위배열에 대해 재귀적으로 퀵정렬 호출

1. 퀵정렬 소스코드

작업파일

quickSort.pptx

quickSort.py

100개의 아이템이 있는데 이것들 중 어떤 1개를 찾으려고 한다.

1. 단순탐색이란?

100개의 아이템이 있다면  > 100번의 추측을 통해  아이템을 찾을 수 있다.

추측해야할 최대횟수가 리스트길이와 같으면 선형시간(linear time)이다.

2. 이진탐색이란?

100개의 아이템이 있다면 > 7번의 추측을 통해 아이템을 찾을 수 있다.

40억개의 아이템 > 32번 추측

한번의 하나의 네모칸 그리면 16번 그려야하지만

종이를 반으로 접고 접은 것에 다시 접고 또 접고 4번의 연산으로 16개의 네모칸을 만들었다.

ex 2) 정렬되지 않은 이름노트에 sanghyun 이라는 이름을 찾는다고 해보자.

sanghyun 이라는 이름을 찾는다면 맨앞에 나올수 있고 맨 뒤에 나올수 있다.

맨앞에 나오면 O(1) 로 바로 끝나지만 최악인 경우 모든 이름을 다 확인해 맨뒤에서 찾을 경우 O(n)이 걸린다.

3. 빅오표기법이란?

빅오O를 붙이고 수행시간에 대해 명시한것이다.

빅오표기법은 최악의 경우에 대한 것이다. 최악의 경우보다 느려지지 않는다는 보장하는 것을 말한다.

빅오실행시간의 예

O(log n) 로그시간 : ex) 이진탐색

O(n) 선형시간 : ex) 단순 탐색

O(n*log n) : ex) 퀵 정렬(빠름)

O(n^2) : ex) 선택정렬(느림)

O(n!) : ex) 외판원 문제(정말 느림)

3.1 외판원 문제

미국 중국 한국 캐나다 일본을 여행한다고 한다.

가장 짧은 거리를 통해 다섯개 국가의 수도를 모두 방문하고 싶다.

이 국가들의 수도를 방문하려면 총 몇가지가  있을까?

도시를 방문하는 모든 경로를 살펴봐야한다.

그 다음 전체 거리를 더해서 가장 짧은 경로를 택하면 된다.

도시가 5개이면 120가지 경우가 있다.

5! = 5*4*3*2*1 = 120

6개일 경우

6! = 6*5*4*3*2*1 = 720

7개일 경우 5040개이다.

알고리즘의 속도는 시간이 아니라 연산횟수가 어떻게 증가하는지로 측정한다.

4. 배열과 리스트

메모리에 무언가를 저장할때 마다 컴퓨터에게 공간을 요청한다.

여러개의 원소를 저장해야 한다면 배열과 리스트 중 하나를 사용한다.

배열과 리스트는 장단점이 있다.

극장에서 2명이 영화를 보러갔는데 친구 1명이 추가되어 3명이 되었다. 

2명 자리 옆에는 다른사람이 앉아 있어서 추가된 친구 1명과 같이 나란히 3명이 앉을수 없다.

이런경우 컴퓨터에게 3개의 자리가 있는 다른 메모리공간을 요청한다. 그리고 3명의 자리로 옮겨야 한다.

만약 또다른 친구가 오게 되면 4명이 되고 자리가 모자라 전원이 같이 다른자리로 이동해야 한다.

공간이 모잘라서 매번 모든 원소를 메모리의 새로운 위치로 옮긴다면 배열에 원소를 추가하는 작업이 느려진다

이것을 고칠수 있는 방법은 좌석을 미리 예약하는 것이다.

4.1 배열의 단점

1. 그래서 원래는 친구 2명이서 영화를 본다고 했지만 앞으로 친구를 만날 가능성이 있으니 

컴퓨터에게 10개의 자리를 요청한다.

그러면 전체 배열을 옮기지 않아도 10개까지는 추가할수 있다.

2. 하지만 추가할일이 생기지 않는 다면 메모리를 쓸데없이 낭비하게 된다.(다른사람도 자리를 이용못하고 예약한 사람도 사용안하기 떄문)

목록의 크기가 10개보다 커진다면 자리를 옮겨야 한다.

이러한 문제점으로 연결리스트를 사용한다.

4.2 연결리스트의 장점

1. 원소를 추가할때 생기는 문제를 해결할수 있다.

연결리스트를 사용하면 원소를 메모리 어느곳에나 둘수 있다.

각 원소에는 목록의 다음원소에 대한 주소가 저장되어 있다.

2. 여러가지 임의의 메모리 주소들이 하나의 목록으로 연결되어 있는 것이다.

연결리스트를 사용하면 원소를 추가하는 일이 쉽다.

3. 그냥 메모리 아무곳에나 원소를 넣고 그 주소를 바로 앞의 원소에 저장해 놓으면 된다.

연결리스트를 사용하면 원소를 옮길 일이 없다.

4. 영화를 보러 5명이 갔는데 붙어서 볼수 있는 자리 5자리가 없다.

배열 10000개 중 10000개 공간에 있기는 하지만 모두 이어진 10000개 자리는 없을수도 있다.

그러면 배열을 만들수 없다.

하지만 연결리스트를 사용한다면 일단 흩어져서 영화를 보자 배열을 만들 공간은 없어도 

연결리스트를 만들 공간은 있는 것입니다.

원소를 추가하기에는 연결리스트가 좋다면

배열이 연결리스트보다 나은점은 읽기이다.

4.3 리스트에 가운데에 삽입하기

원소를 배열이나 리스트의 중앙에 삽입한다면 배열과 리스트 중 어느 것이 나을까?

배열은 다음에 오는 모든 원소의 위치를 바꿔야함.

공간이 부족하면 모든 원소를 새로운 장소로 복사해야 한다.

중간에 원소 삽입은 리스트가 나음.

4.4 삭제하기

이전 원소가 가르키는 위치만 바꾸면 되기 때문에 리스트가 낫다

배열에서는 원소하나만 삭제하고 싶을때도 모든 것을 다 옮겨야 한다.

4.5 배열과 리스트 중 어떤것을 많이 사용하나?

임의의 원소에 접근하는 것이 가능하기 때문에 배열을 쓰는 경우가 많다.

연결리스트는 순차접근(sequential access) 밖에 할수 없다.

연결리스트에 있는 10번째 원소를 읽으려면 그 앞에 9개 원소를 모두 읽어서 10번째 원소로 가는 링크를 찾아내야 한다.

임의접근은 10번째 원소로 바로 건너뛸수 있다.

5. 선택정렬

컴퓨터 음악이 가장 많이 들은것부터 정렬하고 싶다.

1. 리스트의 모든항목을 살펴보고 가장 많이 연주된 가수를 찾아 새로운 리스트에 기록

2. 그다음으로 많이 들은 가수를 찾아 반복한다.(계속 반복하면 정렬된 목록 얻을수 있다)

단순검색 가수목록에서 가수를 한명씩 찾아 봄 O(n)

연주횟수가 가장 많은 가수를 찾기 위해서는 목록의 모든항목을 점검 O(n)

O(n) * O(n) = O(n^2)

선택정렬 알고리즘은 전화번호부의 이름, 여행날짜, 이메일(최신받은 이메일부터) 이 있다.

이 정렬을 사용해서 작은 정수부터 큰 정수까지 정렬하는 선택정렬 코드를 작성해보자.

코드는 파이썬으로 작성하였다.

1. 선택정렬 코드

2. 파이썬의 range 함수 예제

6. 재귀

1. 재귀 함수의 기본적인 호출

2. 재귀 함수의 스택 팝 과정 보기

함수안의 함수를 호출하면 컴퓨터는 메모리상자 stack을 사용해 쌓아간다.

함수가 반환되면 pop연산으로 없어진다.

3. 재귀 함수 활용하여 팩토리얼 사용하기

자기 자신인 fact 함수를 계속 부르며 스택을 쌓고 난뒤

값을 반환(pop)하며 값을 구하고 있다.

fact(1) =1

x*fact(1) = 1

x*fact(2) = 2*1 = 2

x*fact(3) = 3*2 = 6

x*fact(4) = 4*6 = 24

x*fact(5) = 5*24 = 120

소스와 작업파일

recursionFunction1.py

selectionSort.py

callStack.pptx

기본적인 알고리즘 문제 풀기 - 2

문제 4. 

앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.

두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.

세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?

출력결과

문제 5.

1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.

그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까? 

접근방법 5-1. if문 중첩방법

출력결과

접근방법 5-2. 메소드 호출방법

출력결과

문제 6. 

1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).

1^2+2^2+3^2+4^2+5^2+6^2+7^2+8^2+9^2+10^2

1+4+9+16+25+36+49+64+81+100 = 385

1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).

(1 + 2 + ... + 10)^2 = 552 = 3025

따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.

그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?

출력결과

기본적인 알고리즘 문제 풀기

문제 1. 

10보다 작은 자연수 중에서 3 또는 5의 배수는 3, 5, 6, 9 이고, 이것을 모두 더하면 23입니다.

1000보다 작은 자연수 중에서 3 또는 5의 배수를 모두 더하면 얼마일까요?

출력결과

문제 2.

피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까? 

출력 결과

문제 3.

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.

예를 들면 13195의 소인수는 5, 7, 13, 29 입니다. // 1, 2, 3, 5, 7, 11

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

출력 결과

사용자로부터 문자열을 입력받아 문자열을 거꾸로 출력해본다.

접근방법

1. 사용자로 부터 문자열 입력받기 위한 scan사용

2. 사용자로 부터 문자를 받아 저장할 변수, 거꾸로 문자열을 저장할 변수, 받은 문자열의 길이를 저장할 변수 선언

3. 받은 문자열 길이를 저장할 변수 - 1을 하여 charAt(index)로 접근한다.

4. 길이만큼 반복하며 거꾸로 저장한다.

출력 결과

마지막으로 소스를 첨부한다.

reverseChar.java