Algorithm66 [백준] 2156 포도주 시식 c++ 문제 링크 https://www.acmicpc.net/problem/2156 KEY [백준] 계단오르기와 상당히 유사한 문제이다. 계단오르기 문제는 항상 연속 몇칸이상을 못간다는 등의 제약조건이 있다. 지금 이 문제 또한 연속 3잔의 포도주를 마실 수 없다는 조건이 있으므로, 현재 시점에서 구할 수 있는 최댓값의 후보를 파악하는 것이 중요하다. 후보는 다음과 같다. 후보1) i-3번째 잔까지의 최댓값 + i-1번째 잔 + i번째 잔 후보2) i-2번째 잔까지의 최댓값 + i번째 잔 후보3) i-1번째 잔까지의 최댓값 다음 후보들 중 최댓값을 구하면 되는 문제이다. 두 문제의 차이점 계단오르기 문제는 지금 칸의 점수를 무조건 포함해야 하기 때문에 후보3이 없어야 한다. 하지만 지금 이 문제의 경우 자신을 .. 2022. 2. 16. [백준] 1912 연속합 c++ 문제 링크 https://www.acmicpc.net/problem/1912 KEY i-1번째까지의 수열의 합에 i번째 숫자를 더해도 i번째 숫자보다 작다면 차라리 i번째 숫자부터 다시 세는 것이 낫다. 수열 {10, -4, -9, 8}로 예를 들어보자. 처음은 10이다. 최댓값은 10 그대로일 것이다. 두번째 -4로 왔다. 최댓값은 (10-4)와 -4 둘 중에 큰 6이 된다. 세번째 -9로 왔다. 최댓값은 (6-9)와 -9 둘 중에 큰 -3이 된다. 마지막 8이다. 최댓값은 (-3+8)와 8 둘 중에 큰 8이 된다. 이렇게 완성된 최댓값을 저장한 배열은 {10, 6, -3, 8}이고, 정답은 이 중 최댓값인 10이다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 2022. 2. 15. 백준 1149 RGB거리 문제를 보자마자 2학년때 수업시간에 배웠던 내용이 떠올랐다. 이틀연속으로 같은 식당에서 먹지 않고 8일간 식사를 하는데 드는 최소비용을 구하는 것이다. 단순히 "현재 최소비용을 택하면 되겠지" 하면 틀린다. 같은 식당이 2일 연속나오면 안되므로, 택해야 되는 시점이 현재라면 어제의 것을 고려해야한다. 따라서 해결방법은, 어떤시점 에서 식당A를 선택하면서 끝났다고 할때, 식당 B 혹은 식당C를 선택하면서 끝났다고 할때, 각각의 최종값에서 가장 최소비용이 되는 것을 택하면 된다. 위 식당의 문제를 예를 들어보면, 2일차가 됐을때의 최소값은 C->A, A->C의 7이다. 3일차가 됐을 때의 최소값은 B->A->C (혹은 C->A->C)의 9이다. 이런식으로 8일째 세 식당에서 밥을 먹은 경우 중 누적비용이 가.. 2022. 2. 15. 백준 11403 경로찾기 플로이드 와샬알고리즘을 이용해서, 경로 i -> k와 k -> j 가 존재한다면, 경로 i -> j도 존재하도록 하는것이 핵심이다. 플로이드-와샬? 모든 정점에서 모든 정점으로의 최단 경로를 구하고 싶다면 플로이드 와샬 알고리즘을 사용해야 한다. Key point는 '거쳐가는 점'을 기준으로 최단거리를 구하는것! 플로이드 와샬은 다이나믹 알고리즘을 사용한다. 자세한 설명은 아래 사이트를 참고하였다. https://blog.naver.com/ndb796/221234427842 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 2022. 2. 5. 백준 1260 DFS와 BFS DFS와 BFS를 구현하는 문제이다. DFS의 경우 DFS(깊이우선탐색)은 자기자신을 호출하는 순환알고리즘의 형태를 갖는다. 재귀를 이용해서 구현!! 1번 노드에 인접한 모든 노드들에 대해서 간선이 있고, 방문하지 않았던 지점이라면 방문한다. 같은 방식으로 n개의 노드에 대해서 진행. BFS의 경우 BFS(너비우선탐색)은 재귀적으로 동작하지 않는다. 일반적으로 큐를 사용해서 반복적으로 구현한다. Prim, Dijkstra알고리즘과 유사하다. 큐를 이용해서 구현!!(FIFO방식) 1번노드에 인접한 모든 노드들에 대해서 간선이 있고 방문하지 않았던 지점이라면 방문하여 큐에 넣는다. 큐가 empty가 될 때까지 반복해서 진행. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17.. 2022. 2. 3. [백준] 11000 강의실 배정 c++ 문제 링크 https://www.acmicpc.net/problem/11000 풀이 방법 먼저 시작하는 회의 순으로 정렬한다. 회의가 끝나는 시간을 저장하는 우선순위 큐(pq)를 하나 만든 후, 맨 앞의 회의가 끝나는 시간을 저장한다. 지금 회의가 pq의 top이후에 시작한다면(같은 회의실을 사용할 수 있다면) pq의 top을 꺼내고, 지금 회의의 끝나는 시간을 pq에 push한다. 그게 아니라면(다른 회의실을 사용해야 한다면) 회의가 끝나는 시간을 pq에 push한다. 모든 회의를 순회했을 때 결국 pq의 size가 회의실 갯수가 될것이다. 구현은 어렵지 않았으나 풀이 방법이 생각이 안나서 굉장히 까다로웠던 문제였다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 .. 2022. 2. 2. 이전 1 ··· 7 8 9 10 11 다음