내가 그때 이걸 알았더라면

1. 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 2. 해결 아이디어 1) 각 노드마다 갈 수 있는 최대 cost를 2개까지 저장한 뒤(재귀 방식이라 시간 복잡도 O(n)), 모든 노드의 최대 cost값 2개의 합을 비교하면서 가장 큰 최대 cost의 합을 출력한다. (= 트리의 지름) 한 노드에..

1. 문제 도현이는 컴퓨터와 컴퓨터를 모두 연결하는 네트워크를 구축하려 한다. 하지만 아쉽게도 허브가 있지 않아 컴퓨터와 컴퓨터를 직접 연결하여야 한다. 그런데 모두가 자료를 공유하기 위해서는 모든 컴퓨터가 연결이 되어 있어야 한다. (a와 b가 연결이 되어 있다는 말은 a에서 b로의 경로가 존재한다는 것을 의미한다. a에서 b를 연결하는 선이 있고, b와 c를 연결하는 선이 있으면 a와 c는 연결이 되어 있다.) 그런데 이왕이면 컴퓨터를 연결하는 비용을 최소로 하여야 컴퓨터를 연결하는 비용 외에 다른 곳에 돈을 더 쓸 수 있을 것이다. 이제 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라. 모든 컴퓨터를 연결할 수 없는 경우는 없다. https://..

1. 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 분석 및 아이디어 이 문제에서 까다로웠던 점은 트리에서 연결된 간선이 주어질 때 무방향으로 주어진다는 점이다. (누가 부모인지 알 수 없음) 그래서 필자는 트리를 루트부터 시작해 dfs로 탐색하면서 부모->자식 노드 연결을 끊어 주는 방식을 생각했다. 처음에는 인접 행렬 방식으로 무식하게 구현했는데, 이러면 답은 구할 수 있지..

문제 https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과..

참고한 블로그 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 알고리즘을 풀다 내가 삽입 정렬도 구현하지 못하는 것을 발견했고, 잊지 않고자 기록한다... 먼저 삽입 정렬이란 다음과 같다. (오름차순 정렬이라고 가정) https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列..

> 문제 https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자. > 풀이 문제 자체는 보기엔 간단해 보이지만, 1~n까지의 모든 문자열 각각에 대해 각 자리의 숫자를 카운트 해주면 시간초과가 나는 문제이다. 시간복잡도만 보자면 O(nlogn)인데 문자열 처리에 걸리는 시간에 n 0은 100~109, 200~209, .., 54200~542..

> 문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i 풀이 idea 1) m..

https://m.blog.naver.com/ndb796/221236874984 25. 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 ... blog.naver.com https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-sort [알고리즘] 그림으로 알아보는 위상 정렬(Topology sort) 위상정렬은 순서가 정해져 있는 노드..

> 문제 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효..

> 문제 문제 링크 : https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 문제 요약 : 총 n개의 방문자 수가 주어질 때, x일간 방문한 최대 방문자수와 그 방문자수가 있는 구간의 개수를 구하여라. > 풀이들 첫 번째 풀이 : 구간 x 안에 있는 사람들의 합을 각각 구하고, 그걸 n - x + 1번만 반복하면 되는 줄 알았다. 하지만 시간 초과가 떠서 다른 방법을 생각해야만 했다. (시간 복잡도가 O(n-x+1) * O(x) => O(x*..