분류 전체보기

[백준] 그리디 기초 문제풀이 ③ - 2437, 1783, 1969, 2812 (C/C++)

2437 저울 문제 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다. 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오. 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 입력 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 ..

[백준] 그리디 기초 문제풀이 ② - 1138, 1541, 10610, 1946 (C/C++)

1138 한 줄로 서기 문제 N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다. 어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다. 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다. 각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다..

[백준] 그리디 기초 문제풀이 ① - 5585, 11047, 11399, 2217 (C언어)

5585 거스름돈 문제 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오. 입력 입력은 한줄로 이루어져있고, 타로가 지불할 돈(1 이상 1000미만의 정수) 1개가 쓰여져있다. 출력 제출할 출력 파일은 1행으로만 되어 있다. 잔돈에 포함된 매수를 출력하시오. 풀이 입력으로 들어온 수를 1000에서 빼고, 큰 화폐단위부터 차례대로 거슬러준다. #include int main() { int n, result = 0; scanf("%d"..

[알고리즘 공부] 그리디(Greedy) 알고리즘

그리디 알고리즘(Greedy Algorithm) - 당장 눈앞에 보이는 최적의 상황만을 쫓는 알고리즘 - 가장 단순한 형태이며, 난이도가 매우 낮은 알고리즘 중 하나. - 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있음. - 특정한 상황에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있음! 가장 대표적인 예제 : 거스름돈 문제 - 무조건 더 큰 화폐 단위부터 거슬러 주는 게 최적의 해 #include using namespace std; int main() { int n, result = 0; scanf("%d", &n); result += n/500; n %= 500; result += n/100; n %= 100; result += n/50;..

[알고리즘 공부] 플로이드 와샬(Floyd Warshall) 알고리즘

다익스트라 알고리즘 - 한 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 알고리즘 (1 → n의 최단경로) - 가장 적은 비용을 하나씩 선택해서, 그 적은 비용을 갖는 노드와 인접한 노드로 가는 비용을 계산해 알고리즘을 수행 - 가장 적은 비용을 가지는 노드를 하나씩 꺼내서, 그 노드를 거쳐가는 비용을 확인 플로이드 와샬 알고리즘 - '모든 정점'에서 '모든 정점'으로의 최단 경로를 구하는 알고리즘 (n → n의 최단경로) - 거쳐가는 정점을 기준으로 최단거리를 구함 - 거쳐가는 노드를 하나씩 설정해서 확인 : 거쳐가는 정점을 반복문의 중심에 있게 함. 각각의 정점이 다른 정점으로 가는 비용을 이차원 배열 형태로 출력하면 0 5 ∞ 8 7 0 9 ∞ 2 ∞ 0 4 ∞ ∞ 3 0 => 현재..

[알고리즘 공부] 다익스트라(Dijkstra) 알고리즘

다익스트라(Dijkstra) 알고리즘 - DP(다이나믹 프로그래밍)을 활용한 대표적인 최단경로 탐색 알고리즘 최단 거리는 여러 개의 최단 거리로 이루어져 있기 때문에 DP로 분류 가능 (그리디로 분류되기도 함) 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용 - 현재까지 알고 있던 최단경로를 계속해서 갱신 - 음의 간선을 포함할 수 없음. - 현실 세계에서 사용하기 매우 적합한 알고리즘 중 하나 (∵ 현실세계에서도 음의 간선이 존재하지 않으므로) 작동 과정 1. 출발 노드 설정 2. 출발 노드 기준으로 각 노드의 최소 비용 저장 3. 방문하지 않은 노드 중 가장 비용이 적은 노드 선택 4. 해당 노드를 거쳐서 특정 노드로 가는 경우를 고려해 최소 비용 갱신 5. 3~4 반복..

[알고리즘 공부] 에라토스테네스의 체

에라토스테네스의 체 - 가장 대표적인 소수(Prime Number) 판별 알고리즘 - 소수를 대량으로 빠르고 정확하게 구하는 방법 들어가기 전) 소수 구하는 간단한 알고리즘 모든 경우의 수를 다 돌면서 약수 여부를 확인하면 시간복잡도 O(N) => 비효율적 // O(N) #include bool isPrimeNumber(int x) { for (int i = 2; i < x; i++) if (x % i == 0) return false; return true; } int main() { printf("%d", isPrimeNumber(97)); return 0; } 약수들끼리 어느 수를 기점으로 대칭을 이룸. 그 기점이 되는 수가 판별하려는 수의 제곱근임. 특정한 숫자의 제곱근까지만 약수의 여부를 검증하..

[백준] 11726, 11727, 14852 2xn 타일링, 2133 3xn 타일링 (C, DP)

DP 개념 [알고리즘 공부] 다이나믹 프로그래밍(DP, 동적 계획법) 다이나믹 프로그래밍(Dynamic Programming) 하나의 문제를 단 한번만 풀도록 하는 알고리즘 컴퓨터적인 사고력을 물어보기 적합해서 자주 출제되므로 확실하게 알아야 함. DP, 동적 계획법이라고도 함 coding-maggot.tistory.com 11726 2xn 타일링 1 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 풀이 i) n이 1일 때(..