목록대학교/Algorithm (105)
차근차근
0. 제목 백준 10610 30 BOJ 10610 30 C++ 10610 30 1. 문제 https://www.acmicpc.net/problem/10610 2. 풀이 30의 배수가 되려면 3의 배수이면서 10의 배수여야한다. 10의 배수이려면 마지막에 0이 반드시 나와야 하고 3의 배수이려면 각 자리 수의 합이 3으로 나누어 떨어져야 한다. 그리고 문제에서 N이 최대 100000개의 숫자로 구성되어 있다고 하여 문자열로 입력을 받았다. 먼저 입력값에 0이 포함되어 있는지 확인하고 포함되어 있는 것들의 자리수 합을 구한다. 자리수가 3으로 나누어 떨어지면 내림차순을 하고 정답을 출력한다. 조건에 맞지 않으면 -1을 출력한다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16..
0. 제목 백준 2875 대회 or 인턴 BOJ 2875 대회 or 인턴 C++ 2875 대회 or 인턴 1. 문제 https://www.acmicpc.net/problem/2875 2. 풀이 그리디 알고리즘을 사용하였다. 2명의 여학생과 1명의 남학생이 팀을 만들어야 하고 K명이 인턴쉽에 참여해야 한다. K명이 빠져야 하므로 여학생, 남학생에서 합하여 K명 만큼 모든 경우의 수대로 뺀다. 여학생 2명과 남학생 1명이므로 위에서 뺀 값을 각각 2와 1로 나눈다. 두 값중 작은 값이 만들어질 수 있는 팀의 수가 된다. 최대의 팀 수를 구해야 하므로 최대값과 만들어진 팀을 비교하면서 최대값을 갱신하고 최종 결과가 답이 된다. 다음과 같은 방식으로도 답을 구할 수 있다. min(N/2, M, (N+M-K)/3..
0. 제목 백준 2331 반복수열 BOJ 2331 반복수열 C++ 2331 반복수열 1. 문제 https://www.acmicpc.net/problem/2331 2. 풀이 DFS를 사용하였다. visited는 방문횟수를 저장하는 배열이다. 인덱스의 최댓값은 300000을 넘지 못하므로 visited[300001] 으로 크기를 설정하였다. dfs함수를 구현할 때 방문할때마다 visited[x]의 값을 1씩 증가시켜주었다. 그리고 if(visited[x]==3) retun; 에서 3일때 return 해야 하는 이유는 문제에서 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 구하라고 하였기 때문이다. 만약 2에서 return을 해버리면 반복되는 수들까지 개수에 포함이 된다. 그래서 3일때 ret..
0. 제목 백준 11047 동전 0 BOJ 11047 동전 0 C++ 11047 동전 0 1. 문제 https://www.acmicpc.net/problem/11047 2. 풀이 그리디 알고리즘을 사용하였다. 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다. 동전의 가치가 오름차순으로 주어지기 때문에 가치가 큰 동전부터 차례대로 나눈다. 몫만큼 cnt에 더해주고 K를 나머지로 갱신해준다. 그렇게 모든 동전에 대해서 K/value[i]의 값이 0이 아닌동안 반복하면 누적된 cnt가 정답이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
0. 제목 백준 10451 순열 사이클 BOJ 10451 순열 사이클 C++ 10451 순열 사이클 1. 문제 https://www.acmicpc.net/problem/10451 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. Directed Graph 이므로 방향성을 가지고 있다. 각 정점에 연결된 점들을 graph vector에 push_back 함으로써 연결성을 가지게 한다. 그 후 DFS, BFS 중 하나를 이용하여 탐색을하고 모든 점을 시작점으로 하여 count 값을 구한다. count 값이 순열 사이클의 개수이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 ..
0. 제목 백준 1912 연속합 BOJ 1912 연속합 C++ 1912 연속합 1. 문제 https://www.acmicpc.net/problem/1912 2. 풀이 DP 방식을 이용하였다. 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 것이 목적이다. 예를 들어, 배열의 값들이 10, 20, -100, -500, 700, 30 이라고 할 때, dp[1] = 10, dp[2] = 30, dp[3] = -70, dp[4] = -500, dp[5] = 700, dp[6] = 730 이다. 이 배열 dp 의 원소 값들을 구하는 규칙은 다음과 같다. 만약 dp[i]를 구하려고 할 때 dp[i-1] 가 음수라면 dp[i] = arr[i] 로 업데이트 해주고 양수라면 dp[i] = dp[..
0. 제목 백준 1707 이분 그래프 BOJ 1707 이분 그래프 C++ 1707 이분 그래프 1. 문제 https://www.acmicpc.net/problem/1707 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다고 문제에 정의되어 있다. 각 단계마다 색을 칠하는데 color 가 0이면 아직 방문하지 않은 것이고 1과 2로 색을 표현하였다. 이분 그래프 여부를 판단하는 함수에서는 다음 단계로 갈때 같은 색깔을 가지고 있으면 false를 반환하고 그것이 아니면 true를 반환하도록 하였다. 3. 코드 1 2..
0. 제목 백준 11724 연결 요소의 개수 BOJ 11724 연결 요소의 개수 C++ 11724 연결 요소의 개수 1. 문제 https://www.acmicpc.net/problem/11724 2. 풀이 DFS, BFS 두가지 방법으로 풀 수 있다. checked 배열을 N번째 index까지 검사하여 true가 아니면 탐색을 실시하고 실시할때마다 count값을 1씩 증가시켜준다. 그 count값이 연결 요소의 개수이다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 5..
0. 제목 백준 2750 수 정렬하기 BOJ 2750 수 정렬하기 C++ 2750 수 정렬하기 1. 문제 https://www.acmicpc.net/problem/2750 2. 풀이 가장 작은 것을 앞으로 보내는 것이 핵심 아이디어인 선택 정렬을 사용하였다. 가장 작은 원소를 맨 앞으로 보내고 다음 Loop에서는 두번째 작은 원소를 두번째로 보내고 이런식으로 원소 개수만큼 Loop를 돈다. 3. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include using namespace std; int main(int argc, const char * argv[]) { int N; int ar..
0. 핵심 아이디어 옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내면 어떨까? 1. 예시 1 10 5 8 7 6 4 3 2 9 1 5 10 8 7 6 4 3 2 9 1 5 8 10 7 6 4 3 2 9 1 5 8 7 10 6 4 3 2 9 1 5 8 7 6 10 4 3 2 9 1 5 8 7 6 4 10 3 2 9 1 5 8 7 6 4 3 10 2 9 1 5 8 7 6 4 3 2 10 9 1 5 8 7 6 4 3 2 9 10 //결국 가장 큰 값이 뒤로 오게 됨. 첫번째 Loop 끝. 1 5 7 8 6 4 3 2 9 10 1 5 7 6 8 4 3 2 9 10 .... 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include using n..