옌의 로그

문제 [백준] 주유소 (Olympiad > 한국정보올림피아드 > KOI 2016 > 중등부 2번) 사용 알고리즘 - 그리디 (Greedy) 해결방법 마을이 일직선 상에 있다는 것이 포인트 한 마을에서 다음 마을로 이동하기 전에 가장 저렴한 주유소를 저장해 두고 해당 주유소에서 주유한 뒤 이동한다 매 번 마을에 도착할 때마다 최소 주유비에 다음 이동 거리를 곱해서 경비를 구해야한다 예제 1의 경우 각 마을의 주유비가 [5, 2, 4, 1] 이다. 이 때 이동할 때마다 그리디 하게 주유비를 선택한다고 하면 다음과 같다. i 현재 주유비 최소 주유비 이동 거리 경비 0 5 5 2 10 1 2 2 3 6 2 4 2 1 2 소스코드 사용언어 : C++ #include #include using namespace..

문제 [백준] 풍선 공장 사용 알고리즘 - 이분 탐색 해결방법 스텝별로 실시간 누적 작업시간을 담는 우선순위 큐를 활용한다 우선순위 큐에 pair를 삽입한다. 이렇게 하면 가장 작업이 빨리 끝나는 스태프가 항상 top 에 위치하기 때문에, 해당 스태프를 Pop 한 뒤, 작업을 할당해서 다시 push 해주면 된다. 예제 1을 살펴보면, 가장 빠르게 풍선 1개를 완성한 (3, 3) 스태프를 Pop 하고, 해당 스태프에게 작업을 한 번더 할당한 뒤 (6, 3) 을 push 해준다. 그 다음으로 빠르게 풍선 1개를 완성한 (5, 5) 스태프를 pop하고, 일을 할당한 뒤 (10, 5)를 push 한다. 그 다음으로 빠르게 풍선 1개를 완성한 (6, 3) 스태프를 pop하고, 일을 할당한 뒤 (9, 3)를 pu..

문제 [백준] 사탕 게임 (Olympiad > Croatian Highschool Competitions in Informatics > 2012 > Junior Croatian Olympiad in Informatics - Exam #1 ) 사용 알고리즘 - 브루트포스 (Brute Force) 해결방법 이 문제의 핵심은, 바꾼 사탕이 위치한 행, 열 만 탐색하는게 아닌, 전체 보드판을 다 탐색해야 한다는 것 ! 예제 2번을 살펴보면, C(1,0), Y(1,1) 두 사탕을 swap 한 후 (0,0) 부터 행방향 탐색을 했을 때, [P, P, P, P] 로 연속한 N개의 사탕이 확인되므로 탐색이 종료된다. 보드판의 (0,0)부터 마지막 사탕까지 쭉 반복문을 돌면서, 인접한 사탕 (가로 방향, 세로 방향) 을..

문제 [백준] IF문 좀 대신 써줘 사용 알고리즘 - 이분 탐색 (Binary Search) 해결방법 입력받은 전투력 배열(level_num)을 이분탐색으로 탐색한다. 예제 2에서 살펴보면 다음과 같은 흐름으로 계산된다 더보기 99가 입력되었을 때 lv : 99 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) right => 0 (mid - 1) left : 0, right : 0 mid : 0 level_num[mid] : 100 (B) right => -1 (mid - 1) level_name[mid] : B . . . lv : 101 left : 0, right : 3 mid : 1 level_num[mid] : 100 (A) left => 2 (mi..

문제 [백준] 크림 파스타 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 dp[A배열 원소 개수] = (최대값 - 최소값)의 최대값 A배열에 값이 들어올 때 마다 A의 원소중 최소값과 비교해 최소값을 체크해준다. 들어온 값 - 최소값 과 dp[i-1]을 비교해 더 큰 값을 dp[i]에 기록해준다. A 배열에 원소가 들어올 때마다의 상황을 표로 나타낸 것 50이 들어왔을 때 원소 중 최소값 : 50 input 값과 최솟값의 차 : 0 50이 들어오기 전까지 가장 (최대값-최소값)의 최대값 : 0 dp[1] = 0 100이 들어왔을 때 원소 중 최소값 : 50 input 값과 최소값의 차 : 50 (100-50) 100이 들어오기 전까지 가장 (최대값-최소값)의 최대값 (= d..

문제 [백준] 설탕 배달 (Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #7 1번) 사용 알고리즘 - 동적계획법 (Dynamic Programming) 해결방법 동전으로 금액을 만드는 문제와 같다고 보면 된다. > 3과 5를 가지고 N키로 만들기 $dp[N] = 사용한 최소 동전(설탕 봉지) 수 $dp 배열을 0으로 초기화 해준 뒤 반복문을 돌면서 채워주면 되는데, 이 때 3, 5 번째는 각 각 1개의 봉지 만으로 만들 수 있기 때문에 1로 갱신, 4의 경우 만들 수 없는 숫자기 때문에 0으로 갱신해준다. $dp[$i-3], $dp[$i-5] 의 값이 모두 있는 경우 (0보다 큰 경우) 최소 값에 1을 더해주면..

문제 [프로그래머스] 호텔 대실 사용 알고리즘 - 그리디 (Greedy) 해결방법 키 포인트는 다음 2가지 시간 데이터를 분으로 변경 입실 시간을 기준으로 정렬 퇴실 시간을 담는 배열을 통해 필요한 방의 개수를 count 입실 시간을 기준으로 정렬한 배열 sortedT를 가지고 반복문을 돌며, 해당 순서 사람의 끝나는 시간을 finishT 배열에 담는다. finishT 배열은 항상 빠른 시간이 앞에 오도록 오름차순 정렬을 해주고, 반복문이 돌때마다 현재 순서 사람의 입실 시간과 finishT 배열의 가장 빠른 퇴실 시간을 비교해, 퇴실시간이 더 빠른 경우 그 방에 사람을 받을 수 있다는 뜻이므로 finishT 배열에서 해당 시간을 제거한다. finishT에 담기는 데이터를 순서대로 보면 다음과 같다. f..