초콜릿 파워

1. 크루스칼 알고리즘 최소 신장 트리를 구하는 알고리즘 중 하나이다. 1. 유니온 파인드 연산을 필요로 한다. 유니온 파인드 보러가기 >> 2.트리 그래프 : 순환을 갖지 않는 연결 그래프. 임의의 두 정점에 대해서 경로가 정확히 1개 존재함. 하나 이상의 정점을 가지며 임의의 간선 e를 제거한 그래프는 연결 그래프가 아니다. (연결 그래프: 모든 정점들을 간선을 통해방문할 수 있는 그래프 : 임의의 v, u 정점에 대해 path(v,u)가 존재하는 그래프) - 느낌: 그래프를 최소한의 간선으로 모두 연결해서 이동가능 할 수 있게 만든 것이되 사이클이 없는 것. - 특징: 전체 노드의 개수가 N개일때, 트리를 만들고 나면 전체 간선의 수는 N-1개가 된다. (1개의 경로로만 이루어져 있기 때문에) 3...

1. 플로이드 워셜 - 임의의 한 지점에서 다른 임의의 지점까지의 최단 거리를 구하는 알고리즘 (모든 지점에 대해 구할 수 있음: dist[V][V]) - 중간 지점을 통해서 최단거리를 갱신하는 알고리즘 - O(N^3)의 시간 복잡도: 3중 for문 - 사용가능한 시점: 시간 초과 제한에 걸리지 않을 때( 정점의 수가 약 500개 이하정도) - 다이나믹 프로그래밍 사용 : dist[i][j] = i에서 j 로 가는 거리라고 할 때, i -j의 최단경로가 i-k-j라면 i-k와 k-j도 최단경로이다. 점화식: dist[i][j](최단) = dist[i][k] + dist[k][j] - code for k

1. 유니온 파인드(Union Find) - 서로소인 집합들의 정보를 확인(find)하고 조작(union)할 수 있는 자료구조. - Union 연산 : 서로소인 집합을 '유니온' 연산을 통해서 같은 집합으로 만들 수 있다. - Find 연산 - 두 원소가 같은 집합에 속해있는지 확인할 수 있다. - 메쏘드 1. init - parent[N] 배열을 모두 자기 자신으로 초기화. 2. find - 루트를 반환하는 함수 - 재귀적으로 짤 수 있음 : 부모가 자신 일 때 종료. - 경로 압축: 변수에 결과를 반환받은 뒤, parent 를 갱신 후 다시 return 3. union - 두 원소를 받아서 한 집합으로 만드는 함수 - C++의 경우 union이라는 이름은 이미 있어서 다른 함수 이름으로 설정. - a..

시간 제한메모리 3 초 512 MB 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 1. 문제 해석 * 그래프 연결요소란? 그래프가 이어져 있는 노드끼리 같은 색으로 선을 긋다보면, 여러가지 색깔의 그룹이 생긴다. 그러한 그룹들을 그래프의 연결 요소들이라고 부른다. 쉽게 설명한 블로그 : https://velog.io/@kj..

문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. 출력 합이 0이 되는 쌍의 개수를 출력한다. 1. 문제 해석 늘 그렇듯이 브루트 포스부터 생각해볼 수 있다. 이 경우 합이 0이 되는지 안되는지 각 배열을 하나씩 탐색하면, N^4 꼴의 시간 복잡도가 나올 것이다. 따라서 이것은 매우 비효율적이므로 바로 패스. 그 다음으로 생각해볼 것은 배열의 합은 어차피 구해야 ..

사랑에 대한 어떠한 이론이든 인간른으로부터, 곧 인간 실존론으로부터 시작되어야 한다. 우리는 사랑, 또는 사랑과 비슷한 것을 동물에게서도 발견하지만, 동물의 애착은 동물의 본능적 기구의 일부에 지나지 않는다. 그러나 인간의 경우엔 다만 이러한 본능적 기구의 잔재가 작용하고 있음으로 볼 수 있을 뿐이다. 인간의 실존에 있어서 본질적인 것은 인간이 동물계로부터, 곧 본능적 적응의 세계로부터 벗어났고 자연을 초월해 있다는 사실이다. 인간은 자연의 일부이다. 그러나 한번 자연과 결별하면 인간은 자연으로 되돌아 가지는 못한다. 일단 낙원 -자연과의 본래의 합일 상태-에서 쫓겨나면, 다시 돌아가려 해도 불타는 칼을 가진 케루빔 천사가 길을 가로막는다. 인간은 철저하게 생실한 전 인간적 조화 대신에, 이성을 발달시키..

문제 ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다. 문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 또 모..

문제 백준이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 백준이가 정수를 하나씩 외칠때마다 동생은 지금까지 백준이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 백준이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. 예를 들어 백준이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 백준이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로..

문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. 출력 첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다. 1. 문제 해석 1.1. 투 포인터 알고리즘 포인터 2개(low, high) 를 이용해서 원하는 구간을 설정하면서 이동한다. - 정렬된 데이터 집합에서 합집합, 교집합 구하기..

모르는게 생기면 잘 아는 사람에게 물어보는 것이 가장 빠를 것입니다. 하지만 물어볼 사람이 없다면 ? 그때는 검색이 가장 빠른 방법일 것입니다. 검색을 잘하는 기술은 정말 중요합니다. 특히 IT 업계쪽에서는 매번 오류가 나는 문제, 새롭게 배우는 알고리즘을 이해할 때 어려움을 겪는 문제 등 여러가지 문제를 접했을 때 주로 검색을 통해 해결하죠. 또한, 질문을 하려고 할 때에도 먼저 검색을 통해서 혼자서 열심히 알아보았으나 잘 해결되지 않는 부분을 정리해서 질문을 해야지, 그냥 질문을 하면 사수나 상사가 눈살을 찌뿌릴 수도 있습니다. 따라서 검색을 효과적으로 하는 방법은 개발자에게 정말 중요하다고 할 수 있습니다. 하지만 내가 원하는 답을 찾으려면 몇가지 기술이 필요합니다. 저는 이 기술이 부족하다고 생각..