본문 바로가기

Time waits for no one 😎
FE 개발자 지망생의 기술 블로그입니다.
[Github - https://github.com/inthhh]

블로그 내 검색

📝 알고리즘217

[코드트리] 완전탐색 / 자리 수 단위로 완탐 연습문제 5개의 숫자 [1, 5, 2, 6, 8]이 주어졌을 때 이 중 단 하나의 숫자만 두 배로 해서, 인접한 숫자간의 차이의 합이 최대가 되도록 해보세요. 위 문제는 단순하게, 모든 위치의 숫자를 2배씩 해보는 완전탐색을 진행해 볼 수 있습니다. 1. 첫 번째 숫자 1에 2배를 하는 경우 [2, 5, 2, 6, 8]이 되므로, 인접한 숫자간의 차이의 합은 3 + 3 + 4 + 2 = 12가 됩니다. 2. 두 번째 숫자 5에 2배를 하는 경우 [1, 10, 2, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 9 + 8 + 4 + 2 = 23이 됩니다. 3. 세 번째 숫자 2에 2배를 하는 경우 [1, 5, 4, 6, 8]이 남게 되므로, 인접한 숫자간의 차이의 합은 4 + 1 + 2 + 2 = 9가 됩.. 2023. 2. 22.

[코드트리] Greedy - 그리디 알고리즘 / 동전 연습문제 1, 4, 5 동전을 이용하여 8원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 위 문제를 보면 당연히 큰 동전부터 쓰는 것이 좋아 보입니다. 하지만 큰 동전부터 사용하게 되면 5 + 1 + 1 + 1이므로 4개의 동전이 필요하지만, 4 + 4 역시 8 이므로 최소 동전의 수는 2가 됩니다. 그런데 다음 경우는 어떨까요? 1, 5, 10, 20 동전을 이용하여 78원을 거슬러주기 위해 필요한 최소 동전의 수를 구하는 프로그램을 작성해보세요. 이 경우에는 큰 동전부터 거슬러주는 것이 항상 좋습니다. 그 이유는 주어진 동전들이 전부 배수관계에 놓여있기 때문입니다. 그렇기에 큰 동전이 사용이 가능하다면, 작은 동전을 사용하는 것보다 항상 좋은 선택이 되는 것입니다. 따라서 배수 .. 2023. 2. 22.

[코드트리] Backtracking - 백트래킹 / 재귀 연습문제 백트래킹. 대충 알고있는건 백트래킹 == 완전탐색(모든 경우의 수를 무식하게 찾기)에서 가지치기로 효율 높임 이정도라서..ㅋㅋ 연습문제도 풀어봐야겠다 대부분의 알고리즘 문제들은 원하는 모든 조합을 만들어 그 중 문제에서 원하는 답을 고르는 식으로 해결이 가능합니다. 만약 n 제한이 작고, 모든 조합을 만드는 데 걸리는 시간이 문제에서 주어진 제한 시간보다 더 작다면, 항상 모든 조합을 다 만들어 보는 것이 가독성 측면에서나, 코드를 작성하는 입장에서 가장 좋다고 할 수 있을 것입니다. 다만, (1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2), .. 등 여러 가능한 순열과 조합을 만드는 것을 for문 만을 .. 2023. 2. 21.

[C++/백준] 11052 : 카드 구매하기 문제 요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. (카드 종류는 생략) 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다. 민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다. 예를 들.. 2023. 2. 21.

[C++/백준] 1260 : DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. .. 2023. 2. 21.

[C++/백준] 1149 : RGB 거리 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 .. 2023. 2. 21.

이전 1 ··· 27 28 29 30 31 32 33 ··· 37 다음

728x90

티스토리툴바