개발저장소

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 문제의 코드 버블 정렬을 C++로 구현한 알고리즘이다. 버블 정렬에서 swap이 한 번도 일어나지 않은 루프의 위치를 알아내는 코드이다. 버블 정렬에서 swap이 일어나지 않은 루프가 존재한다는 것은 정렬이 끝났다는 뜻이다. 그러므로 루프를 알아낸 즉시 반복문을 종료하는 것이 좋다. 정렬해야 하는 배열의 크기는 최대 500,000인 자연수이고, 요소의 크기는 최대..

문제 https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 숫자 중 왼쪽부터 1자리, 2자리, 3자리, ... N자리까지 모든 수가 소수가 되는 숫자를 모두 출력한다. ex) 7331 => 7, 73, 733, 7331 모두 소수이다. N은 1보다 크고 8보다 작다. 출력되는 소수는 오름차순으로 정렬한다. 1자리씩 점점 숫자를 늘려가며 소수인 경우만 가지를 뻗는 백트래킹 문제이다. 1자리는 2, 3, 5, 7만 가능하기 때문에..

문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 크기가 N인 수열 A가 있을 때, 각 원소 Ai에 대하여 Ai보다 오른쪽에 있으면서 큰 수 중에서 가장 왼쪽에 있는 수를 오큰수라고 한다. 수열 A가 있을 때, 각 원소들의 오큰수를 구해야 한다. 오큰수가 없다면 -1을 출력한다. 수열 A의 길이와 각 원소의 크기는 둘 다 1 이상 1,000,000 이하이다. 즉, 다중 for문을 사용한다면 무조건 시간 초과가 일어난다. 스택의 원리를 이해하고 이..

문제 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 풀이 N개의 수가 주어질 때, 어떤 수가 다른 두 수의 합으로 나타낼 수 있다면 "좋다"라고 한다. 주어진 N개의 수 중 좋은 수의 개수를 출력해야 한다. 같은 값의 수가 주어질 수도 있지만 서로 다른 수로 취급한다. N은 1에서 2000 사이이고, 주어지는 수는 |Ai| ≤ 1,000,000,000 의 정수이다. 투포인터를 사용해 N개의 수를 탐색하는 방법으로 풀었다. 이때, 수의 범위가 크므로 Long형 배열로 입력..

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 N개의 수열이 주어졌을 때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구한다. Ai + ... + Aj 가 M으로 나누어 떨어지는 순서쌍 (i, j)를 구해야 한다. Si % M과 Sj % M의 값이 같다면 (Si - Sj) % M = 0이 되는 성질을 이용해야 한다. 누적 합을 가장한 모듈러 산술에 대한 문제이다. ..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 길이 N의 수열에서 연속된 수들의 부분합 중에 S 이상을 만족하는 것 중, 가장 짧은 경우의 길이를 구한다. N의 범위는 10 이상 100,000 이하이고 S의 범위는 0 초과 100,000,000 이하이다. 입력되는 N이 많기 때문에 이중 for문을 사용한 풀이는 무조건 시간 초과가 일어난다. 투포인터를 사용하면 일차원 배열 위에서 인덱스가 움직이는 방식이기 때문에, 최..