0과1

1. 문제정의 최소 신장 트리 ( Minimum Spanning Tree )란? 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다. BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다. MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다. 2. 문제 설계 Prim's 알고리즘Prim's 알고리즘은 최소 우선순위 큐에서 가중치가 가장 작은 정점을 선택한 후,그 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값을 갱신할 지 말지 결정합니다. 3. 구현 #include #include #define V 9 //다음에 수행할 정점을..

1. 문제정의 최소 신장 트리 ( Minimum Spanning Tree )란? 최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다. BFS , DFS는 각 규칙에 따라 모든 정점들을 연결하는 트리를 생성했었습니다. MST도 마찬가지로 모든 정점들을 연결하는 트리를 생성하는데, 이 때 규칙은 최소한의 비용이 되는 그래프가 되도록 하는 것입니다. 2. 문제 설계 Kruskal's 알고리즘Kruskal's 알고리즘은 두 개의 트리를 연결하는 모든 간선 중 가장 작은 간선( u , v )를 찾아 MST의 부분집합에 추가합니다. Kruskal's 알고리즘은 안전 간선을 연결할 때 Union - Find 자료구조를 이용합니다. 3. 구현 include #include..

1. 문제정의 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다. 0번 스위치 -> 0, 1, 2 시계와 연결됨 1번 스위치 -> 3, 7, 9, 11 시계와 연결됨 2번 스위치 -> 4, 10, 14,15 시계와 연결됨 3번 스위치 -> 0, 4, 5, 6, 7 시..

1. 문제정의 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. 입력 력의 첫 줄에는 테스트 케이스의 수 C (C 1) //겹쳐질 경우 ok = false; } return ok; } //board의 모든 빈 칸을 덮을 수 있는 방법의 수를 반환 //board[i][j]=1 이미 덮인 칸 혹은 검은 칸 //board[i][j]=0 아직 덮이지 ..

1. 문제정의 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다. (태연,제시카) (써니,티파니) (효연,유리) (태연,제시카) (써니,유리) (효연,티파니) 입력 입력의 첫 줄에는 테스트 케이스의 수 C ..

1. 문제정의 최근 개인 사업을 시작한 광성이는 매일 아침마다 은행에 가서 동전과 지폐들을 교환해 오는 것이 일이다. 현금으로 물건 값을 지불할 경우 조금 더 싸게 한 덕분에 현금으로 구입하는 사람이 많은데, 대부분의 손님들이 물건 값보다는 더 많은 돈을 내서 꼭 거스름돈이 필요해지는 일이 발생하기 때문이다. 그래서 최대한 적은 지폐랑 동전을 사용하여 거스름돈을 주고 싶은데, 광성이를 위해서 물건값과 받은 금액이 주어졌을 때, 거스름돈으로 지불할 지폐 혹은 동전의 최소 개수를 출력하는 프로그램을 작성하시오. 입력 첫줄에는 테스트 케이스 수 둘째 줄부터 T + 1번째 줄까지는 물건의 값과 받은 금액이 주어진다. 출력 각 줄에 하나씩, 거스름돈으로 줄 5만원권, 1만원권, 5천원권, 1천원권, 5백원, 10..

1. 문제정의 전산학에서 트리 순회(Tree traversal)는 트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다. 이는 노드를 방문하는 순서에 따라 분류된다. 여기서 설명하는 알고리즘은 이진 트리에 대해서 작성되었지만, 다른 모든 트리에서도 일반화될 수 있다. 2. 문제 설계 연결 리스트와 1차원 배열과 같은 선형 자료 구조에서는 한 가지의 논리적인 순회 방법만이 존재하지만, 트리 구조의 순회에는 많은 방법이 존재한다. 이진 트리의 루트 노드에서 시작해서, 세 가지 주요 단계를 거치며 순회를 진행하는데, 그 단계에는 현재 노드를 방문하는 것, 왼쪽 자식 노드를 순회하는 것과 오른쪽 자식 노드를 순회하는 것이 있다. 이러한 과정은 재귀로 쉽게 설명할 수 있다. 전위..

1. 문제정의 LCS란 Longest Common Subsequence의 약자로 최장 공통 부분 문자열이다. 우리가 알고 있는 substring과 비교하면 substring은 연속된 부분 문자열이고 subsequence는 연속적이지는 않은 부분 문자열이다. 예로 들어 Iamhungry라는 문자열에서 연속된 부분 문자열인 mhun은 substring이 되고 연속적으로 이어지지는 않았지만 순서는 맞는 mugy는 subsequence가 된다. 그러면 LCS는 어디에 쓰일까? 대표적으로 LCS가 쓰이는 곳은 염기서열 유사성 분석이다. 이외에도 음파 단어 검색 및 교정 등에 사용된다. 2. 문제 설계 Dynamic Programming기법으로 문제를 해결하여 두 문자열 크기에 해당하는 2차원 배열의 값을 채우므로..