💻

문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 ..

문제 동혁이는 나무 조각을 5개 가지고 있다. 나무 조각에는 1부터 5까지 숫자 중 하나가 쓰여져 있다. 또, 모든 숫자는 다섯 조각 중 하나에만 쓰여 있다. 동혁이는 나무 조각을 다음과 같은 과정을 거쳐서 1, 2, 3, 4, 5 순서로 만들려고 한다. 첫 번째 조각의 수가 두 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 두 번째 조각의 수가 세 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 세 번째 조각의 수가 네 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 네 번째 조각의 수가 다섯 번째 수보다 크다면, 둘의 위치를 서로 바꾼다. 만약 순서가 1, 2, 3, 4, 5 순서가 아니라면 1 단계로 다시 간다. 처음 조각의 순서가 주어졌을 때, 위치를 바꿀 때 마다 조각의 순서를 출력하는 프로그..

문제 어린 토니킴은 색칠공부를 좋아한다. 토니킴은 먼저 여러 동그라미와 동그라미 두 개를 연결하는 직선들 만으로 그림을 그리고 (모든 동그라미들 사이에 직선이 있을 필요는 없다), 연결된 두 동그라미는 서로 색이 다르게 되도록 색을 칠하고자 한다. 이 그림을 색칠하는데 필요한 최소의 색의 개수를 구하는 문제는 어렵기 때문에 토니킴은 2 가지 색상으로 색칠이 가능한지의 여부만을 알고 싶어한다. 동그라미들의 번호와 동그라미들이 서로 연결된 직선에 대한 정보가 주어졌을 때, 이 동그라미들이 2 가지 색상으로 색칠이 가능한지 알아내자. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T 가 주어진다. 그 다음 줄부터 각 테스트 케이스에 대해 동그라미의 개수 n(n n >> m; bool cir[1001][1001]..

문제 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. 예제 입력1 5 0 -7 -3 -2 5 8 예제 출력1 1 생각 이 문제의 경우는 n이 20까지이므로 재귀함수로 풀면 될 것 같았다. 재귀호출되는 과정을 구하면 다음과 같다. 인덱스를 증가시키면서, 해당 원소를 sum에 더하거나 혹은 더하지 않거나 이므로 ..

너비우선탐색(BFS= Breadth First Search) 는 너비를 우선으로 탐색하는 알고리즘입니다. 기본적으로 큐(Queue)를 이용하여 구현합니다. 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다 2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드들을 모두 큐에 삽입하고, 방문 처리를 합니다 . 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복합니다. 너비 우선 탐색은 큐(Queue)자료구조에 기초한다는 점에서 구현이 간단합니다. 실제로 구현함에 있어 큐 STL을 사용하면 좋으며 탐색을 수행함에 있어서 O(N)시간이 소요됩니다. 일반적인 경우 실제 수행 시간은 DFS보다 좋은 편입니다. #include #include #define INF 999999999 ..

깊이 우선 탐색(DFS=Depth First Search) 기본적으로 전체 노드를 맹목적으로 탐색하고자 할 때 사용합니다. 깊이 우선 탐색은 스택(Stack) 자료구조에 기초합니다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 합니다. 2. 스택의 최상단 노드에게 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리를 합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다. 3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복합니다. #include #include #define MAX_SIZE 1001 typeder struct{ int index; struct Node *next; } Node; Node** a; int n, m, c[MAX_SIZE..

그래프란 사물을 정점(Vertex)과 간선(Edge)으로 나타내기 위한 도구입니다. 그래프는 2가지 방식으로 구현할 수 있습니다. 1) 인접행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식 2) 인접리스트(Adjacency List) : 리스트를 사용하는 방식 무방향 비가중치 그래프와 인접 행렬 - 모든 간선이 방향성을 가지지 않는 그래프를 무방향 그래프라고 합니다. - 모든 간선에 가중치가 없는 그래프를 비가중치 그래프라고 합니다. - 무방향 비가중치 그래프가 주어졌을때 연결되어 있는 상황을 인접 행렬로 출력할 수 있습니다. #include int a[1001][1001]; int n,m; int main(void){ scanf("%d %d", &n, &m); //간선의 개수 for..

문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 출력 첫째 줄부터 V개의 줄..