FOSCAR 알고리즘 스터디 2주차 2조 블로깅
구성 :
1) 그리디 알고리즘
2) 구현
3) 문제 리뷰
1) 그리디 알고리즘
12강 ~ 13강
https://www.youtube.com/watch?v=5OYlS2QQMPA&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=12
https://www.youtube.com/watch?v=_TG0hVYJ6D8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=13
- 그리디 알고리즘(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법.
- 일반적인 그리디 알고리즘은 문제 해결을 위한 최소한의 아이디어를 떠오르는 능력을 요구.
- 그리디 해답법은 정당성 분석이 중요하다 ! ( 문제에서 요구하는 최적의 해를 구할 수 있는지.. )
하지만
- 그리디 알고리즘은 일반적 상황에서 최적의 해를 보장 못하는 경우가 많다.
- 대다수 코딩 테스트에서는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 한다.
즉
그리디 알고리즘 문제는 문제 풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토할 수 있어야 한다.
2) 구현
14강 ~ 15강
https://www.youtube.com/watch?v=puH2p1CQEg4&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=14
https://www.youtube.com/watch?v=QhMY4t2xwG0&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=15
- 구현이란, 머릿속의 알고리즘을 소스코드로 변환하는 과정이다.
- 주된 구현 유형의 문제 : 풀이를 떠올리는 것은 쉬우나, 소스코드로 옮기는 것이 어려운 문제들..
ex) 알고리즘은 간단하나 코드가 지나치게 길어지는 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제
- 적절한 라이브러리를 찾아 사용해야 하는 문제
- 일반적으로 알고리즘 문제에서 2차원 공간은 행렬(Matrix)의 의미로 사용됨.
- 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됨.
3) 문제리뷰
3-1) 우유 축제
https://www.acmicpc.net/problem/14720
14720번: 우유 축제
영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후
www.acmicpc.net
- 딸기우유가게 : 0 , 초코우유가게 : 1 , 바나나우유가게 : 2
- 딸기우유 -> 초코우유 -> 바나나우유 -> 딸기우유 순서로 진행되어야 한다.
- 즉, 가게 번호가 0일때 카운트, 가게 번호가 1일때 추가 카운트 ( 0다음 가게 번호가 2일 경우 카운트 X)
- 따라서 이전 가게 번호가 몇 번이었는지 계산하는 것이 중요 !
- 처음 가게는 0 이여야 하므로, data 첫번째 요소를 0으로 설정해야 cnt 가 증가
- 그리고 cnt 값은 1이 되고, 그 다음 data 요소가 1이여야 cnt 가 증가한다.
- data 요소가 2가 되면, 다음 data 요소가 2가 되어야 cnt 가 증가한다.
- data 요소가 3가 되면, 다음 data 요소가 0가 되어야 cnt 가 증가한다.
- data 요소가 4가 되면, 다음 data 요소가 1가 되어야 cnt 가 증가한다....
따라서 3으로 나눴을 때, 나머지 연산을 사용하는 것이 유리하다.
3-2) 욱제는 효도쟁이야!!
https://www.acmicpc.net/problem/14487
14487번: 욱제는 효도쟁이야!!
욱제는 KOI를 망친 기념으로 부모님과 함께 코드게이트 섬으로 여행을 떠났다. 코드게이트 섬에는 오징어로 유명한 준오마을(심술쟁이 해커 임준오 아님), 밥으로 유명한 재훈마을, 영중마을 등
www.acmicpc.net
- 주어진 데이터들은 현재 위치로 부터 각각의 마을까지 도달하는 비용을 의미
- 따라서 최대 비용을 지불해야 하는 지역을 제외한 전체의 합을 구하면 된다.
3-3) 피로도
https://www.acmicpc.net/problem/22864
22864번: 피로도
첫 번째 줄에 네 정수 $A$, $B$, $C$, $M$이 공백으로 구분되어 주어진다. 맨 처음 피로도는 0이다.
www.acmicpc.net
- 입력 받는 변수
A : 쌓이는 피로 / B : 일의 양 / C : 회복되는 피로 / M : 최대 허용 피로도
- 만약 한 시간을 일했다고 할때, 현재 피로도가 최대 허용 피로도 수치에 도달하지 않는다고 하면
- 한 시간 일을 더 한다.
- 이 과정을 반복하다, 피로도가 최대 피로도의 한계수치보다 커지게 될 경우 휴식을 취해준다.
3-4) 라디오
https://www.acmicpc.net/problem/3135
3135번: 라디오
첫 줄엔 정수 A와 B가 주어진다 (1 ≤ A, B < 1000, A ≠ B). 다음 줄엔 정수 N이 주어진다 (1 ≤ N ≤ 5). 다음 N개의 줄엔 미리 지정되어 있는 주파수가 주어진다 (주파수는 1000 보다 작다).
www.acmicpc.net
- 첫번째 버튼은 주파수를 1 증가시키고, 두번째 버튼은 주파수를 1 감소시킨다.
- 나머지 N개의 버튼은 즐겨찾기 기능으로써, 미리 지정된 주파수로 이동한다.
- 현재 주파수 A와, 듣고 싶은 주파수 B가 주어질 때,
- 주파수 A에서 B로 갈 때 필요한 가장 적은 버튼의 수
- 즐겨찾기 메뉴와 B사이의 차이가 최솟값일 때, 그때의 즐겨찾기 메뉴를 클릭한다.
i) 메뉴를 경유하여 B에 도달할 때
- B의 주파수가 음수이면 두번째 버튼 (주파수를 1증가)을 반복해서 클릭하여 B에 도달한다.
- B의 주파수가 양수이면 첫번째 버튼 (주파수를 1감소)을 반복해서 클릭하여 B에 도달한다.
ii) 메뉴를 경유하지 않고 B에 도달 할때
(A - B)가 (즐겨찾기 - B) 보다 작은 경우, 첫번째 혹은 두번째 버튼을 통해 바로 이동한다.
- 메뉴 B와 최소거리인 즐겨찾기 탐색
- A에서 바로 B로 이동할 것인지, 혹은 즐겨찾기를 경유하여 이동할 것인지 파악한다.
'FOSCAR-(Autonomous Driving) > 알고리즘 스터디' 카테고리의 다른 글
| [2023 알고리즘 스터디] 4조 이은선 2주차 - 백준 11508, 19941, 16953, 1080 (1) | 2023.02.05 |
|---|---|
| [2023 알고리즘 스터디] 1조 안세홍 2주차 - 백준 14720, 14487, 22864, 9237 (2) | 2023.02.05 |
| [2023 알고리즘 스터디] 5조 #2주차 - 그리디 (1) | 2023.02.04 |
| [2023 알고리즘 스터디] 1조 오현민 #1주차 - 백준 10870, 2525, 1712, 4673 (1) | 2023.01.29 |
| [2023 알고리즘 스터디] 4조 #1주차 - 백준 3085번(사탕 게임), 24954번(물약 구매) 문제 풀이 (2) | 2023.01.29 |
