기록하는 습관

[백준] 11399 ATM

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..
알고리즘/[문제풀이] 백준 2020. 1. 7. 18:20
[백준] 11047 동전 0

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. #include #include using namespace std; int main(void) { int n, k; int cnt = 0; int a[11]; ci..
알고리즘/[문제풀이] 백준 2020. 1. 7. 18:19
[알고리즘] Greedy Algorithm

Greedy Algorithm 이란? 탐욕적인 알고리즘이라고도 하며, 결정을 해야 할 때마다 그 순간에 최적이라고 생각되는 것을 해답으로 선택하는 방식 문제점 그 순간의 선택은 당시(local)에는 최적이다. 그러나 최종적인(global) 해답을 만들었을 때, 그 해답이 최적이라는 보장이 없다. 따라서 항상 최적의 해답을 주는지 검증해야 한다. (대표적으로 0-1 Knapsack문제가 그러하다.) 1. Prim's Algorithm 임의의 정점(vertex)에서 가중치가 가장 작은 간선(edge)을 선택, 선택된 정점(vertex)와 연결된 간선(edge)들 중에 가장 가중치가 작은 것들을 선택(단, cycle을 만드는 경우는 제외) 2. Kruskal's Algorithm 그래프의 모든 간선(edge)..
알고리즘/[개념] 알고리즘 2020. 1. 7. 16:47
[프로그래머스] 완전탐색 - 소수 찾기

문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbers return 17 3 011 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 ..
알고리즘/[문제풀이] 프로그래머스 2020. 1. 7. 02:26
[C++] 순열과 조합

1. 조합 STL함수 next_permutation을 활용한 조합 구현 void combinationSTL(vector set, int n, int r) { for (int j = 0; j < n - r; ++j) set.push_back(0); for (int j = 0; j < r; ++j) set.push_back(1); do { for (int j = 0; j < n; ++j) if (set[j]) printf("%d ", j); printf("\n"); } while (next_permutation(set.begin(), set.end())); } 재귀함수를 활용한 조합 구현 #include #define MAX 5 using namespace std; int Arr[MAX]; bool Sele..
알고리즘/[개념] C++ 2020. 1. 7. 00:52
[프로그래머스] 완전탐색 - 모의고사

문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작..
알고리즘/[문제풀이] 프로그래머스 2020. 1. 6. 01:13
[C++] STL 정리

STL(Standard Template Library) : C++의 템플릿을 사용하여 표준으로 정리된 라이브러리 컨테이너(Container) : 컨테이너란 기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조 간단한 컨테이너 : pair 시퀀스 컨테이너 : vector, list, deque ... 연관 컨테이너 : set, map, multiset, multimap ... 어댑터 컨테이너 : queue, priority queue, stack ... 1. vector : 자동으로 메모리가 할당되는 동적배열로서, end에 요소를 삽입하는 연산은 상수 시간을 필요로 한다. 중간에 값을 삽입, 삭제 할 수 있지만 빈번해지면 비효율적이다. 생성자와 연산자 vector v; // 빈 벡터 생성 vector..
알고리즘/[개념] C++ 2020. 1. 5. 23:41
[백준] 2346 풍선 터뜨리기

문제 N개의 풍선이 있다. 각 풍선 안에는 -N부터 N까지의 수가 적혀있는 종이가 들어 있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다. 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 풍선은 원형으로 놓여 있다고 생각한다. 즉, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있는 것이다. 이동할 때에는 이미 터진 풍선은 빼고 생각한다. 예를 들어 다섯 개의 풍선 안에 차례로 3, 2, 1, -3, -1이 적혀 있었다고 하자. 이 경우 3이 적혀 있는 1번 풍선, -3이 적혀 있는 4번 풍선, -1이 ..
알고리즘/[문제풀이] 백준 2020. 1. 5. 01:22
Prev 1 ··· 16 17 18 19 20 Next