코딩 공부하는 코딩류

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

목표지점에 가기 위해서 내리막 길로만 가는 경로의 갯수 구하는 문제 문제의 조건 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다. 지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 ..

트리에 있는 노드들의 부모 노드를 찾아서 출력하는 문제 문제의 조건 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 풀이 과정 양방향 그래프를 구성한 뒤 DFS로 풀었습니다. 1. 2차원 배열을 만들고 입력 받으면서 양방향 그래프를 구성한다. 2. 각 정점의 부모 노드를 저장할 1차원 배열을 만든다. 각 정점 인덱스에 부모 노드 번호를 저장할 것이라서 정점 갯수+1 크기로 만든다. 3. 1번 정..

DFS 문제인데... 문제 설명이 좀 더 추가되었으면 좋겠는 문제(제발 쿨병 자제 좀...) 문제의 조건 1. 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 2. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 3. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. => 여기가 정말 설명이 애매한 곳이라고 생각하는데, 차라리 프로그래..

제목 그대로 DFS와 BFS로 그래프를 탐색한 결과를 출력하는 문제 문제의 조건 1. 주어진 그래프를 DFS와 BFS로 각각 탐색한 결과를 순서대로 출력하면 된다. 2. 단, 방문할 수 있는 정점의 개수가 여러 개면 정점의 수가 작은 것 부터 방문한다. 풀이 과정 처음에는 요즘 알고리즘을 공부하고 있는 책에 나와 있는 알고리즘을 썼는데... (대충 엣지 좌우 저장하는 구조체 만들고 전체 그래프를 구성하는 클래스를 만든 뒤 그렇게 만들어진 그래프 클래스를 이용해서 bfs와 dfs를 수행하는 내용 코드 길이가 A4 한 장 정도 됨) 알고 보니 모든 정점이 서로서로 연결되어 있다는 것을 전제로 한 알고리즘이라 이번 문제에는 맞지 않았습니다. 주륵 ㅠ.ㅠ 그리고 제게는 그것을 수정할 능력이 없었습니다...ㅋㅋㅋ..

주어지는 배열의 원소들을 합하거나 더해서 타겟 넘버로 만들 수 있는 모든 경우의 수를 찾는 문제 문제의 조건 1. 정수가 담긴 배열 numbers, 타겟 넘버 target이 주어짐 2. 배열의 모든 숫자를 이용해서 더하고 빼서 target과 같아지는 경우가 몇 개인지 구해서 리턴 #include #include using namespace std; int answer = 0; void dfs(vector& numbers, int target, int index = 0, int sum = 0) { //마지막 인덱스라면 if (index == numbers.size()-1) { //마지막 바로 앞 원소까지 더한 값에 마지막 원소를 더했을 때 target과 같아진다면 경우의 수 증가 if (sum + numb..