[TIL] 230531 - 백준 알고리즘 문제풀이

오늘 한 것

- 백준 알고리즘 문제 풀이
11279번 : 최대 힙
11866번 : 요세푸스 문제0

---

백준 문제풀이

11279번 : 최대 힙(중)

2023.06.05 - [알고리즘/백준] - [백준] 11279번: 최대 힙 (Javascript, node.js)

[백준] 11279번: 최대 힙 (Javascript, node.js)

문제

일단 자료구조를 다 까먹어서(...) 힙이라는 게 무엇인지 먼저 찾아봤었다
 
힙이란?
- 우선 순위 큐를 위해 만들어진 자료구조로, 완전 이진 트리의 일종
- 최댓값이나 최솟값을 빠르게 찾아낼 수 있음
- 우선 순위 큐: 가장 먼저 들어온 데이터가 먼저 삭제되는 큐의 데이터에 우선순위를 도입하여 우선순위에 따라 데이터를 다루도록 하는 자료구조
- 완전 이진 트리:  모든 노드들이 둘 이하의 자식을 가지면서 모든 레벨이 완전히 채워져 있는 트리
- 부모 노드가 자식 노드보다 크거나 같은 최대 힙(max heap), 작거나 같은 최소 힙(min heap)이 있음
 
구현 방법
- 표준적으로 배열로 저장 
- 첫 인덱스 0은 사용하지 않음
- 노드 번호는 변하지 않음
- 부모/자식 노드의 관계

• (왼쪽 자식 인덱스) = (부모 인덱스) * 2
• (오른쪽 자식 인덱스) = (부모 인덱스) * 2 + 1
• (부모 인덱스) = (자식의 인덱스) / 2 

최대 힙
- 데이터 삽입

1. 새로운 요소가 들어오면 일단 마지막 노드에 삽입
2. 새로운 요소가 부모 노드보다 작거나 같아질 때 까지 부모 노드와 교환

- 데이터 삭제

1.  최댓값인 루트 노드를 삭제
2. 삭제된 노드에 힙의 마지막 노드를 가져옴
3. 마지막 노드와 자식 노드 중 큰 값을 비교하여 가능할 때 까지 교환  

시도 & 해결

이런 개념들을 가지고 이해하기 시작했지만 힙 구현 시작을 어떻게 해야할지 막막했는데, Jun님이 js로 구현된 최대 힙 클래스 코드와 함께 삽입 삭제 과정을 설명해주시면서, 삽입/삭제 함수만 구현해 보라고 기반을 딱 주신 덕분에!! 다른 데 힘 쏟지 않고 힙 이해와 삽입 삭제 과정 구현에 대해서만 고민해볼 수 있게 해주셔서 너무 감사했다.
 
우선 삽입 과정에서는 삽입된 노드(마지막)에서 부모 노드를 계속 거슬러 올라가면서 같아지거나 최대로 작아질 때 까지 교환해줘야 하는데 이 과정에서 부모 노드의 인덱스가 필요했다.
또 값을 교환해주려면 잠깐 값을 저장해 줄 빈 변수가 temp가 필요했다.
삭제 과정도 비슷하지만 조금 더 복잡한데, 마지막 노드를 루트로 올려준 후 우선 자식 노드 중 큰 것을 가려야 한다.
이를 위해 왼쪽/오른쪽 노드를 인덱스 규칙에 따라 저장해 주었고, 삼항연산자를 사용해서 bigger_child 변수에 큰 노드를 저장해 주었다.
그 후에는 또 temp를 이용해서 바꿔주고 교환이 안될때 까지 진행해주면 되었다.
진짜 C언어 처음 배울 때 배웠었던 교환 코드를 떠올리며 위의 과정에 따라 코드를 조금이나마 작성해 봤고 교환 과정은 잘 구현했었지만 노드를 거스르고 내려가면서 교환해주는 것이 안돼서, 재귀함수를 써서 각각 함수 내에 다시 함수를 불러와서 실행시키는 것으로 Jun님이 첨삭(?) 해주셨다.
또 자식 노드가 존재하지 않는 것 때문에 발생하는 에러는 삼항연산자를 사용하여 undefined 값일 때는 루트로, 아닐 때는 자식 노드 인덱스를 주어 해결할 수 있었다. 
 

알게된 점

- 최대 힙에 대한 개념과 자바스크립트에서 클래스를 사용하는 문법에 대해 대략 알게되었고 이는 따로 이노캠에서 주셨던 자바스크립트 책을 통해 정리해보려고 한다.
- 다른 언어로는 '/' 연산자를 사용했을 때 그냥 몫을 구하는 연산자라고 생각하고 있어서 js에서도 계속 그대로 썼고 값도 잘 나와서 오류를 못 느꼈는데, 알고보니 몫이긴 한데 실수로 나와서 정수로 바꿔주는 과정이 필요했다.
- 방법은 두 가지가 있는데 Math.floor(), parseInt()가 있다.

var a = Math.floor( 13 / 5)
var b = parseInt( 13 / 5)

---

11866번 : 요세푸스 문제0 (중)

2023.06.05 - [알고리즘/백준] - [백준] 11866번: 요세푸스 문제 0 (Javascript, node.js)

[백준] 11866번: 요세푸스 문제 0 (Javascript, node.js)

문제가 보기에는 쉬워보였는데 이상하게 머리가 안 돌아가서 배열에 1부터 값 넣어주기까지만 하고 멍때리고 있다가 ㅋㅋㅋㅋㅋ Jun님이 도와주셔서 사실 코드 보고 이해했다ㅋㅠ
입력값만큼 배열을 받아오고 입력받은 순서를 기준으로 -1 위치까지 배열을 돌려주면서 입력받은 순서에 해당하는 값을 빼면 된다.
돌려주는 방법은 앞 요소를 shift로 삭제해주고 다시 push해서 순서에 해당하는 요소가 첫 요소가 될때까지 돌려준다. 순서에 해당하는 요소 차례가 되면(i = 0) shift로 빼주고 그 값을 result에 저장한다. 배열 길이가 0이 될 때 까지 진행해준다.   
 
되게 신기하고 귀여운 문법을 알려주셨는데 while문 조건 내부에 (i --> 0) 으로 해주면 되게 직관적으로 i가 0이 될때까지로 이해하게 되는것이였다 ㅋㅋㅋㅋ 띄어쓰기만 조금 바꿔준건데 이렇게 의미가 바뀌다니,,, 1씩 증감되는 반복문 돌릴 때 for문보다 간편할 것 같아서 자주 쓰게 될 듯 하다.

---

참고자료

https://velog.io/@holicme7/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%9E%99heap-ktk49na9c3
https://velog.io/@dlgosla/CS-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC-Binary-Tree-vzdhb2sp
https://chancoding.tistory.com/237