코딩테스트22

• 

  [백준 14889] 스타트와 링크 (C++) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 아이디어 나는 문제를 3가지 파트로 나눠서 풀었다. 1. 입력을 받는 부분 2. 팀을 짜는 부분 3. 짜여진 팀을 이용해서 점수를 계산하고 큐에 기록 입력을 받고, 짜여진 팀을 이용해 점수를 계산하는 것을 어렵지 않다. 이 문제의 핵심적인 부분은 팀을 짜는 부분이다. 그 부분은 아래와 같이 구현하였다. 이 문제의 경우에는 사람이 스타트팀 혹은 링크팀이기 때문에 스타트팀에 절반을 배정하면 나머지는 자동으로 링크팀이 된다.. 코딩테스트/BOJ 2022. 1. 5.

• 

  [C++ 알고리즘] 다이나믹프로그래밍2 - 배낭문제(Knapsack Problem) 배낭문제(Knapsack Problem) 다이나믹 프로그래밍의 대표적인 예시문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 아래와 같은 형식으로 주어진다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제를 요약하자면 아래와 .. 코딩테스트/알고리즘 2022. 1. 4.

• 

  [백준 9461] 파도반 수열 (C++) https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 아이디어 문제를 풀고 다른 블로그 글들도 봤는데 규칙이 여러가지라 여러 방식의 점화식으로 풀 수 있다. 난이도가 쉬운 편의 문제이다. P(N)을 쭉 나열하면 아래와 같다. N P(N) 1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 7 10 9 11 12 12 13 나의 경우 1~5까지는 규칙이 적용되지 않는다고 보고 P(N)=P(N-1)+P(N-5)라고 점화식을 세워서 풀었는데 P(N)=.. 코딩테스트/BOJ 2021. 12. 3.

• 

  [백준 1011] Fly me to the Alpha Centauri (C++) https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 아이디어 마지막이 1로 끝나도록 일단 나열을 해봤는데 아래와 같았다. 숫자 식 횟수 1 1 1 2 1+1 2 3 1+1+1 3 4 1+2+1 3 5 1+2+1+1 4 6 1+2+2+1 4 7 1+2+2+1+1 5 8 1+2+2+2+1 5 9 1+2+3+2+1 5 10 1+2+3+2+1+1 6 11 1+2+3+2+2+1 6 12 1+2+3+3+2+1 6 .. 코딩테스트/BOJ 2021. 12. 2.

• 

  [백준 1065] 한수 (C++) https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 아이디어 1~99는 한수가 1,2,3,4 .... 99개이니 (한 자리, 두 자리 수는 모두 한수이니까) 입력받은 수가 100이상일 경우 100부터 해당 수 까지 한수인지 체크하면 된다. 한 자리씩 잘라 배열에 넣고 뒷자리 수에서 앞자리 수를 빼며 한수인지 체크했다. 코드 #include #include #include using namespace std; int main() { ios::sync_w.. 코딩테스트/BOJ 2021. 12. 1.

• [C++] 벡터 탐색 1. 벡터 내에 존재하는지 여부 탐색 (binary_search) 이 경우에는 이진탐색을 사용하는것이 빠르다. 단 이진탐색을 사용하려면 정렬이 되어있어야 한다. 에 정의되어있다. 아래와 같이 사용한다. binary_search(시작범위, 끝범위, 찾을 값); 예제 코드 #include #include #include using namespace std; int main() { int num; cin >> num; vector vec = { 1,3,5,7,9 }; //존재시 1, 그렇지 않으면 0 리턴 if (binary_search(vec.begin(), vec.end(), num)) { cout num; vector vec = { 1,3,5,7,9 }; int idx = find(vec.begin(),.. 코딩테스트/알고리즘 2021. 9. 7.

• 

  [C++] 숫자 자릿수 더하기 19-> 1+ 9 = 10 이런식으로 자릿수를 구해주는 코드이다. #include using namespace std; int seperateAndPlus(int x) { int res = 0; while (x != 0) { res = res + x % 10; x /= 10; } return res; } int main() { int num; cin >> num; cout 코딩테스트/알고리즘 2021. 9. 7.

