알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 삼성 SW 역량테스트 문제입니다. 까다로운 구현 문제였습니다. 게임이 멈추는 경우는 3가지입니다. 1. 턴이 1000번보다 넘게 진행되었을 경우 -> -1를 출력 2. 게임을 진행해도 끝낼수 없는 경우 -> -1를 출력 3. 블럭을 움직였을때 4개 이상의 블럭이 쌓였을 경우 -> 턴 횟수를 출력 3번 경우가 있기 때문에, vector를 통해서, (X , Y) 좌표에 어느 블럭..

문제 링크입니다. 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를 해주면서 뱀의 위치를 계속 갱..

안녕하세요? 엄청 오랜만입니다. 시험이 끝나고 방학을 맞이했으니 이제 블로그를 활발하게 작성할 예정입니다. 지금까지 꽤 쉬기도 했습니다. 요즘 제가 올리고 있는 문제들입니다. 45개 전부 푸는 것이 목표이며, 문제를 풀때마다 블로그에 올릴 예정입니다. 또한 방학을 맞이해, 너무 어려운 문제만 올리는 같아서 쉬운 문제들도 올려볼 생각입니다. 이와 비슷한 기초문제을 말한 것입니다. 또한 BFS, DFS, 최소 스패닝 트리, 트리, 정렬, DP 등등.. 다양한 알고리즘에 해당 설명과 대표 문제 풀이도 올릴 생각입니다. 관심이 많은 분이거나, 해당 자료, 정보들이 필요하신 분들이라면 많이 방문해주시길 바랍니다.

문제 링크입니다. https://www.acmicpc.net/problem/5988 5988번: 홀수일까 짝수일까 짝이 없는 경재는 매일 홀로 있다보니 홀수를 판별할 수 있는 능력이 생겼다. 창식이는 경재의 말이 사실인지 그 능력을 시험해보려 한다. 창식이의 의심이 끝이 없을 것 같아 N개만 확인하기 www.acmicpc.net 간단한 문제였지만, string을 사용해야하는 문제였습니다. 수의 범위가 최대 10^60임으로 int 나 long long 으로 값을 받지 못합니다. 저는 문자열로 값을 받아 홀수, 짝수를 판별했습니다. 1. 홀짝 판별하기 void solve() { for (int i = 0; i < N; i++) { int check = num[i][num[i].size() - 1] - '0'..

문제 링크입니다. 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()..