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. 시간 : 알고리듬의 수행 속도의 특성을 분석 2. 공간 : 알고리듬의 메모리 사용 특성을 분석 -> 시간이 빠르면서 메모리도 더 적게 사용하는 알고리듬이 이상(理想)! BUT! 두 기준은 서로 상충하는 경우가 많다. 즉, 메모리 사용량을 희생해 속도를 높이거나, 속도를 희생해서 메모리 사용량을 줄여인 알고리듬들을 훨씬 자주 볼 것이다. 시간복잡도 분석(Time complexity) 알고리듬의 수행 속도를 측정하는 방법 1. 프로그램의 수행 시간을 측정(Timer) -> 가장 직관적인 방법이지만 하드웨어, 사용 언어, 운영체제 등 외부 요소가 시간에 영향을 미치므로 부적합! 2. 수행 시간 기준 기본적인 연산의 수 비교 (ex. 사칙연산, 대소비교, 대입연산) -> 가..

알고리듬? 어떠한 문제를 해결하기 위한 일련의 절차를 공식화한 형태로 표현한 것 ※ 좋은 알고리듬은 아래 특징을 따른다. 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 타당성 : 구현할 수 있고 실용적이어야 한다. 입력 : 정의된 입력을 받아들일 수 있어야 한다. 출력 : 답으로 출력을 내보낼 수 있어야 한다. 유한성 : 특정 수의 작업 이후에 정지해야 한다. 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 알고리듬 구현 방식? 자연어, 의사코드, 순서도, 프로그래밍 언어로 다양 알고리듬 개발의 정형적인 단계 문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화 즉,..