• 

  [C++ 알고리즘] 분할정복(Divide and conquer) 개념 분할정복 알고리즘은 주어진 문제를 둘 이상의 부분문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 이를 병합해 문제를 해결하는 알고리즘이다. 종만북의 표현을 빌리자면 각개 격파 라고 간단히 설명할 수 있다. 바로 예제를 보도록 하자. 예제 1 : 수열의 합 1부터 N까지의 값을 구해야 한다고 가정하자. 이를 단순 재귀함수로 구현하면 아래와 같을 것이다. #include using namespace std; int recursiveSum(int N) { if (N == 1) { return N; } else { return recursiveSum(N - 1) + N; } } int main() { int A; cin >> A; cout > A; cout 코딩테스트/알고리즘 2021. 8. 28.

• 

  [백준 1541] 잃어버린 괄호(C++) https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제는 두가지를 생각해야 한다. 첫번째 수는 무조건 더해주는 수이다. -가 한번이라도 나오면 그 뒤에 나오는 숫자는 모두 빼줘야 한다. 예를들면 위의 55-50+40이라는 식은 값을 최소로 만들기 위해서는 55-(50+40)이렇게 괄호를 칠 것이다. 즉 결론적으로 55-50-40=-35가 된다. 위 규칙 2개를 유념하며 코드를 짜면 아래와 같다. #include #include using.. 코딩테스트/BOJ 2021. 8. 13.

• 

  [C++ 알고리즘] 그리디(탐욕법,Greedy Algorithm) 개념 그리디 알고리즘은 개념은 굉장히 단순하다. 말 그대로 탐욕적으로, 눈 앞의 가장 큰 이익을 추구하는 기법이다. 실제 그리디 알고리즘을 검색하면 아래와 같이 나온다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 일반적으로 생각했을 때 눈앞의 이익만을 쫓는 것이 최적의 선택이라고는 할 수 없다. 가령 아래와 같은 상황이 있다고 생각해보자. 예제 1 각 그림의 적힌 숫자는 문제를 푸는데 걸리는 시간이고 우리는 가장 빠른 시간안에 level1, level2, level3문제를 하나씩 해결하려 한다. 이때 문제를 푸는 시간을 최소화 하려면 어떻게 해야 .. 코딩테스트/알고리즘 2021. 8. 8.

• 

  [C++ 알고리즘] 동적 계획법(Dynamic Programming) 개념 동적계획법의 정의는 아래와 같다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산하는 방식. 정의만 가지고는 이해하기 쉽지 않다. 뒤에서 설명하겠지만, 결론적으로 말하자면 배열을 만들어 값들을 저장하고, 후에 그것들을 가지고 답을 구하는 방법이다. 동적 계획법을 이용해 문제를 풀려고 한다면 먼저 점화식을 세워야 한다. 점화식이라는 것은 어떤 수열의 일반항을 이전의 항들을 이용해 정의한 식이다. 고등학교 때 배웠던 수열의 일반항을 구하듯이 n번째 항을 구하는 방법을 식으로 나타낸다고 생각하면 쉽다. 예를 들어 흔히들 아는 피보나치 수열의 점화식은 아래와 같다. 이제 이 식을 가지고 코드로 작성을 해 보도록 하자. 일반적으로 재귀함수를.. 코딩테스트/알고리즘 2021. 7. 31.

• 

  [백준 1676]- 팩토리얼 0의 개수(C++) https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 값을 직접 구한 뒤 0의 개수를 뒤에서부터 세려고 했는데 500!의 값은 굉장히 크다. 아래 사이트에서 구해본 결과 https://ko.numberempire.com/factorialcalculator.php 팩토리얼 계산기 팩토리얼 계산기 ko.numberempire.com 팩토리얼의 값이 너무 크다. 그래서 구글링을 한 결과 소인수 분해를 한 뒤 5의 수를 세면 된다. 예제 출력을 보면 10을 입력받으면 2를 출력해야 하는데 10의 경우 10 9 8 7 6 5 4 3 2.. 코딩테스트/BOJ 2021. 7. 30.

