알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net deque에 관한 명령어를 알아보는 문제였습니다. 간단한 문제니 코드를 보면 이해가 쉽습니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include using namespace std; int N; deque dq; ..

문제 링크입니다. https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 간단한 이분 탐색 문제였습니다. 이분 탐색을 통해 해당 숫자가 있는지는 찾은 후, 해당 숫자가 존재한다면 똑같은 카드가 몇개인지를 찾는 문제입니다. 존재하는 것은 찾은뒤 -> for문을 통해서 몇개가 있는지 -> 시간초과가 됩니다. 따라서 중복되는 숫자가 몇개가 있는지를 이분 탐색 전에 확인해야합니다. 저는 배열 크기를 10,000,000 + 1..

드디어 백준 플레티넘을 달성했습니다. 올해안에 절대 못할거 같다고 생각했지만 결국에는 해냈네요. 간간히 찾아와주는 분들 덕분에 계속 블로그를 하고 있을 수 있는거 같습니다. 당분간은 rating을 올릴 수 있는 문제가 아닌 class를 채울 예정입니다. class 4를 꽉채운뒤 나머지는 생각해보겠습니다. 감사합니다.

문제 링크입니다. https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 기본적인 두 포인터 알고리즘 문제였습니다. S이상 합을 가질 수 있는 수열의 길이를 구하는 문제였습니다. low 와 high를 정한뒤, low ~ high까지 vector의 합을 구한 다음, S와 비교한 뒤, 값에 따라 low 와 high를 증가하면 됩니다. 자세한 것은 코드를 참고해주세요! #define _CRT_SECURE_NO_WARNINGS #include ..

문제 링크입니다. https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 에라토스테네스의 체 + 두 포인터가 합쳐진 문제였습니다. 1 ~ N까지의 수에서 소수를 판정한 뒤, 해당 소수의 값들로 N을 만들 수 있는지 확인하면 되는 문제였습니다. N의 범위가 최대 4,000,000 이여서 N*N크기의 2중 for문을 돌린다면 시간 초과가 생길 수 있습니다. 따라서 에라토스테네스의 체를 사용해주시면 됩니다. 소수 판정이 끝났다면 소수가 있을 때와 소수가 없을 때로 나누어서 계산해야합니다.(소수가 없을 때를 고려하지 않아 계속 런타임 에러가 생겼습니다..) 소수가 없을 때에는 ..

문제 링크입니다. https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 삼성 SW 역량테스트 문제였습니다. 2048 게임을 응용한 문제로, 상하좌우를 움직이는 것은 똑같지만 게임처럼 움직일 때마다 2가 생기지는 않습니다. 이때 나올 수 있는 최대 값을 구하는 문제였습니다. 먼저, 값이 더이상 변하지 않는 횟수가 몇 번인지를 찾아야합니다. 1줄에 최대 20개의 수가 주어질 수 있으니 한번 가정을 해보겠습니다. Case 1,..

문제 링크입니다. https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net DP 문제였습니다. N개의 행렬을 합치는데 필요한 최소 연산 횟수를 구하는 문제였습니다. 위와 같이 행렬이 곱해질 때는, 행렬이 (m,k)인 행렬로 바뀌게 됩니다. 이때의 연산 횟수는 m * n * k가 됩니다. 이점을 유의하고 점화식을 접근해 보겠습니다. (1 ~ N) 까지의 행렬을 연산 횟수는 많은 경우의 수가 있습니다. 그렇기에 모든 경우의 수를 확인할 수 없으..

문제 링크입니다. https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 꽤 어려운 DP 문제였습니다. 접근이 어려워 https://js1jj2sk3.tistory.com/search/11066 해당 블로그에서 접근 방법을 알았습니다. 먼저 고려해야할 것은 인접된 파일들만 겹칠 수 있다는 점입니다. 따라서 정렬을 한 뒤 합치는등, 배열을 섞으면 안됩니다. 따라서 메모리제이션을 통해서 DP를 풀어나가야 한다는 것입니다. 저는 Dp[i][j]인 ..

문제 링크입니다. https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net BFS와 이분 탐색을 사용해야하는 문제였습니다. N*N 배열에서 모든 편지를 전달하고 돌아올 때, 최소 피로도를 구하는 문제였습니다. 저는 N*N 배열의 값을 백터를 통해서 저장하고 정렬한 후 중복된 값을 전부 없앤 뒤, 범위를 (0 ~ 1), (0 ~ 2) 등으로 늘려가면서 이동할 수 있는 경로가 있는지를 확인했습니다. 출력 예시 - 예제 입력 3을 통해서 설..

문제 링크입니다. https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net BFS와 이분 탐색을 해야하는 문제였습니다. N*N 배열에서 (1,1) -> (N,N) 까지 도착하는데 경로 값의 최댓값과 최솟값의 차이의 최솟값을 구하는 문제입니다. 저는 N*N 배열의 값을 모두 저장한 뒤, 중복값을 없앴습니다. 그 뒤에 (0~0) -> (0~1)등으로 값을 늘려가면서 해당 범위에 있는 경로만을 통해서 갈 수 있게 만들었습니다. 문제의 ..

문제 링크입니다. https://www.acmicpc.net/problem/2479 2479번: 경로 찾기 길이가 같은 두 개의 이진수 코드 A와 B가 있다고 하자. 이 두 코드 사이의 해밍 거리는 A와 B의 각 비트를 왼쪽부터 오른쪽으로 차례대로 비교할 때 서로 다른 값을 가진 비트의 수이다. 예를 들 www.acmicpc.net 저는 2가지 방법으로 접근해서 풀었습니다. 1. 현재 지점에서 모든 이진 코드를 확인해, 1개가 차이날 경우 해당 지점을 탐색한다. 2. 모든 이진 코드를 1의 갯수로 나눈 뒤, 1의 갯수가 1개 차이나는 곳만 확인한다. 첫번째 방법은 짜기 쉬운 대신에 시간이 오래 걸렸고, 두번째 방법은 복잡했던 대신에 시간이 짧았습니다. 먼저 첫번째 방법부터 설명하겠습니다. 이진 코드를 s..

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net N*M의 값이 주어졌을 때, (i , j) 칸의 벽을 부셨을 때, 해당 칸에서 이동할 수 있는 곳은 몇 칸인지를 물어보는 문제입니다. 예를 들어 아래와 같은 입력이 주어졌을때, (1,1)의 벽을 허문뒤, 해당 칸에서 이동할 수 있는 곳의 갯수를 세는 것입니다. (1,1) 에서는 값이 4가 되겠습니다. 이와 같은 과정을 벽의 갯수 만큼 반복해주면 됩니다. 그렇다면 가장 쉬운 방..