⭐ 코딩테스트
[프로그래머스 C++] 양궁대회
[프로그래머스 C++] 양궁대회
2024.05.14[프로그래머스 C++] 양궁대회 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결전략 완전탐색 Brute Force 문제를 읽고 완전탐색 문제라는것은 파악했다. 하지만 어려웠던 점이 2가지 있었다. 이 부분은 생각이 나지 않아 문제 게시판을 읽고 알게 되었다. DFS가 끝나는 시점에 아래 부분을 생각하기 힘들었다. ryan[ 10 ] = remain; // 남은 화살은 무조건 가장 낮은 점수에 사용 if문에 들어가는 경우 중 ' rem..
[백준 15685번 C/C++] 드래곤 커브
[백준 15685번 C/C++] 드래곤 커브
2024.05.07[백준 15685번 C/C++] 드래곤 커브 https://www.acmicpc.net/problem/15685 해결전략 구현 처음 시도할 때, 그려지는 모든 좌표를 기록한 후 재귀를 돌려 90도 회전시켰다. 좋지 않은 방법이고 재귀이기 때문에 시간초과가 나온다. 핵심 아이디어vector dots;꼭지점의 좌표가 아닌 방향을 저장한다생성되는 꼭지점을 dots 배열에 담는다. 이 때, 배열의 값은 방향이다.배열의 값(=방향)을 회전시킬 때 업데이트한다. 정답 코드 #include #include using namespace std;int dirY[4] = { 0, -1, 0, 1 };int dirX[4] = { 1, 0, -1, 0 };int n; // 커브의 개수vector> v(101, vect..
[백준 16236번 C/C++] 아기 상어
[백준 16236번 C/C++] 아기 상어
2024.05.04[백준 16236번 C/C++] 아기 상어 https://www.acmicpc.net/problem/16236 해결전략 너비우선탐색 BFS 아기 상어가 물고기를 먹은 시점에 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;int answer;bool success = false;struct Info{ int y, x, feed, sharkSize;};void BFS(int startY, int startX, int feed, int size, int time){ int timeSpe..
[백준 14499번 C/C++] 주사위 굴리기
[백준 14499번 C/C++] 주사위 굴리기
2024.05.04[백준 14499번 C/C++] 주사위 굴리기 https://www.acmicpc.net/problem/14499 해결전략 구현 x, y 좌표가 대다수의 코딩테스트 문제의 반대여서 헷갈렸다. 문제를 이해하는데 많은 시간이 걸렸다.이동할 때마다 주사위가 구른다. ' 북 >> 남 >> 서 >> 동' 순서로 주사위는 굴러간다. 정답코드 #include #include using namespace std;int n, m;int startX, startY;int k; // 명령의 개수vector> v;vector dice(6);// [0]// [4][1][5]// [2]// [3]void Roll(int dir){ vector tmp(6); if (dir == 1){ // 동 tmp[..
[프로그래머스 C++] 카카오프렌즈 컬러링북
[프로그래머스 C++] 카카오프렌즈 컬러링북
2024.04.28[프로그래머스 C++] 카카오프렌즈 컬러링북 https://school.programmers.co.kr/learn/courses/30/lessons/1829 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결전략 너비우선탐색 BFS 정답코드 #include #include #include using namespace std;int dirY[4] = { -1, 0, 1, 0 };int dirX[4] = { 0, -1, 0, 1 };vector> v, ch;int NumOfArea = 0;int MaxOneArea = 0;void BFS(int y, int ..
[프로그래머스 C++] 개인정보 수집 유효기간
[프로그래머스 C++] 개인정보 수집 유효기간
2024.04.27[프로그래머스 C++] 개인정보 수집 유효기간 https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해결전략 문자열 정답코드 #include #include #include #include using namespace std;map myMap;vector solution(string today, vector terms, vector privacies) { vector answer; int tYear = stoi(today.subs..
[백준 1520번 C/C++] 내리막 길
[백준 1520번 C/C++] 내리막 길
2024.04.23[백준 1520번 C/C++] 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해결전략 깊이우선탐색 + 다이나믹 프로그래밍, Dynamic Programming DFS + DP (= 메모이제이션) DFS로만 풀면 시간초과가 나온다. DFS 풀이: 시간초과 #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int..
[프로그래머스 C++] 3 x n 타일링
[프로그래머스 C++] 3 x n 타일링
2024.04.22[프로그래머스 C++] 3 x n 타일링 https://school.programmers.co.kr/learn/courses/30/lessons/12902 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해결전략 동적계획법 Dynamic Programming, DP dp[i] = dp[i-2] * 3 + dp[i-4] * 2 + dp[i-6] * 2 + dp[i-8] * 2 + dp[i-10] * 2 + ... dp[i] = dp[i-2] * 3 + ( dp[i-4] + dp[i-6] + dp[i-8] + dp[i-10] + ... ) * 2 크기가 n인 ..
[백준 7682번 C/C++] 틱택토
[백준 7682번 C/C++] 틱택토
2024.04.20[백준 7682번 C/C++] 틱택토 https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 해결전략 구현 정답코드 #include #include using namespace std; vector v; bool isWin(int ny, int nx, char player) // 특정 플레이어가 이겼는지 확인하는 함수 { // 가로 틱택토 if (v[ny][nx] == player && v[ny][nx] == v[ny][nx + 1] && v[ny]..
[백준 15864번 C/C++] 사다리 조작
[백준 15864번 C/C++] 사다리 조작
2024.04.19[백준 15864번 C/C++] 사다리 조작 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 해결전략 백트래킹 Backtracking 정답 코드 #include using namespace std; int n, m, h; int ch[31][11]; bool Cal() { for (int start = 1; start > n >> m >> h; for (int i = 0; i > y >> x; ..
[백준 6087번 C/C++] 레이저 통신
[백준 6087번 C/C++] 레이저 통신
2024.04.16[백준 6087번 C/C++] 레이저 통신 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 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 w, h;// w: 맵의 너비, h: 맵의 높이 int answer = 987654321;// 최소 거울 ..
[백준 2589번 C/C++] 보물선
[백준 2589번 C/C++] 보물선
2024.04.15[백준 2589번 C/C++] 보물선 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 해결전략 너비우선탐색 BFS 정답 코드 #include #include #include #include using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int r, c; vector v; int answer; void BFS(int startY, int startX..