• 

  [백준 1463] -1로만들기(C++)/다이나믹 프로그래밍 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근은 잘 했는데 경우의 수를 각각 비교해서 최솟값으로 답을 내야한다는 점을 간과해서 한참 헤맨 문제이다. 내가 생각한 접근 방법은 아래와 같다. 각 수를 1로 만드는 경우를 나열해 보았다. 입력 1 2 3 4 5 ... 8 9 10 연산 횟수 0 1 1 2 3 ... 3 2 3 점화식은 아래와 같이 세웠었다. n=1이면 0 3으로 나눠질 때 : f(x)=1+f(x/3) 2로 나눠질 때 : f(x)=1+f(x/2) 두 수로 나눠지지 않을 때 : f(x)=f(x-1)+1 이런식으로 세웠었다. 적용해보면 f(5)=.. 코딩테스트/BOJ 2021. 7. 29.

• 

  [백준 1620]-나는야 포켓몬 마스터 이다솜(C++)/이진탐색, 숫자여부 https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제에서 배운것은 문자열-숫자 변환, 이진탐색이다. 이진탐색은 이론은 알고 있었는데 사용할 생각을 자꾸 못하는 것 같다. 문자열과 숫자 우선 입력받은 값이 숫자인지 숫자가 아닌지 판정을 해야 했는데 그러기 위해 함수를 하나 만들었다. isdigit()함수를 이용했다. //isdigit( [char형 문자] ) -> 해당 문자가 숫자인지 아닌지 리턴해준다. bool .. 코딩테스트/BOJ 2021. 7. 28.

• 

  [백준1978]-소수 찾기(C++) https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수 구하기 2보다 작으면 무조건 소수가 아니므로 false를 리턴, 그게 아닐 경우 2부터 해당 수의 제곱근으로 나눠보며 한번이라도 나누어 떨어지면 소수가 아니라고 판정하는 방식을 이용하였다. 코드는 아래와 같다. sqrt를 사용하기 위해서 #include 를 해주어야 한다. bool isPrime(int p) { if (p < 2) { return false; } double sq = sqrt(p); for (int i = 2; i N; while (N--) {.. 코딩테스트/BOJ 2021. 7. 18.

• 

  [백준2609]-최대공약수와 최소공배수(C++)/유클리드 호제법 https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법 유클리드 호제법의 과정은 아래와 같다. 큰 숫자를 작은 숫자로 mod연산을 한다. 작은 숫자를 1번에서 구한 나머지 mod연산을 한다. 위 과정을 mod연산의 결과가 0이 나올때 까지 계속 반복한다. 이때 나누는 수로 사용된 수가 두 수의 최대공약수가 된다. 위 과정을 이용해서 1428과 833의 최대공약수를 구해보도록 하자. mod연산의 결과가 0이 될때 나누는 수는 119였으니 1428과 833의 최대공약수는 119이다. 이를 코드로 구현하면 .. 코딩테스트/BOJ 2021. 7. 18.

