220408 금 Algorithms TIL

백준 힙 11279번 최대 힙 실버2

• 문제
• 코드

백준 1655번 가운데를 말해요 골드2

• 문제
• 코드

푼 것

• 작은 수를 max힙에 넣어두고, 큰 수를 min힙에 넣어둔다.
• 두 힙의 개수를 최대한 똑같게 만들되, 홀 수라면 max힙에 넣는다.
• max힙의 max값이 가운데 수
• 만약 max힙에 넣으려고 하는데, min힙의 최소값보다 num의 값이 크다면 min힙에서 하나를 빼서 max힙에 넣어준 다음에 min힙에 num을 넣는다
• 반대도 마찬가지

기타

https://velog.io/@bongf/220206-Algorithms-TIL#%ED%9E%99---3000-%EC%A4%91%EA%B0%84%EA%B0%92-%EA%B5%AC%ED%95%98%EA%B8%B0 지난 번에 이 문제와 유사

백준 18258번 큐2 실버4

• 문제
• 코드

푼 것

• 직접 구현 한 것 보다 dequeue를 쓴 것이 조금 더 빨랐다.

백준 2164번 카드2 실버4

• 문제
• 코드

백준 이진탐색 1920번 수찾기 실버4

• 문제
• 코드

백준 이진탐색 2805번 나무 자르기 실버3

• 문제
• 코드

푼 것

• sort()를 안해도 되는데 자꾸하네

백준 2630번 분할정복 색종이 만들기 실버3

• 문제
• 코드
• 코드-자바

배운 것

• 저번 z문제 도 그렇고 종이 자를 때 그걸로 새로운 배열을 만들려하지 말고 r, c 값을 넘기자

종이 자르기

• 나는 시작, 끝의 행 열의 index 4개를 다 넘겨줬는데 사실, 시작점과 size만 넘겨주면 된다.
• 그리고 같은 색인지 아닌지 확인하면서 사실 한 번씩 순회하게 되므로, 4개씩 자르면서 같은 색이 아니면 4개 씩 잘라서 또 확인 보다는 가장 작은 사이즈로 자른 후에 합치는 것이 낫다 "분할정복" 문제니까 (병합 정렬을 생각하자)

백준 1629번 분할정복 곱셈 실버1

• 문제
• 코드-파이썬
• 코드-자바

푼 것, 배운 것

• long의 범위를 초과하지 않게 중간 중간 나누는 것이 중요하고,
• 분할정복이라는 개념이 머리에 들어오는 것이 어려운 것 같다.
• 모듈러 연산과 지수 법칙을 활용하는 것
• https://st-lab.tistory.com/237 풀이와 https://velog.io/@grace0st/%EA%B3%B1%EC%85%88-%EB%B0%B1%EC%A4%80-1629%EB%B2%88-%ED%8C%8C%EC%9D%B4%EC%8D%AC 풀이를 참고했다.