본문 바로가기

전체 글105

[자료구조] 힙 (Heap) C/C++ 구현 - 알고리즘 // 최소 힙, 최대 힙 요즘 heap (min heap, max heap) 관련 과제 요청이 많이 들어와서 힙 자료구조에 대해 글을 써봅니다. 힙은 이진트리 (Binary Tree)로 구성할 수 있으며 트리 구조체로 구현하거나 또는 1차원 배열로 쉽게 구현할 수 있습니다. 구현 시 하나의 규칙만 지켜주면 되는데 최소 힙은(min heap) 부모가 자식보다 값이 작아야 하며 최대 힙은 (max heap) 그 반대입니다. 이진트리의 형태를 띄고있어 루트 노드를 1번 정점이라고 한다면, 자식 노드는 각각 2, 3 번 노드가 됩니다. 여기서 알 수 있는건 부모 정점의 번호가 n이라면 왼쪽 자식의 번호는 2*n, 오른쪽 자식의 번호는 2*n + 1 의 규칙을 띄고있습니다. 노드 번호를 배열의 인덱스로 한다면 아래와 같이 1차원 배열로 .. 2021. 6. 3.
[BOJ] 백준 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 n개의 동전의 가치가 주어질 때 동전을 원하는 대로 사용하여 k원을 만드는 경우의 수를 구하는 문제입니다. 동적 계획법 관련 문제들에서 이 문제와 유사한 문제들이 가끔 출제되며 이 문제를 잘 이해하고 풀면 0/1 배낭 문제 또한 쉽게 풀 수 있습니다. 풀이 쉽게 접근해 보기 위하여 dp [i][j]를 0~i 번째 동전을 사용하여 j원을 만들 때 적어도 한 개의 i번째 동전을 사용하는 경우의 수.. 2021. 3. 24.
리마스터 후 불독 무릉 // 54 -> 57층! 불독만세! 빌드 인피는무조건 돌리기 19층 도퍼 40층에서 길스 방무 쓰기 46 레비아탄- 링썸 47 도도- (리커) 48 릴리노흐- (웨펖) 49 라이카- (크뎀) 50 핑크빈- (리레) 51 락스피릿 -(링썸) 52 거미- (웨펖) ★어댑팅★★★바인드 끝나고 무적비★★★★ 53 드래고니카(빨간용)- (리커) 54 드래곤라이더(흰털)- (리레) 55 쪼그만해적- (링썸) 56 가면쓴 박쥐- (웨펖) 57 후드쓴 활- (크뎀) // 바인드가없으니 크뎀링으로 수정 58 후드쓴지팡이- (리레) 2021. 2. 2.
[BOJ] 백준 1517번: 버블소트 www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1≤N≤500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0≤|A[i]|≤1,000,000,000의 범위에 들어있다. www.acmicpc.net 문제 N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오. 버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므.. 2021. 1. 11.

티스토리툴바