알고리즘

[C++] 백준 17825번 주사위 윷놀이

17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제. 어떻게 풀어야 깔끔하게 풀 수 있을 지 모르겠어서 하드 코딩하는 방식으로 해결했다. WA를 많이 받게 됐는데 하드 코딩으로 구현해서 여러 번 고쳐서 맞출 수 있었다. 문제 조건 문제의 조건들은 다음과 같다. 시작 칸의 말이 4개 존재한다. 말이 파란색 칸(10, 20, 30)에서 이동할 경우 파란색 화살표를 따라 이동해야 하고, 이외에는 빨간색 화살표로 이동해야 한다. 말이 도착하면 이동 끝..

[C++] 백준 19237번 어른 상어

19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제. 테스트 케이스들이 잘 나와 있어서 테스트 케이스만 맞춰도 맞출 수 있다. 문제 조건 문제의 조건들은 다음과 같다. 상어의 정보 상어는 1 ~ M 번호를 가지고 있고, 중복되지 않는다. 상어들은 서로 내쫓으려고 하는데, 숫자가 낮을 수록 강한 상어이다. 격자 정보 N x N 크기의 격자에, M마리의 상어가 한마리씩 존재. 각 칸에 상어의 냄새가 존재..

[C++] 백준 9466번 텀 프로젝트

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 그래프 탐색 문제. 그래프 내의 Cycle의 존재를 찾은 후에 해당 Cycle에서 몇 개의 노드가 존재하는 지 찾아서 해결하면 된다. 문제 풀이 나같은 경우에는 다음과 같은 방법으로 해결할 수 있었다. 그래프 탐색을 돌면서 각 수가 만나는 마지막 번호를 기록한다. 이 때, 다음 번호가 이미 방문된 번호라면 현재 번호를 Return한다. (해당 번호에서 Cycle이 발생했다는 뜻) 그 후 각 수가 만나는 마지막 번호들에 대해 그래프 탐색을 진행해서 노드의 개수를 찾는다..

[C++] 백준 17837번 새로운 게임 2

17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제로, 초반에 설계를 잘 하고 들어가면 쉽게 풀 수 있는 문제. 정답률이 46퍼인 만큼, 테스트 케이스만 맞추면 거의 맞출 수 있는 것 같다. 문제 풀이 문제의 조건은 다음과 같이 정리할 수 있다. N * N 체스판에 말이 K개 존재한다. 말은 초반 입력에는 겹치지 않지만, 겹칠 수 있다. 체스판의 각 칸은 흰색(0), 빨간색(1), 파란색(2)일 수 있다. 각 말은 1~K번이며 각 말마다 이..

[C++] 백준 11779번 최소비용 구하기 2

11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 문제. BaaaaaaaaaaarkingDog 님의 0x1D강 - 다익스트라 알고리즘 에 수록된 문제이다. 특정 도시에서, 특정 목적지까지 최소 비용을 구할 뿐만 아니라 경로까지 출력해야 하는 문제. 문제 해석 어려운 조건은 없고 특정 도시에서 다른 도시까지 가는 데 최소 비용을 출력하면 된다. 이 때 최소 비용 뿐만 아니라, 해당 목적지까지 가는 경로도 출력해야 한다. 코드 /* * 백준 11779번 최소비용 구하기 2 ..

[C++] 백준 19236번 청소년 상어

19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 테스트 케이스가 잘 주어져 있어서 테스트 케이스만 잘 맞춘다면 대체로 맞는 것 같다. 구현 / 시뮬레이션 문제. 문제 조건 문제의 조건을 다음과 같이 정리할 수 있다. 4 * 4 공간이 존재하고, 1 * 1 크기인 한 칸마다 (x, y)에 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향이 존재하고, 번호는 1 ~ 16 / 방향은 1부터 8까지이며 상하좌우 + 대각선이다. 문제는 상어와 물고기의 ..

[C++] 백준 22862번 가장 긴 짝수 연속한 부분 수열 (large)

22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 투 포인터 문제. 투 포인터라는 점을 알 수 있다면 쉽게 풀 수 있는 문제. 나는 BaaaaaaaaaaarkingDog 님의 0x14강 - 투 포인터 문제집인 것을 알 수 있어서 바로 투 포인터로 풀었다. 문제 풀이 다음과 같은 조건으로 풀었다. 각 포인터인 L이 왼쪽, R이 오른쪽이라 할 때, 현재 R이 짝수면 R을 한 번 더 움직인다. 현재 R이 홀수이지만, 홀수의 삭제가 가능하다면 R을 한 번 더 움직인다. 위 두 조건에 해당하지 않으면 다음과 같은 조건으로 확인한다. R이 L보다 우측에 ..

[C++] 백준 19238번 스타트 택시

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 + 시뮬레이션 + 그래프 탐색 알고리즘으로 풀 수 있다. 문제 해석 택시의 조건은 다음과 같다. 목적지에 도착 시, 연료가 충전된다. 연료가 바닥날 경우 업무가 끝난다. 택시는 빈 칸의 상, 하, 좌, 우로 이동하며 특정 위치에 최단 경로로만 이동한다. 연료는 이동 한 칸마다 1이 소모된다. 다른 조건들은 다음과 같다. M명의 승객을 태우는 것을 목표로 한다. 활동 영역은 ..

[C++] 백준 12100번 2048 (Easy)

12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 상, 하, 좌, 우를 잘 움직일 수 있다면 풀 수 있는 문제. 문제 조건 문제 조건은 생각보다 간단하다. 보드의 모든 블럭들을 상, 하, 좌, 우로 이동. (보드를 눕히는 형태로 이동.) 이 때, 같은 숫자의 블럭은 합쳐지는데, 한 번의 이동마다 한 번만 합쳐진다. 보드 크기 n * n에서, 최대 5번 이동 후 만들 수 있는 가장 큰 블록의 값을 찾으면 된다. 보드 움직이는 조건 상, 우,..

[C++] 백준 6593번 상범 빌딩

6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 삼차원 배열로 풀 수 있는 그래프 탐색 문제. 삼차원 배열 초기화, 출력만 잘 맞춰주면 쉽게 풀 수 있다. /* * 백준 6593번 상범 빌딩 * https://www.acmicpc.net/problem/6593 * 그래프 탐색 이론 - 너비 우선 탐색(BFS) */ #include #include #include using namespace std; struct Point { int l; int r; int c; }; Point startPoint; int buil..