네이스

문제 링크입니다 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. www.acmicpc.net DFS, BFS 중 어느것이든 상관없이 원하는 방법으로 그래프 순회를 해서 나누어진 그래프(연결 요소)가 몇 개인지 구하는 문제였습니다. DFS를 통해 문제를 해결하였습니다. 주석 참고해주세요! [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..

문제 링크입니다 https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 연산자의 개수는 N-1보다 많을 수도 있다. 모든 수의 사이에는 연산자를 한 개 끼워넣어야 하며, 주어진 연산자를 모두 사용하지 않고 모든 수의 사이에 연산자를 끼워넣을 수도 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 www.acmicpc.net 저번에 풀어봤던 연산자 끼워넣기와 거의 비슷한 문제였습니다. 연산자 끼워넣기에서는 입력으로 주어지는 연..

문제 링크입니다 https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 재귀 함수를 이용해 모든 경우를 탐색하는 방식으로 문제를 해결했습니다. 합이 0인 부분집합을 찾을 때, 크기가 양수인 부분집합을 찾아야 한다는 사실을 주의해서 풀어야 했습니다. 자세한 설명은 주석을 참고해주세요. [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26..

문제 링크입니다 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 재귀 함수를 이용해 모든 경우를 탐색하는 방식으로 문제를 해결했습니다. 두 가지 방법으로 구현하였습니다. 자세한 설명은 주석을 참고하시면 될 것 같습니다! [소스코드 1] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 4..

문제 링크입니다 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 재귀 함수를 이용해 문제를 해결했습니다. 두 가지 방법으로 풀어봤습니다. 첫 번째 방법은 - 인자를 받지 않는..

문제 링크입니다 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19) 우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1 www.acmicpc.net 변수 3개를 각각 1씩 증가하되, 주어진 조건에 나와있는 수를 넘어가면 다시 1로 바꿔주면서 입력받은 수와 같아지면 그..

문제 링크입니다 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 1. 입력받은 9명의 난쟁이들의 키를 모두 더해줍니다. 2. 난쟁이들의 키를 저장할 배열을 오름차순으로 정렬해줍니다. 3. 키들의 합이 100인 난쟁이 7명을 고르는 문제인데, 9명 중 2명을 고르고 남은 난쟁이들의 키의 합이 100인 경우를 찾는것과 동일하므로, 2중 for문을 통해 모든 키의 합에서 두 명의 키를 뺀 값이 100인 경우를 찾습니다. 4. 제일 먼저 찾은 경우를 출력하고 ..

문제 링크입니다 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에 이동하 www.acmicpc.net 1. 낚시왕을 오른쪽으로 한 칸씩 이동하며 각 열에서 땅과 제일 가까운 상어를 잡는다. 2. 잡은 상어는 map에서 없..

문제 링크입니다 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 전형적인 BFS 문제였습니다. BFS를 통해 (0, 0) 부터 방문할 수 있는 칸(1)으로만 이동하여 최소 몇 칸을 방문해야 (N - 1, M - 1)까지 이동할 수 있는지 찾으면 되는 문제였습니다. [소스코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41..