알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 방문한 위치를 1차원 배열이 아닌 2차원 배열을 이용해서 확인해야되는 문제였습니다 문제 접근 방법 1. 현재 가지고 있는 스티커의 갯수를 통해서 3가지의 방법을 확인한다. 2. S개의 이모티콘이 만들어졌을 경우, 시간을 return 한다. 문제 접근 방법 - 1번(BFS() 함수를 참고해주세요) 현재 N개의 이모티콘에서 갈 수 있는 방법은 3가지 입니다. 1. check[N][N]이..

문제 링크입니다 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net BFS를 이용해 갈 수 있는 편의점에 들리면서, 도착점에 갈 수 있는지를 확인하는 문제였습니다. 편의점에 들릴 때마다 맥주의 갯수를 20개로 계속 바꾸어줘야 했습니다. 문제 접근 방법 1. 출발점, 도착점, 편의점의 위치를 pair로 받는다. 2. 위치 + 맥주의 갯수를 담을 수 있는 구조체를 선언한 뒤, 큐로 만들어준다. 3. 출발점에서 N개의 편의점 중, 갈 수 있는 곳을..

문제 링크입니다! https://www.acmicpc.net/problem/2611 2611번: 자동차경주 첫째 줄에는 지점의 개수 N이 주어진다. 각 지점에는 1부터 N까지의 서로 다른 번호가 부여된다. 둘째 줄에는 도로의 개수 M이 주어진다. 이어 M개의 줄에는 p ,q ,r의 형식으로 도로의 정보가 주어 www.acmicpc.net 위상정렬과 DP를 활용해서 최대 점수를 구하고, 경로를 구하는 문제였습니다. 예를 들어 1 -> 2 -> 3 -> 5 or 1 -> 4 -> 7 -> 5의 경로가 있다고 가정하겠습니다. 5번을 도착하기 위해서는 3번과 7번을 거쳐가는 2가지 방법이 있습니다. 이때 최댓값을 구하기 위해서는 3번까지 왔을 때의 값과 7번까지 왔을 때의 값을 비교하면 됩니다. 3번과 7번의 ..

문제 링크입니다! https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 1번 PD의 경우 1번 -> 4번 -> 3번 2번 PD의 경우 6번 -> 2번 -> 2번 -> 5번 -> 4번 3번 PD의 경우 2번 -> 3번 순으로 공연을 맡습니다. 1번을 방송하기 위해서는 선행이 없음으로 바로 방송할 수 있습니다. 2번의 경우는 6번을 먼저 방송 후 방송해야 합니다. 3번의 경우는 4번과 2번을 먼저 방송해야 합니다. 따라서 X번 -> ..

문제 링크입니다! https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 그래프를 사용한 DP 문제였습니다. 먼저 지을 수 있는 건물을 지은 다음, 해당 건물을 짓고 난 다음에 지을 수 있는 건물을 지어보는 식으로 최댓값을 찾아가는 문제였습니다. ex) 1 -> X , 2 -> X , 3 -> 2 , 4 -> 1,2 , 5 -> 1,3 (A -> B는 B를 짓고 나서 A를 지을 수 있다는 의미입니다.) 해당 경우, 1번과 2번을 먼저 짓습니..

문제 링크입니다! https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 1. 백조를 먼저 이동시켜본다. 2. 백조가 못만났을 경우 얼음을 녹인다. 3. 1번과 2번을 반복한다. -> 이 방법이 가장 생각하지 쉬운 방법입니다. 하지만 시간초과가 나는 방법이였습니다. 시간 초과가 나지 않는 다른 방법은 1. 백조를 이동시킨다. 2. 백조가 얼음을 만났을 경우 다음 탐색에서 시작할 좌표임으로 큐에 넣어준다. 3. 백조가 못만났..

문제 링크입니다! https://www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net BFS를 이용한 문제였습니다. 완전 탐색을 통해서 파도 -> 모래 확인 -> 이전 모래 확인을 반복한다면, 시간 초과가 나는 문제였습니다. (최악의 경우로서 1000*1000 배열에서 100번만 확인해도 1초가 넘습니다.) -> BFS를 통해서 '.'의 좌표에서 8방향으로 탐색한 뒤, 모래가 전부 사라지는 곳을 다시 BFS에 넣어주는 식으로 진행해야합..

문제 링크입니다! https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net DFS를 이용한 선택 + BFS를 이용한 탐색이 합쳐진 문제였습니다(연구소 문제의 심화문제 느낌이였습니다.) DFS에서 주의할 점이 Green, Red를 선택해야 하는데 겹치면 안된다는 것이였습니다. 따라서 저는 Green -> Red 로 선택해줬습니다. 예를들어 1, 2, 3, 4칸에 배양액을 놓을 수 있고, 초록색, ..

문제 링크입니다! https://www.acmicpc.net/problem/16397 16397번: 탈출 첫 번째 줄에 N (0 ≤ N ≤ 99,999), T (1 ≤ T ≤ 99,999), G (0 ≤ G ≤ 99,999)가 공백 하나를 사이에 두고 주어진다. 각각 N은 LED로 표현된 수, T는 버튼을 누를 수 있는 최대 횟수, G는 탈출을 위해 똑같이 www.acmicpc.net 간단한 BFS 문제였습니다. N -> G까지 A or B 연산을 통해서 최소 몇번을 통해서 갈 수 있는지를 물어보는 문제입니다. 99999보다 작다는 조건만 해주면 쉽게 풀 수 있는 문제였습니다. 문제 접근 방법 1. N에서 시작해 A, B 연산을 했을 때의 값을 찾는다. 2. 값들이 99999보다 작을 때, 이전에 방문하..

문제 링크입니다 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 연구소 1과 같이 DFS를 통해서 선택, BFS를 통해서 탐색을 하는 문제였습니다. 문제 조건과 출력예시는 위 링크를 참고해주세요! 문제 접근 방법 1. 입력과 같이 바이러스의 위치와 빈칸의 갯수를 저장한다. 2. 빈 칸의 갯수가 1개 이상일 때, 바이러스를 M개 만큼 선택해준다. 3. 바이러스가 M개 선택되었다면, BFS 탐색을 통해서 바이러스를 확산시킨다. 4. 빈 칸이 없다면 T를, ..

문제 링크입니다 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net BFS를 이용한 문제였습니다! 3차원 배열을 만든뒤, 0~8초까지의 벽의 움직임을 담고, 9방향 탐색을 하면 되는 문제였습니다. 문제 접근 방법 1. 벽의 위치를 vector를 이용해 저장합니다. 2. 벽의 갯수가 0개라면 1출력, 아니면 탐색을 시작합니다. 3. 0~8초까지 저장한 벽의 위치를 이용해 N초가 지났을때의 벽의 위치를 저장합니다. 4. 9방향 탐색을 통해서..

문제 링크입니다 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP문제였습니다. "RGB 거리1" 과는 다르게 N번과 1번의 색깔이 달라야한다는 조건이 추가되었습니다. 따라서 1번 집에 R,G,B를 선택했을때를 전부 확인한뒤, 최솟값을 비교해주면 됩니다! 문제 접근 방법 1. 1번 집의 R,G,B를 순서대로 선택한다. 2. R을 선택했을때 -> 2번 집의 G,B만 값을 구하고, R의 값에는 매우 큰 값을 넣는다. ..