알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 생각보다 간단한 구현 문제입니다. 문제를 풀기 위해선 구현해야할 것이 3개 있습니다. 1. 컨베이어 벨트 움직이기 2. 로봇 움직이기 3. 로봇 놓기 먼저 컨베이어 벨트는 2줄로 되어있지만, 실제로 로봇이 올라가고 내려가는 부분은 1과 N부분 입니다. 따라서 2차원 배열을 통해 벨트를 관리할 필요는 없으며, N*2개의 1차원 배열을 이용하면 됩니다. 1. 컨..

문제 링크입니다. https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. 문제를 풀기 위해서는 2가지를 알아야합니다. 1. 드래곤 커브 구현하기 2. 정사각형 갯수 세기 먼저 드래곤 커브를 구현 하겠습니다. 위의 그림을 통해 설명하겠습니다. 1세대에서 2세대로 넘어갈 경우, 1세대의 움직임에서 반시계 방향으로 90도 움직인 방향으로 먼저 움직인 뒤, 1세대의 방향으로 움직입니다. 2세대에서 ..

문제 링크입니다. https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 정렬을 한 뒤의 MAP의 저장이 중요했습니다. 정렬을 하는 기준은 수의 등장횟수(오름차순)이며, 등장횟수가 같다면 수가 커지는 순서로 정렬을 하면 됩니다. 예를 들어, (3 , 3 , 2 , 1 , 2) 가 있다고 했을 때, (1 , 1 , 2 , 2 , 3 , 3)으로 정렬이 됩니다. 행의 갯수가 열의 갯수보다 많거나 같을 때에..

문제 링크입니다. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 조합을 사용하면 풀 수 있는 문제였습니다. N개의 수가 입력되었을때, N/2인 팀을 2개 만들어서 두 팀의 능력치 차의 최솟값을 구하는 문제입니다. 6명이 있다고 했을때, 팀이 (1, 2, 3) 과 (4, 5, 6)으로 나누어졌다고 가정하겠습니다. 이때 (1, 2, 3)이나 (3, 2, 1)이나 (2, 1, 3)이나 모두 같은 경우입니다. 마찬가지로 (4, 5, ..

문제 링크입니다. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 모든 경우를 확인하면 풀 수 있는 문제였습니다. N값과 나올 수 있는 경우가 적기에 모든 경우를 확인해보면 됩니다. 1. 경우 확인하기 void dfs_calculation(int plus, int minus, int multi, int divide, int cnt, int sum) { ..

문제 링크입니다. https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 꽤 복잡한 구현 문제였습니다. 저는 상어 움직이기 -> 겹치는 상어 없애기 -> 냄새 없애기 -> 냄새 퍼트리기 순서로 만들었습니다. 0. 선언된 배열, vector 설명 int change_way[401][4][4]; // X번 상어의 상하좌우 이동 우선순위 /// /////////////////..

문제 링크입니다. https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 주사위 굴리기 + BFS가 합쳐진 문제였습니다. 주사위를 동서남북으로 바꿀때, 값이 어떻게 변하는지를 나타냈습니다. 이를 통해서 주사위를 구리는 것을 구현할 수 있습니다. 1. 주사위 방향 바꾸기 int change_way_180(int x) { if (x == 0 || x == 2) return x + 1; else ret..

문제 링크입니다. https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 톱니바퀴의 움직임을 구현하는 간단한 문제였습니다. 톱니바퀴가 움직이는 규칙입니다. 1. X번 톱니바퀴가 Y 방향으로 움직인다. 2. X+1, X-1번 톱니바퀴가 X번 톱니바퀴와 맞닿아있는 곳의 극이 다르다면 해당 번호도 움직인다. 3. 움직인 톱니바퀴를 기준으로 앞뒤의 톱니바퀴도 다시 확인한다. 4. 한번 움직인 톱니바퀴는 다시 움직이지..

문제 링크입니다. https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 삼성SW 역량 테스트 문제였습니다. 정렬 기준을 만들어 정렬하면 쉽게 풀 수 있는 문제였습니다. 채우는 과정을 예시 입력 1번을 통해 확인하겠습니다. 1. 4번이 채워질때, 좋아하는 학생이 인접한 칸이 없음으로, 빈칸이 가장 많은 가운데에 놓아진다. 2. 3번이 채워질때, 좋아하는 학생이 있고(4번), 해당 자리들의 빈칸 수가 모두 같음으로, 행이 가장 작은 곳에 앉는..

문제 링크입니다. https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. Deque을 사용하면 풀 수 있는 문제였습니다. 뱀의 현재 위치와 이동했을 때, 뱀의 머리가 몸통에 닿는지를 확인해야 했습니다. 저는 Deque을 사용하여 front에는 머리 위치, back에는 꼬리 위치를 저장하여 풀었습니다. 이동할 때마다, 꼬리 위치인 back를 pop해주고, 새로운 머리 위치를 front에 push를 해주면서 뱀의 위치를 계속 갱..

문제 링크입니다. https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 삼성 SW 역량테스트 기출문제 입니다. 복잡해 보여도 규칙만 알면 매우 간단한 문제였습니다. 문제의 핵심은 주사위 움직임을 어떻게 구현하는가 입니다. 저는 주사위의 위치에 순서를 정하고, 동서남북 방향으로 굴렸을 때, 어떻게 변하는지는 확인했습니다. 사진을 통해 설명하겠습니다. 해당 사진을 보았을 때, 동서남북 방..

문제 링크입니다. https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 삼성 SW 역량테스트 기출문제입니다. 생각보단 귀찮은 구현 문제였습니다. 시간을 줄이기 위해 Queue에 좌표를 넣어놨습니다. 만들어야할 것은 1. 구름 좌표 이동 2. 해당 칸 물 증가 3. 다음 구름 찾기 입니다. 1. 구름 좌표 이동 while (!place.empty()) { int x = place.front().first; int y = place.front()..