알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 주어진 map에서 흰 돌을 2개 놓을 때, 검은색 돌을 최대한 많이 죽을 수 있는 개수를 구하는 문제입니다. 돌을 놓을 수 있는 곳에 모두 놓아본 뒤, 잡을 수 있는 돌의 개수를 전부 확인해보면 됩니다. 1. 2개의 돌을 차례대로 놓는다. 2. 돌을 놓은 뒤, 검은 색 돌을 몇개를 잡을 수 있는지를 확인해본다. 3. 모든 경우를 확인한 ..

문제 링크입니다. https://www.acmicpc.net/problem/1535 1535번: 안녕 첫째 줄에 사람의 수 N(≤ 20)이 들어온다. 둘째 줄에는 각각의 사람에게 인사를 할 때, 잃는 체력이 1번 사람부터 순서대로 들어오고, 셋째 줄에는 각각의 사람에게 인사를 할 때, 얻는 기쁨이 1번 www.acmicpc.net N명이 사람이 있을 때, i번째 사람에게 인사를 하면 L[i]만큼 체력이 줄어들고, J[i]만큼 기쁨이 늘어납니다. 이때, 최대로 얻을 수 있는 기쁨을 구하는 문제입니다. 사람의 수가 따라서 확인할 수 있는 모든 경우를 확인했습니다. i번째 사람을 선택하는 경우와 안하는 경우가 있기 때문에 이를 모두 vector에 넣어준 뒤, 선택하는 경우에서 최댓값을 비교해주면 됩니다. 자세..

문제 링크입니다. https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 완전탐색을 이용한 그래프 문제입니다. 5*5 숫자판에서 무작위 위치에서 5번까지 이동해 수열을 구하는 문제입니다. 1을 5번 이동했다면 11111이 수열이 됩니다. 만들 수 있는 수열이 숫자판에 따라 11111 ~ 99999까지 있을 수 있습니다. 따라서 이전에 만들었던 수열을 찾는 배열 칸은 100000 이상으로만 잡아주면 됩니다. 아..

문제 링크입니다. https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹을 이용한 문제입니다. 구현하는 방법을 떠올리는게 어려웠던 문제입니다. 한 곳의 불을 끄면 해당 위치부터 상하좌우의 값이 바뀌게 됩니다. 가로, 세로가 모두 10의 크기이기에 모든 경우를 확인하여면 2^100인 경우가 나오게 됩니다. -> 시간 초과가 생깁니다. 이 문제를 풀기 위해선 2가지를 생각해야하는데, 1. 한 번 누르면 다시 누를 필요가 없다. -> ..

문제 링크입니다. https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net BFS와 구현, 브루트포스가 합쳐진 문제였습니다. 문제 자체는 간단하지만 구현 능력이 있어야했던 문제입니다. 5개 층의 Map이 주어지고, 이를 통해 미로를 구성한 뒤 탈출할 수 있는지를 확인하는 문제입니다. 이 문제를 풀기 위해서 구현해야할 것이 있습니다. 1. 5개 층을 선택하기 2. 층을 반시계 혹은 시계 방향으로 돌리기 3. 구성된 미로를 탐색하기 먼..

문제 링크입니다. https://www.acmicpc.net/problem/17086 17086번: 아기 상어 2 첫째 줄에 공간의 크기 N과 M(2 ≤ N, M ≤ 50)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어지며, 0은 빈 칸, 1은 아기 상어가 있는 칸이다. 빈 칸과 상어의 수가 각각 한 개 이상인 입력만 www.acmicpc.net 브루트포스와 BFS가 합쳐진 문제였습니다. map이 주어졌을때, 상어와 가장 멀리 떨어진 위치를 찾는 곳입니다. 주어질 수 있는 map의 크기가 크지 않기 때문에 모든 곳에서 상어와 떨어진 거리를 확인해보면 되는 문제입니다. for문을 통해, map의 값이 0인 모든 곳에서 8방향 탐색을 시작해 1과 만나면 바로 탈출해주면 됩니다. 이때의 이동거리를 ..

문제 링크입니다. 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/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 삼성 SW 역량 테스트 기출문제 였습니다. 문제에서 주어진 조건대로 구현하면 풀 수 있는 문제였습니다. 구현 문제에 익숙하지 않으시다면 어려울 것 같습니다. 모든 경우를 탐색해야 함으로 DFS를 통해 확인했습니다. CCTV는 1번~5번까지 있습니다. 1번 -> 한방향 2번 -> 2방향(평행) 3번 -> 2방향(수직) 4번 -> 3방향 5번 -> 4방향 6번 -> 벽 M..

문제 링크입니다. https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 브루트포스 알고리즘 문제였습니다. (0 ~ 256) 높이 사이에서 고르게 만들 수 있는지를 확인하는 문제였습니다. 블록을 쌓던가, 없애던가 총 2가지 방법이 있습니다. 따라서 먼저 해당 높이를 만들 수 있는지를 확인해야합니다. B + 제거한 블록의 수 >= 쌓아야하는 블록의 수 -> 해당 조건이 맞을때만 시간 계산을 해야합니다. 해당 조건을 만족한다면 시간을 계산 해야합니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 브루트포스 알고리즘 문제였습니다. "666"을 포함하여 영화번호를 정하는 문제였습니다. 1번 -> 666, 2번 -> 1666, 3번 -> 2666, 4번 -> 3666, 5번 ->5666, 6번 -> 6660.... 666이 포함되어 있지만, 숫자가 계속 증가하고 있음은 알수 있습니다. 따라서 숫자를 계속 증가하면서, 666이 발견되면 순서를 하나 증가합니다. 이때 순서가 N..

문제 링크입니다 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 123 / 456 / 780의 순서로 퍼즐을 만들면 되는 문제였습니다. 이때 0을 1~8 이외의 숫자인 9로 정해준뒤 이동시키는 문제였습니다. 따라서 123456789의 순서로 만들어주면 됩니다. -> 123 / 456 / 789 9를 가진 칸은 비어있음을 의미함으로 해당 위치에서 4방향 탐색을 통해서 이동할 수 있는 곳으로 이동합니다. 3*3 배열이기에 위의 과정을 전부 확인해봅니다(브루트 포스) 이동하는 과정에서 123456789의 순서로 나열되는 것이 ..