알고리즘 모음(C++)

문제 링크입니다 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 삼성 SW 역량 테스트 문제입니다. 아기 상어는 위와 같은 규칙으로 움직입니다. 문제를 해결하기 위해서 구현해야 할 기능은 상, 하, 좌, 우로 움직이며 갈 수 있는 칸 찾기, 규칙에 따라서 갈 수 있는 칸 정렬, 아기 상어의 정보 변경하기를 구현해야 합니다. 1. 기본 설정 아기 상어가 갈 수 있는 칸 중에서 자신이 먹을 수 있는 물고기가 있을 수 있습니다. 그렇다면 그 ..

문제 링크 입니다 https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS 문제입니다. 이렇게 4개의 연산을 할 수 있는 할 수 있는 계산기가 있습니다. 이 계산기에는 0 이상 10000이하의 수를 저장할 수 있다고 할 때 수 A에서 수 B로 바꿀 수 있는 최소 횟수의 연산을 구하는 문제입니다. 각각 연산을 구현한 다음에 BFS를 통해서 A에서 B까지의 연산 과정을 저장하면 됩니다. 처음에 vector를 이용해 연산 과정을 저장했지만..

문제 링크입니다 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 가장 긴 증가하는 부분수열 4번과는 다르게 범위가 1,000,000입니다. 따라서 이중 for문을 사용한다면 시간초과가 ..

문제 링크입니다 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4입니다. 이때 가장 긴 길이인 4와 수열 10,..

문제 링크입니다 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 수열 S가 어떤 수 Sk를 기준으로 S1 Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 합니다. 예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, ..

문제 링크입니다 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 삼성 SW 역량 테스트 기출문제입니다. 만들어야할 배열의 크기는 작지만, 시간이 0.3초(c++기준)로 매우 짧습니다. 따라서 효율적이고 간결하게 만들어야 시간 초과를 피할 수 있습니다. 문제에서는 나무 재테크를 하려고 합니다. 봄, 여름, 가을, 겨울 각각의 계절마다 해야할 일이 전부 다릅니다. 1. 봄의 경우 나무가 자신의 나이만큼 양분을 먹고, 나이가 1 증가..

문제 링크입니다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 다이나믹 프로그래밍 문제였습니다. 문제만 읽으면 간단히 BFS, DFS로 풀 수 있는 문제지만 해당 알고리즘을 사용한다면 시간초과가 됩니다. 따라서 동적계획법과 회귀를 사용하여 푸는 문제입니다. 문제 조건입니다. 1. 자신이 있는 곳에서 상,하,좌,우 한곳으로 이동한다. 2. 이동한 곳에는 전에 있던 곳보다 대나무가 많아야한다. 3. 1,2조건을 만족하면서 최대한 오래 살..

문제 링크입니다 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택(stack)이란 기본적인 자료구조로 한쪽 끝에서만 자료를 넣고 뺄수 있는 LIFO(last in first out) 형식을 따릅니다. 스택 push, pop등 다양한 연산을 사용할 수 있습니다. push(num) -> num을 가장 위에 하나 추가한다. pop() -> 가장 위에 있는 항목을 제..

문제 링크입니다. https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A 4 -> 8 -> 81 -> 162 이와 같은 방법으로 최소 횟수는 5입니다. 1. 주어지는 수의 범위가 10^9이기 때문에 int 범위는 넘습니다. 따라서 long long 형으로 선언해줍니다. 2. 처음에 큐에 (A,0)를 저장해서 BFS를 시작합니다. 3. X*2, X*10+1 각각 B ..

문제 링크입니다 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 미세먼지의 위치와 공기 청정기의 위치가 주어지고 일정 시간이 지난 뒤 남은 미세먼지의 갯수를 구하는 문제입니다. 미세먼지의 확산 방법부터 보겠습니다. 미세먼지는 자신이 있는 위치에서 상하좌우로 퍼집니다.(위 사진과 같이 퍼집니다.) 공기 청정기의 순환 방식도 보겠습니다. 화살표를 따라 공기가 움직이고 미세먼지는 공기를 따라 움직입니다. 이때 미세먼지가 공기 청정기 안으로 빨려간다..

문제 링크입니다 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제의 조건입니다. 입력 받은 문자열이 폭발 문자열을 포함한다면 해당 문자열이 사라집니다. mirkovC4nizCC44 - 입력 받은 문자열 C4 - 폭발 문자열 이라고 한다면 mirkovC4nizCC44는 폭발 문자열을 포함하고 있기에 mirkovC4nizCC44 -> mirkovnizCC44 -> mirkovnizC4 -> mirkovniz 가 됩니다. 시간 제한..

문제 링크입니다 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 지민이의 이야기의 진실을 알고 있는 사람들을 피해서 거짓말을 말할 수 있는 파티의 최대 갯수를 찾는 문제입니다. 진실을 알고 있는 사람이 있는 파티는 거짓말을 하면 들통이 남으로 무조건 진실을 말해야하며 진실을 모르는 사람만 있는 파티인 경우에는 사람들이 진위 여부를 가릴 수 없어 지민이는 거짓말을 합니다. 진실을 알고 있는 사람들을 - A, B, C, D, E ..... 진실을 모르는 사람..