⭐ 코딩테스트
[백준 2623번 C/C++] 음악 프로그램
[백준 2623번 C/C++] 음악 프로그램
2024.03.21[백준 2623번 C/C++] 음악 프로그램 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 해결전략 위상 정렬 Topology Sort 정답코드 #include #include #include using namespace std; int n, m; // n: 가수의 수, m: 보조 PD의 수 vector v; // 각 가수의 진입차수 저장 벡터 vector graph; // 가수들의 순서 관계를 나타내는 그래프 bool i..
[프로그래머스 C++] 가장 긴 팰린드롬
[프로그래머스 C++] 가장 긴 팰린드롬
2024.03.20[프로그래머스 C++] 가장 긴 팰린드롬 https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 구현 글자 자리를 한칸씩 이동하며 글자 자리 기준으로 양옆을 검사한다. ex. "abcdcba" a 자리 검사 b 자리 검사 홀수 가정: b기준으로 양옆의 a, c가 같은지 검사. 같다면 계속해서 양옆으로 가면서 검사. int left = i-1, right = i+1; if (s[left] != s[right]) 짝수 가정: b기준으로 왼쪽의 a..
[프로그래머스 C++] 이모티콘 할인행사
[프로그래머스 C++] 이모티콘 할인행사
2024.03.18[프로그래머스 C++] 이모티콘 할인행사 https://school.programmers.co.kr/learn/courses/30/lessons/150368 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 구현 깊이우선탐색 DFS 정답코드 #include #include #include using namespace std; int n, m; vector answer(2); int discount[4] = { 10, 20, 30, 40 }; vector price(7); // 이모티콘 가격, 할인율 void DFS(int idx, const vect..
[프로그래머스 C++] 두 원 사이의 정수 쌍
[프로그래머스 C++] 두 원 사이의 정수 쌍
2024.03.17[프로그래머스 C++] 두 원 사이의 정수 쌍 https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 수학 구현 정답코드 #include using namespace std; long long solution(int r1, int r2) { long long answer = 0; for(int i = 1; i
[백준 3015번 C/C++] 오아시스 재결합
[백준 3015번 C/C++] 오아시스 재결합
2024.03.16[백준 3015번 C/C++] 오아시스 재결합 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 해결전략 자료 구조 스택 Stack 정답코드 #include #include using namespace std; struct Info { int height, pair; // height: 키, pair: 조건을 만족하는 쌍의 수 }; int n; long long answer; // 계산할 조건을 만족하는 쌍의 수 stack..
[백준 13907번 C/C++] 세금
[백준 13907번 C/C++] 세금
2024.03.14[백준 13907번 C/C++] 세금 https://www.acmicpc.net/problem/13907 13907번: 세금 첫 번째 줄에 세 정수 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 30,000), K (0 ≤ K ≤ 30,000)가 주어진다. 각각 도시의 수, 도로의 수, 세금 인상 횟수를 의미한다. 두 번째 줄에는 두 정수 S와 D (1 ≤ S, D ≤ N, S ≠ D www.acmicpc.net 해결전략 다익스트라 알고리즘 Dijistra Algorithm 최단경로 처음 시도한 코드 - 시간초과 #include #include #include using namespace std; const int INF = 987654321; int n, m, k; // n: 도시의 수, m: ..
[프로그래머스 C++] 과제 진행하기
[프로그래머스 C++] 과제 진행하기
2024.03.13[프로그래머스 C++] 과제 진행하기 https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 문자열 자료구조 스택 stack 정답코드 #include #include #include #include #include using namespace std; struct Info { // 과제 정보를 담는 구조체 정의 string subject; int time, duration; Info(string a, int b, int c) { subjec..
[백준 13141번 C/C++] Ignition
[백준 13141번 C/C++] Ignition
2024.03.12[백준 13141번 C/C++] Ignition https://www.acmicpc.net/problem/13141 13141번: Ignition 첫 번째 줄에는 그래프의 정점의 수 N과 간선의 수 M이 주어진다. (2 ≤ N ≤ 200, N-1 ≤ M ≤ 20,000) 두 번째 줄부터 M개의 줄에는 각 간선의 시작점 S, 끝점 E, 길이 L이 주어진다. (1 ≤ L ≤ 100) 시작점 www.acmicpc.net 해결방안 그래프 이론 브루트포스 알고리즘 최단 경로 플로이드–워셜 Floyd-Warshall 정답코드 #include #include using namespace std; const int INF = 987654321; int n, m; // n: 정점의 수, m: 간선의 수 vector di..
[프로그래머스 C++] 혼자 놀기의 달인
[프로그래머스 C++] 혼자 놀기의 달인
2024.03.11[프로그래머스 C++] 혼자 놀기의 달인 https://school.programmers.co.kr/learn/courses/30/lessons/131130 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 구현 풀이보다 문제를 해석하기가 더 힘든 문제다.. 정답코드 #include #include #include #include using namespace std; int solution(vector cards) { int n = cards.size(); // 전체 카드수 if (n < 1) return 0; // 카드가 한 개만 있는 경우 vec..
[백준 13977번 C/C++] 이항 계수와 쿼리
[백준 13977번 C/C++] 이항 계수와 쿼리
2024.03.08[백준 13977번 C/C++] 이항 계수와 쿼리 https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 해결전략 수학 소페르마 정리 고민하다 힌트를 보았다. 소페르마 정리를 모르면 풀기 힘든 문제였다. 소페르마 정리를 읽고 공식을 코드를 구현하면 되었다. 정답 코드 #include using namespace std; long long factorial[4000001]; long long MOD = 1000000007; long long CustomPow..
[프로그래머스 C++] 우박수열 정적분
[프로그래머스 C++] 우박수열 정적분
2024.03.06[프로그래머스 C++] 우박수열 정적분 https://school.programmers.co.kr/learn/courses/30/lessons/134239 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결방안 수학, 구현 정적분 공식을 사용하지 않아도 된다. 구분구적법의 개념으로 x길이 1단위로 도형의 넓이를 구하면 된다. 넓이는 마름모를 구하는 방식인 (윗변 길이 + 아랫변 길이) / 2 로 구하면 된다. 정답 코드 #include using namespace std; vector solution(int k, vector ranges) { vector..
[프로그래머스 C++] 광물 캐기
[프로그래머스 C++] 광물 캐기
2024.03.04[프로그래머스 C++] 광물 캐기 https://school.programmers.co.kr/learn/courses/30/lessons/172927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 깊이우선탐색 DFS 그리디 Greedy 정답 코드 - DFS #include #include #include using namespace std; int answer; // fatigue: 피로도, idx: 현재 인덱스, dia, iro, sto: 각 곡괭이의 수, 광물 벡터 void Shuffle(int fatigue, int idx, int dia,..