알고리즘

[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++] 백준 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..

[C++] 백준 2504번 괄호의 값

2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 스택 자료구조 문제. 구현력을 필요로 하는 노가다 문제이다. 문제 분석 스택 하나에 입력들을 넣어놨다가, 괄호가 닫히는 경우를 처리해주면 된다. 나같은 경우에는 다음과 같이 처리했다. 현재 입력이 '(' 또는 '['인 경우 -> 그냥 스택에 넣어준다. 현재 입력이 ')' 또는 ']'인 경우 -> 만일 스택의 위에 있는 게 숫자들일 경우, 다 더해준 후 *2 / *3을 해준다. 스택의 위에 있는 게 '(' / '[' 일 경우 '(' / '['를 빼내고 2를 넣어..