⭐ 코딩테스트
[프로그래머스 C++] 배달
[프로그래머스 C++] 배달
2023.12.07[프로그래머스 C++] 배달 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 Dijkstra 다익스트라 알고리즘 (최단경로 알고리즘) 다익스트라(Dijkstra) 알고리즘은 그래프에서 한 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 음수인 간선이 없는 그래프에서만 사용할 수 있\다. 다익스트라 알고리즘 출발 노드를 설정 pQ.push(Edge(1,0)) 출발 노드를 기준으로 그래프의 모든 노드의..
[백준 16928번 C/C++] 뱀과 사다리 게임
[백준 16928번 C/C++] 뱀과 사다리 게임
2023.12.06[백준 16928번 C/C++] 뱀과 사다리 게임 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 해결전략 너비 우선 탐색 BFS 정답 코드 #include #include #include #include using namespace std; int n, m; // n: 사다리 수, m: 뱀의 수 map ladder, snake; int ch[101]; int main() { ios::sync_wi..
[프로그래머스 C++] 행렬 테두리 회전하기
[프로그래머스 C++] 행렬 테두리 회전하기
2023.12.06[프로그래머스 C++] 행렬 테두리 회전하기 https://school.programmers.co.kr/learn/courses/30/lessons/77485 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 구현, 브루트 포스 Brute Force 행렬 회전, 시뮬레이션 정답 코드 #include #include using namespace std; vector v; vector answer; void Rotate(int x1, int y1, int x2, int y2, int r, int c) { int minNum = 2147000000; ve..
[백준 18808번 C/C++] 스티커 붙이기
[백준 18808번 C/C++] 스티커 붙이기
2023.12.05[백준 18808번 C/C++] 스티커 붙이기 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 해결전략 구현 브루스포스 Brute Force 정답 코드 #include #include using namespace std; int n, m, k; // 노트북의 크기(n*m)와 스티커의 개수(k) int r, c; // 각 스티커의 크기(r*c) vector v; // 노트북 격자 vector sticker; // 각 스티커를 저장하기 위한 격자 i..
[백준 9019번 C/C++] DSLR
[백준 9019번 C/C++] DSLR
2023.12.04[백준 9019번 C/C++] DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 해결전략 구현 처음 시도한 코드 - 시간초과 #include #include #include #include #include using namespace std; vector ch; int D(int k){ return k * 2 % 10000; } int S(int k) { if (k == 0) return 9999; else return k ..
[백준 5430번 C/C++] AC
[백준 5430번 C/C++] AC
2023.12.03[백준 5430번 C/C++] AC https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 해결전략 구현 자료 구조 문자열 파싱 덱 처음 시도한 코드 - 시간초과 #include #include #include using namespace std; int t; string p; // 수행할 함수 int n; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) { cin >> p; cin >> n; stri..
[백준 1107번 C/C++] 리모컨
[백준 1107번 C/C++] 리모컨
2023.12.02[백준 1107번 C/C++] 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 해결전략 구현, 브루트포스 Brute Force 정답 코드 #include #include #include using namespace std; int n, m; set broken; // num에 고장난 버튼이 포함되어 있는지 확인하는 함수 bool isPossible(int num) { if (num == 0) { return broken..
[백준 10026번 C/C++] 적록색약
[백준 10026번 C/C++] 적록색약
2023.12.01[백준 10026번 C/C++] 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 해결전략 너비우선탐색 BFS 코드 #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int n; vector v; // 각 칸의 색을 기록 vector R, G, B; // R, G, B의 위치를 기록 /..
[프로그래머스 C++] 줄 서는 방법
[프로그래머스 C++] 줄 서는 방법
2023.11.29[프로그래머스 C++] 줄 서는 방법 https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결방안 순열 Permutation, 조합 Combination 처음 시도한 코드 - 테스트 케이스 모두 통과. 효율성 테스트 시간 초과 #include #include using namespace std; vector answer, temp; int ch[21]; int cnt; void Combination(int idx, const int& n, cons..
[백준 1744번 C/C++] 수 묶기
[백준 1744번 C/C++] 수 묶기
2023.11.28[백준 1744번 C/C++] 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 해결전략 탐욕법, 그리디 알고리즘 Greedy Algorithm 정렬 많은 분기 조건 정답 코드 #include #include #include using namespace std; int n; long long answer; // 수열의 두 수를 묶었을 때 나올 수 있는 수열의 최대합 vector negative, zero, positive; int ma..
[백준 1339번 C/C++] 단어 수학
[백준 1339번 C/C++] 단어 수학
2023.11.27[백준 1339번 C/C++] 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해결전략 탐욕법 Greedy Algorithm 그리디 알고리즘 각 알파벳 [ 예제 ] 2 GCF ACDEB G=100 C=10 F=1 -> GCF = 100G + 10C + 1F A =10000 C=1000 D=100 E=10 B=1 -> ACDEB = 10000A + 1000C + 100D + 10E + 1B A = 10000 * 9 C = 1010..
[백준 10830번 C/C++] 행렬 제곱
[백준 10830번 C/C++] 행렬 제곱
2023.11.26[백준 10830번 C/C++] 행렬 제곱 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결전략 분할 정복 long long mod_pow(long long base, long long exponent, long long mod) base^exponent를 mod로 나눈 나머지를 반환한다. 지수가 0인 경우: base^0 = 1 다. 따라서 1을 반환한다. 지수가 홀수인 경우: base^(2 * k + 1) = (base^k) * (base^k) * ba..