• 

  [백준1012] 유기농 배추(C++) https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include using namespace std; int T, M, N, K; int map[60][60]; int moveX[4] = { 0,1,0,-1 }; int moveY[4] = { 1,0,-1,0 }; void reset() { for (int i = 0; i < 60; i++) { for (int j = 0; j < 60; j++) { map[i][j] = 0; } } } void dfs(in.. 코딩테스트/BOJ 2021. 7. 8.

• 

  [백준1260]DFS와 BFS(C++) https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs/bfs구현 #include #include #include #include using namespace std; vector edge[1001]; int check1[1001]; int check2[1001]; void dfs(int start) { check1[start] = 1; cout M >> S; while (M != 0) { int a, b;.. 코딩테스트/BOJ 2021. 7. 3.

• 

  [백준10989]-수 정렬하기 3(C++) https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 처음에는 아무 생각 없이 정렬해서 풀다가 틀려서 봤더니 메모리 제한이 8MB였다. 구글링을 해보니 수를 모두 입력받아서 저장하면 메모리를 초과하게 되니 입력받은 숫자의 개수를 세는 식으로 접근해야 한다고 한다. 즉 [5, 2, 3, 1, 4, 2, 3]을 입력받았을 때 각 숫자를 입력받아 저장하는 것이 아니라 0으로 초기화 된 배열의 n번째 인덱스를 추가해주는 식으로 풀어 주어야 한다. 정답 코드는 아래와 같다. .. 코딩테스트/BOJ 2021. 6. 23.

• 

  [C++자료구조] 배열(Array)구현 구현 내용 at(𝒊) : 배열 Arr의 인덱스 i에 저장된 값을 출력한다.(단, 0 ≤ 𝑖 ≤ 𝑁 − 1) add(𝒊, 𝒗𝒂𝒍𝒖𝒆) : 배열 𝐴𝑟𝑟의 인덱스 𝑖에서 𝑁 − 2의 값을 오른쪽으로 한 칸씩 이동한다. 그리고 배열 𝐴𝑟𝑟의 인덱스 𝑖번째에 𝑣𝑎𝑙𝑢𝑒를 삽입한다. (단, 0 ≤ 𝑖 ≤ 𝑁 − 1) remove(𝒊): 배열 𝐴𝑟𝑟의 인덱스 𝑖 + 1에서 𝑁 − 1까지의 값을, 왼쪽으로 한 칸씩 이동시킨다. 그리고 배열 𝐴𝑟𝑟의 𝑁 − 1번째 인덱스의 값을 0으로 할당한다. (단, 0 ≤ 𝑖 ≤ 𝑁 − 1) set(𝒊, 𝒗𝒂𝒍𝒖𝒆): 배열 𝐴𝑟𝑟의 인덱스 𝑖번째에 𝑣𝑎𝑙𝑢𝑒를 할당하고 𝑣𝑎𝑙𝑢𝑒를 출력한다. (단, 0 ≤ 𝑖 ≤ 𝑁 −1) print(): 배열 𝐴𝑟𝑟의 모든 값을 공백으로 구분지어 .. 코딩테스트/자료구조 2021. 4. 10.

• 

  [C++ 자료구조] 단일 연결 리스트(Singly Linked List) - 기본 https://thewayaboutme.tistory.com/91 c++ singly linked list 단일 링크드 리스트 구현 * 본문은 (범한서적주식회사, 2013)을 공부하면서 작성한 글입니다. 향후 객체지향 및 자료구조 수업을 들으며 정확한 + 최신 내용 이해를 반영하여 보완해 나갈 것입니다. 1. 문자열 리스트를 가 thewayaboutme.tistory.com 이 글은 위 블로그 글을 참고하여 작성되었습니다. 연결 리스트를 사용하는 이유 여러가지 값들을 저장하고 처리하는 방법 중 가장 대표적인 것은 아마 배열(Array)일 것이다. 그런데 배열의 경우 중간에 있는 원소를 삭제하거나, 값을 삽입할 때 굉장히 비효율적이다. 만약 아래와 같은 배열이 있다고 가정해보자. 여기서 22를 삭제하려 한.. 코딩테스트/자료구조 2021. 3. 4.

• 

  [백준2309] - 일곱난쟁이(C++) https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 아이디어 아홉 난쟁이의 키를 모두 벡터에 넣은 뒤 합(sum)을 구한다. 그리고 sum과 100의 차를 구해 n1이라 하자. 그런 뒤 이중 포문을 이용해 벡터의 값 중 2개를 골라 더한 값이 n1일때 이중포문을 탈출한다. 그리고 벡터에서 해당 원소들을 지워준 뒤 정렬하여 출력한다. 조금 더 자세히 설명하자면 아래의 그림과 같다. i=0~7, j=i+1~8을 반복하는 이중 포문을 만들어 위와 같이 하나씩 더.. 코딩테스트/BOJ 2021. 1. 11.