pinevienna blog

각 묶음의 카드의 수를 A, B라 하면 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다 N개의 숫자 카드 묶음의 각각의 크기가 주어질 때, 최소한 몇 번의 비교가 필요한지를 구하는 문제 멍청하게 풀면 틀리는 문제.. 그래서 바로 내가 틀린 문제 이렇게 정렬해서 싹 더하면 안되나? 했는데 당연히 안된다 항상 제일 작은 값 두개를 더해나가야 최솟값을 얻을 수 있다 3+3=6은 옆에 4, 5보다 크니까 일단 킵 해둬야 한다 4+5=9는 6보다 크니까 킵해두고 6끼리 더하고.. 그리고 9+12=21로 비교가 끝난다 총 비교 횟수는 51로, 앞서 한 번 정렬하고 순서대로 더했을 때 나온 55보다 작다 좀만 생각하면 될걸 꼭 한번 틀리고 간다 정신차려 솔빈아^^~~ 암튼 이걸 어떻게 구현하느냐..

연속하는 P일 중, L일 동안만 캠핑장을 사용할 수 있다 V일짜리 휴가 중 며칠동안 캠핑장을 사용할 수 있는지 출력하는 문제 으음 그냥 (v/p)*l + (v%p) 이렇게 하면 안돼~~? 했다가 틀렸다 제공된 입력값으로만 테스트하고 제출했다가 틀리기 1등^^! 만약 l=5, p=8, v=15 라면 (v/p)*l + (v%p) 에 대입했을 때 12라는 오답이 나온다 (답 : 10) 좀만 생각하면 당연한건데 생각을 하다 말고 제출해버림 암튼 이걸 해결하려면 + 뒤에 (v%p)를 고쳐야한다 이 나머지가 만약 l보다 크다면 l을 더해주고, l보다 작다면 v%p를 더해주면 된다 12345678910111213141516171819#include #include using namespace std; int main..

Depth First Search (DFS) : 깊이 우선 탐색 Breadth First Search (BFS) : 넓이 우선 탐색 깊이 우선 탐색은 자식노드를 타고 쭉쭉 내려갔다가, 다시 올라와서 그다음 줄기를 탐색하는 것을 말하고 너비 우선 탐색은 자식노드를 모두 방문하고, 그 자식의 자식노드를 방문하는 식의 탐색을 말한다 DFS는 Stack을 이용해서 구현하고, BFS는 Queue로 구현한다 Stack은 Last In First Out, Queue는 First In First Out 인데 이 점을 이용하여 구현하는 것이다 DFS는 재귀호출을 통하여 더 쉽고 편리하게 구현할 수 있다 백준 알고리즘 1260 DFS와 BFS 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 문제 방문할 수..

제일 왼쪽 열에서 제일 오른쪽 열까지 파이프를 연결하려고 한다 파이프는 오른쪽, 오른쪽 위 대각선, 오른쪽 아래 대각선으로 연결할 수 있다 파이프라인의 최대 개수를 구하는 문제!! 그리디로 접근하는 DFS 문제다 (멍청하게 DFS로 풀 생각 안해서 돌아 돌아 갔음) //DFS 첫번째 열에서 오른쪽으로 한칸씩 이동하며 가장 마지막 열까지 갈 수 있는지 확인해야 한다 //그리디 오른쪽 위 대각선, 아래 대각선, 바로 옆 ← 이렇게 세 가지 경우로 이동할 수 있는데, 위 대각선, 바로 옆, 아래 대각선 순서대로 확인해야 올바른 값을 구할 수 있다 아래부터 가버리면 아래 파이프들을 막게 되니까 최대 개수를 찾을 수 없다 main에서 행마다 한번씩 실행하도록 하고, dfs 함수에서 x == c - 1, 즉 가장 ..

제일 왼쪽에 있는 도시에서 제일 오른쪽에 있는 도시로 이동할 때 중간중간 기름을 넣어줘야 한다 처음 출발할 때 자동차에는 기름이 없고, 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다 각 도시마다 기름 가격이 다른데, 최소비용을 구하는 문제 동그라미 안에 있는게 리터당 주유 가격이고 사이사이 숫자가 도시 간의 거리이다 얼마든지 많은 기름을 넣을 수 있다는 뜻은 쌀 때 마구마구 넣으라는 뜻이다 일단 처음에는 차에 기름이 없기 때문에 리터당 5원을 주고 2리터를 주유해야 한다 만약 그다음 도시들의 기름 가격이 첫 도시보다 더 비싸다면 첫 도시에서 많이 주유해야 할 것이다 그걸 하나하나 체크할 순 없으므로 전 도시와 현재 도시의 기..