컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 문제 해결 알고리즘 그리디 알고리즘 문제 수 중에 홀수가 존재하면 홀수들을 전부 -1 해준다. 수 중에 홀수가 존재하지 않다면 모든 수를 2로 나눠준다. 소스 코드 #include using namespace std; int N, result = 0; int arr[51]; bool is_zero(){ bool flag = true; for(int i=0;i> N; for(int ..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 알고리즘 다익스트라로 푸는 문제. 노드의 제한이 그렇게 크지 않기 때문에 우선순위 큐로 굳이 안 풀어도 되는 문제이지만 썼다. 아래의 링크에 다익스트라 알고리즘이 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라 - 선형 탐색, 우선순위 큐 다익스트라 알고리즘 (Dijkstra'..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 문제 해결 알고리즘 다익스트라를 써주는 문제. 하지만 노드의 수 제한이 20000까지이므로 그냥 선형탐색으로 풀면 무조건 시간초과가 날 수밖에 없다. 그렇기 때문에 우선순위 큐를 이용해 정답을 구하자. 아래의 링크에 다익스트라 알고리즘이 설명되어있다. https://kimmessi.tistory.com/185?category=871925 [알고리즘] 다익스트라..

https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 해결 알고리즘 알고리즘은 간단한데 그걸 구현해내는 아이디를 내기가 좀 어려웠던 문제.. 1. 점수가 높은 순서대로 (만약에 같으면 일수가 낮은 순서대로) 우선순위 큐에 정렬을 해준다. 2. 그 정렬된 큐 값에 일수를 고려한 최대값을 구해준다. 1번은 쉽지만 2번에서 막혔다. 배열을 이용해서 문제를 풀 수 있었는데 큐에서 나온 값의 일수부터 1까지의 인덱스 중 차례대로 0이면 거기에 값을 그대로 입력해주고 break를 해준다. 이 방식대..

https://www.acmicpc.net/problem/16288 16288번: Passport Control 입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 N 과 k 가 주어진다. N은 입국 승객의 수이며 k는 여권 심사 창구의 수이다. 단, 2 ≤ k ≤ N ≤ 100 이다. 그리고 두 번째 줄에는 승객이 입 www.acmicpc.net 문제 해결 알고리즘 문제가 약간 어렵게 느껴지나 생각을 조금만 해보면 풀 수 있는 쉬운 문제였다. 입력에서 주어진 수열의 연속하는 증가하는 수열의 개수가 여권 심사 창구(k)보다 많다면 불가능한 순서이고 적거나 같다면 가능한 순서이다. 예를 들어, 예제에 나온 입력을 보자 10 3 4 1 3 2 5 6 8 9 7 10 여기서 연속하는 증가하는 수열은 4..

https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 문제 해결 알고리즘 모든 추의 무게를 정렬 해준 후에 자기보다 왼쪽에 있는 추들의 무게의 합보다 크면 그 합에 +1인 값을 출력해주면 된다. 만약에 없다면 모든 추의 무게의 합에 +1을 해준 값을 출력해준다. 이 때, 만약 가장 무게가 가벼운 추의 무게가 1보다 크다면 1을 출력해준다. 소스 코드 #include using namespace std; int main(){ int N; cin >> N; vec..

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제 해결 알고리즘 각 센서간의 차이를 구한 것들을 배열에 넣고 정렬한 후 큰 순서대로 차이들을 K-1개씩 센서 중에 가장 큰 정수거리와 가장 작은 정수거리를 뺀 값에 빼준다. 그 값을 출력한다. 소스 코드 #include using namespace std; int main(){ int N, K; cin >> N >> K; if(N == 1) { cout sensor[i..

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 문제 해결 알고리즘 그리디하게 a + b와 b + a 중에 큰 것으로 정렬을 해준다. 소스 코드 #include using namespace std; bool cmp(string a, string b){ if(a == b) return false; string ab = a+b; string ba = b+a; if(ab > ba) return true; else r..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 해결 알고리즘 그리디 알고리즘으로 '+'연산부터 전부 연산 해준 뒤 '-'연산을 해준다. 파싱해주는 게 까다로웠던 문제였다. 소스 코드 #include using namespace std; int main(){ string str; cin >> str; int result = 99999999; string num = ""; vector number; vector opt; for(int ..

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 해결 알고리즘 X가 연달아 있는 부분에서 X의 개수가 홀수이면 -1을 출력해주고 짝수이면 4개씩 A로 채우다 2개가 남으면 B로 채워준다. '.'은 그대로 출력해준다. 소스 코드 #include using namespace std; int main(){ string str, result = ""; cin >> str; string A = "AAAA", B = "BB"; int cnt = 0; for(int i=0;i