오늘은 여기까지

1. 신장 트리 (Spanning Tree)그래프 내 모든 정점을 포함하는 트리다. 그래프의 최소 연결 부분이다.모든 정점이 연결되어 있음사이클이 존재하지 않음간선의 개수 = 정점의 개수 - 1DFS, BFS를 이용하여 그래프에서 Spanning Tree를 찾을 수 있다. 탐색 도중 사용한 간선만 모으면 된다.하나의 그래프는 여러 개의 Spanning Tree를 가질 수 있다.2. 최소 신장 트리, (Minimum Spanning Tree)Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리모든 정점이 연결되어 있음사이클이 존재하지 않음간선의 개수 = 정점의 개수 - 1간선들의 가중치 합이 최소그리디 알고리즘을 사용하는 대표적인 트리 형태의 자료구조3. MST 구현 방법3.1 크루스칼..

https://www.acmicpc.net/problem/2870 출처: COCI 2010/2011 Contest #2 문제숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다. 첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알..

그리디 알고리즘문제 해결 과정에서 단계마다 눈앞에 최선의 선택을 하고, 선택은 번복하지 않는다.그리디 알고리즘이 최적해를 보장하려면?최적 부분 구조: 부분해를 푸는 과정이 최적해를 구하는 과정과 일치그리디 선택 속성: 선택 과정이 다른 과정에 영향을 주지 않음배낭 문제부분 배낭 문제짐을 쪼갤 수 있는 배낭 문제를 가정하자.배낭에 담을 수 있는 최대 무게가 존재하고, 무게와 가치가 다른 짐들이 있다. 이 짐들을 조합해서 배낭의 무게를 초과하지 않으면서 담은 가치를 최대로 하는 문제를 배낭 문제라고 한다.부분 배낭 문제는 무게당 가치가 높은 짐을 최대한 많이 넣는 그리디 알고리즘을 사용하면 된다.짐별로 무게당 가치를 구한다무게당 가치가 높은 짐부터 넣을 수 있는 만큼 배낭에 넣는다배낭 용량이 짐 무게보다 크..

https://www.acmicpc.net/problem/2876문제 출처: COCI 2010/2011, Contest #1 문제교실에는 N개의 책상이 일렬로 놓여있고, 한 책상에 학생 2명이 앉는다.교수는 퀴즈를 채점할때 점수 등급마다 다른 색상의 연필로 채점한다. 오늘 교수는 한 가지 색연필만 가져왔기 때문에 아래와 같은 방법으로 채점하려고 한다.책상 2개를 선택하여 해당 범위 내 책상마다 한 명의 학생을 선택한다. 이때 양끝의 책상 또한 포함한다.한 가지 색연필만 가져왔기 때문에 고른 학생들 모두 같은 점수를 가져야 한다.교수가 한 가지 색만을 이용해 채점할 수 있는 최대 학생 수와 그때의 점수 등급을 출력한다.만약 답이 여러 가지라면, 가장 작은 점수 등급을 출력한다. 입력의 첫 번째 줄에는 정수..

https://www.acmicpc.net/problem/1010 개념: dp, 조합 문제재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 ..

https://www.acmicpc.net/problem/2839 출처: COCI 2010/2011 Contest #7 문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 첫째 줄..

https://school.programmers.co.kr/learn/courses/30/lessons/133027 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제다음은 아이스크림 가게의 상반기 주문 정보를 담은 FIRST_HALF 테이블과 7월의 아이스크림 주문 정보를 담은 JULY 테이블입니다. FIRST_HALFNAMETYPE NULLABLESHIPMENT_IDINT(N)FALSEFLAVORVARCHAR(N)FALSETOTAL_ORDERINT(N)FALSE JULYNAMETYPE NULLABLESHIPMENT_IDINT(N)FALSEFLAVORVARCHAR(N)FALSETOTAL_ORDERIN..

https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 개념: 이분탐색 문제 설명디딤돌의 숫자는 한 번 밟을 때마다 1씩 줄어든다.디딤돌의 숫자가 0이 되면 더 이상 밟을 수 없고, 이때는 그 다음 디딤돌로 한번에 여러 칸을 건너 뛸 수 있다.무조건 가장 가까운 디딤돌로만 건너뛴다.한 번에 한 명씩 징검다리를 건너야 하며, 한 명이 징검다리를 모두 건넌 후에 그 다음 사람이 건너기 시작한다.징검다리를 건너야 하는 사람들의 수는 무제한이라고 간주한다.디딤돌에 적힌 숫자가 순서대로 담긴 배열 `ston..

https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.한 번에 한 명씩 신청한 순서대로 방을 배정합니다.고객은 투숙하기 원하는 방 번호를 제출합니다.고객이 원하는 방이 비어 있다면 즉시 배정합니다.고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 ..

https://school.programmers.co.kr/learn/courses/30/lessons/62050 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 개념: bfs, 정렬 문제 설명N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다. 이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 ..