henhen henhen

문제더보기문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.N개의 자연수 중에서 M개를 고른 수열입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다. 출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.풀이n, m = map(int, input().split())num = sorted(list(map(int, input().split())))visited = [0] * n# 방문 체크:..

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

문제더보기문제우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 ..

문제https://www.acmicpc.net/problem/1172더보기문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력첫째 줄에 연결 요소의 개수를 출력한다.풀이import syssys.setrecursionlimit(10 ** 7)input = sys.stdin.readlinen, m = map(int, input().split())graph = [[] for _ ..

문제https://www.acmicpc.net/problem/1012더보기문제차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 ..

문제더보기연결된 칸 찾기n x n 크기의 표에서 각 칸에 0또는 1의 값이 주어져 있습니다.1이 주어진 칸끼리 변을 공유하고 있다면 그 칸은 연결되어있다고 합니다.연결된 가능한 많은 수의 칸들의 개수를 모두 구하여, 각 개수를 오름차순으로 출력하는 프로그램을 작성해보세요. 입력 형식첫 번째 줄에는 n이 주어집니다,두 번째 줄부터 n개의 줄에 걸쳐 n개의 0또는 1이 공백을 두고 주어집니다.5 ≤ n ≤ 25출력 형식첫 번째 줄에는 연결된 칸들이 모인 집합의 개수를 출력합니다.두 번째 줄 부터 여러 개의 줄에 걸쳐 오름차순으로 각 집합에 속한 칸에 개수를 출력합니다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 ..

문제더보기정육각형으로 이루어진 배열정육각형의 형태로 이루어진 n x m 크기의 배열의 각 칸에 0 또는 1의 값이 주어져 있습니다.각 정육면체는 다음과 같이 이어져 있습니다. 색칠된 칸은 1의 값이 주어져 있는 칸입니다.1이 적힌 정육각형 칸들로 이루어진 집합의 겉을 둘러싸는 벽의 길이의 합을 구하는 프로그램을 작성해보세요. 정육각형의 한 변의 길이는 1 입니다.아래 그림에서는 붉은 선으로 표시된 부분이 겉을 둘러싸는 벽의 영역입니다. 입력 형식첫 번째 줄에 정수 n과 m이 주어집니다.두 번째 줄부터 n개의 줄에 걸쳐 m개씩 1 또는 0이 주어집니다.1 ≤ n, m ≤ 100출력 형식1이 적힌 정육각형 칸들로 이루어진 집합의 겉을 둘러싸는 벽의 길이를 모두 더한 값을 출력합니다. 코드트리 | 코딩테스트 ..

문제더보기연결된 그래프 2n개의 정점으로 이루어진 그래프에서 가장 많은 정점으로 갈 수 있는 노드들의 번호를 구하는 프로그램을 작성해보세요.각 간선은 양방향이 아닙니다. 입력 형식첫 번째 줄에 n과 m이 공백을 사이에 두고 주어집니다.두 번째 줄 부터 m개의 줄에 걸쳐 간선으로 연결된 두 정점의 번호가 A B 형식으로 주어집니다. 이 형식은 A는 B로 바로 갈 수 있다는 뜻입니다.1 ≤ n ≤ 1,0001 ≤ m ≤ 10,000출력 형식가장 많은 정점으로 갈 수 있는 노드를 출력하세요. 만약 그런 노드가 여러개라면 번호를 오름차순으로 공백을 사이에 두고 출력합니다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 ..

문제더보기연결된 그래프그래프의 연결된 두 노드들이 여러 개 주어졌을 때, 1번 노드와 연결된 모든 노드의 개수를 출력하는 프로그램을 작성해보세요. 입력 형식첫 번째 줄에는 노드의 총 개수 n와 연결된 노드 쌍의 개수 m이 공백을 사이에 두고 주어집니다.두 번째 줄부터 m개의 줄에 걸쳐 연결된 두 노드의 번호가 공백을 두고 한 줄에 하나씩 주어집니다.1 ≤ m ≤ n ≤ 100출력 형식1번 노드와 연결된 모든 노드의 개수를 출력합니다. 단, 자기 자신(1번 노드)은 제외합니다. 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 해결 1. 인접 리스트 생성n,..

DFS(Depth-First Search)> 깊이 우선 탐색으로, 그래프에서 수직 우선으로 탐색한다.그래프: 노드(Node)와 간선(Edge)으로 표현그래프 탐색: 하나의 노드를 시작으로 다수의 노드를 방문하는 것. 두 노드가 간선으로 연결되어 있을 때, 두 노드는 인접하다(Adjacent)라고 한다.인접 행렬(Adjacency Matrix): 2차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 연결되지 않은 노드끼리는 무한의 비용을 가정하여 값을 초기화한다.* 파이썬은 배열을 리스트 자료형으로 표현 가능하므로, 리스트로 구현하는 방식을 선택한다.인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식으로, 각 노드마다 연결된 노드에 대한 정보를 연결하여 저장 > DFS..