nyunu

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 문제 ] N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수 중에서 M개를 고른 수열 [ 입력 ] 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. [ 출력 ] 한 줄에 하나씩 문제의 조건을 만족하는 수..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net [ 문제 ] 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. ..

[ 문제 ] 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. [ 입력 ] 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다. 입력의 마지막 줄에는 0이 두 개 주어진다. [ 출력 ] 각 테스트 케이스에 대해서,..

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 코드 구현 ) https://github.com/nyunu/BaekJoon/blob/main/11724.ipynb [ 문제 ] 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤..

💡 그래프 탐색 하나의 노드에서 시작하여 노드와 연결된 모든 정점들을 한 번씩 방문하는 것 💡 DFS (깊이 우선 탐색) DFS는 이름 그대로 깊이를 우선으로 탐색하는 방법이다. 전회 순회라고도 할 수 있는데 쉽게 말하면 아래 그림처럼, "루트 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리" 순으로 방문하는 방식이다. 그리고 이 과정이 재귀적으로 반복된다고 이해하면 된다. 왼쪽 서브트리에 방문하면 왼쪽 서브트리에서는 왼쪽 서브트리의 루트 노드를 먼저 방문하고 그 루트 노드의 왼쪽 서브트리 -> 오른쪽 서브트리를 방문하는 방식이다. 예시를 통해 더욱 쉽게 이해할 수 있는데, 만약 그래프가 위와 같다고 하면 DFS의 순회 순서는 0 - 1 - 2 - 3 - 4 - 5가 된다. 루트 노드의 0 방문 0이 루트..

https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 확인 ) https://github.com/nyunu/BaekJoon/blob/main/11724.ipynb [문제] 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. [출력] 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번..

[문제] 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임으로 다음의 게임 룰을 지켜야 한다. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때, N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서, 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. [입력 조건] 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1

[문제] 큰 수의 법칙이란 다양한 수로 이루어진 배열이 있을 때, 주어진 수를 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어, 2, 4, 5, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자. 이경우 특정한 인덱스의 수가 최대 세 번까지 더해질 수 있으므로, 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고, K가 2라고 가정하자. 이 경우 두번째 원소에 해당하..