개발 블로그

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 두 개의 포인터를 이용해서 원하는 값을 추출하는 투 포인터 알고리즘 문제 입니다. 연속된 수들의 부분합 중에서 합이 S이상이 되는 것들 중에서 수열의 최소 길이를 구해야 합니다. 테스트 케이스를 예시로 설명 드리겠습니다. 10 15 5 1 3 5 10 7 4 9 2 8 start, end 변수를 두어 이를 조작하여 원하는 수열의 최소 길이를 구해야 합니다. sum(부분합) < S(원..

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 이 문제를 해결하기 위해 적용한 것은 에라토스테네스의 체, 투 포인터 알고리즘입니다. 에라토스테네스 체는 2의 배수(2는 제외, 소수이므로)부터 특정 수의 배수까지 걸러주는 알고리즘입니다. 출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 수학에서 에라토스테네스의 체는 ..

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 DFS + Bruteforce 문제입니다. 중복 값을 제거해주는 Set를 선언해줍니다. 그리고 길이가 6이 될 때 까지 값을 하나씩 추가해줘야하는데, 예시를 들어 값이 112에서 1을 추가한다면 112(기존 값) * 10 + 1(새로운 값)이 되어야 합니다. 그래서 함수 세 번째 파라미터에서 함수 num * 10 + a[nx][ny]를 호출해주었습니다. ..

https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 이 문제는 A, B, C의 각각의 친구의 수의 최솟값을 구하는 문제입니다. 우선적으로 A, B가 친구 관계인지 check해주고, A, B가 친구인 경우에 C가 친구인 경우를 구한다면, 시간 복잡도를 O(N^3)에서 O(N^2 + MN)으로 최소화할 수 있게 됩니다. #include using namespace std; int a[4001][4001]; i..

https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 주어지는 입력값은 아이스크림의 종류와 조합해서 안 되는 아이스크림의 종류 개수입니다. 예시를 들어 조합해서는 안 되는 아이스크림이 1번, 3번이면 check[3][1], check[1][3]을 true로 바꿔줘야 합니다. 왜냐하면 1번, 3번이나 3번, 1번이나 같은 의미이기 때문입니다. 만약 검사를 하고 check변수가 false이면 개수를 하나씩 늘려주면 ..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 이 문제는 c++에 내장되어 있는 next_permutation을 사용하면 간단하게 풀 수 있는 문제입니다. A, B를 입력받고, A의 순서를 뒤바꿔서 C보다 작은 최대 수를 구하는 문제입니다. 우선적으로 A를 문자열로 입력받습니다. 그리고 next_permutation을 이용하여 순열을 하나씩 구하고 stoi함수를 통해 숫자로 파싱 시켜주고 B와 비교해서 작으면 값을 지속..

https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net 이 문제는 해당 격자판에서 다음과 같은 십자가를 몇 개 만들 수 있는지 물어보는 문제입니다. 해당 인덱스에서 상하좌우 비교해서 *가 된다면 해당 부분과 크기를 push 해주면 되는 간단한 문제지면 예외의 경우가 존재합니다. 예외 케이스 * *** * * 다음과 같은 부분은 제일 아래쪽 *이 크기가 1인 십자가에 속하지 않기에, -1을 출력 해줘야 합니다. 이러한 경우를 방지하기 위해 ch..

https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 이 문제는 곱2, 나3이 섞인 수열이 존재하면, 순서에 맞는 수열을 찾는 문제입니다. 여기에서 핵심은 각 수를 소인수분해 했을 때, 3의 인수가 가장 많은 수가 제일 앞에 와야 합니다. 왜냐하면, 인수가 3이 많게 되면, 그다음 수도 자연스럽게 3으로 나누어 떨어지기 때문입니다. 그리고 3의 인수가 동일하다면 오름차순 정렬해주면 됩니다. (3의 인수가 동일한 경우에는 곱하기 2를..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 비교적 간단한 브루트포스 문제였습니다. 우선적으로 I,V,X,L을 사용하여 만들 수 있는 로마 숫자의 개수를 반환해야 합니다. 그런데 for문을 4번 돌리게 된다면, 시간 복잡도가 O(n^4)이 되기 때문에 다른 방안을 생각해야 합니다. I+V+X+L = n(사용할 로마 숫자 개수)이 되어야 합니다. 그러면 가장 큰 수를 나타내는 L의 개수는 n-X-V-I가 됩니다. 나머지 부분은 가장 작은 수 I부터 n까지 탐색하고, V는 n-I까지, X는 n-I-V까지 탐색해서 만들 수 있는 로마 숫자의 ..

https://www.acmicpc.net/problem/16917 16917번: 양념 반 후라이드 반 현진 치킨에서 판매하는 치킨은 양념 치킨, 후라이드 치킨, 반반 치킨으로 총 세 종류이다. 반반 치킨은 절반은 양념 치킨, 절반은 후라이드 치킨으로 이루어져있다. 양념 치킨 한 마리의 가격은 www.acmicpc.net 문제에서 주어지는 입력 값은 양념치킨 값, 후라이드 치킨 값, 반반 치킨 값, 만들어야 할 양념치킨, 후라이드 치킨의 개수이다. 이 문제에서 신경 써야 할 부분은 반반 치킨이다. 반반 치킨을 기준으로 완전탐색(브루트 포스)을 하여 최소 금액을 구할 수 있게 됩니다. #include #include using namespace std; int main() { int a,b,c,x,y; c..