차수열 백준 마라톤 문제들을 풀다가 차수열이라는 태그가 붙은 문제들이 몇개 나와서 공부를 해보았다. 처음보는 단어라서 뭔가 했는데 어떤 그래프의 모든 정점 차수를 모아 만들어서 차수열(degree sequence)이라고 한다. 재밌어 보여서 태그가 붙어있는 모든 문제를 풀어보았고, 여러 그래프나 트리에서의 성질을 공부할 수 있었다. 공부한 이론, ...

트리와 그래프 컴퓨터 과학에서 여러 방면으로 널리 쓰이는 자료구조에는 트리와 그래프가 있다. 우선 트리와 그래프가 무엇인지부터 알아보면 트리는 그래프의 한 종류이다 그렇기에 그래프에 대한 설명을 먼저 하면 그래프 우선 그래프는 정점(node)들 사이의 관계를 간선(edge)으로 표현하는 구조이다. 컴퓨터 네트워크, 도로 및 지도에서의 최단 ...

Knapsack Knapsack 문제(=배낭 문제)는 담을 수 있는 최대 무게가 있는 배낭과 각각의 무게와 가치가 주어진 물건들의 집합에 대해서 배낭에 담은 물건의 가치가 최대가 되도록 하는 집합을 찾는 문제이다. 백준 단계별로 풀어보기 DP에 있는 문제로 G5라는 난이도를 가지고 있는데 너무 저평가된 문제인 것 같다. 우선 물건이 분할이 가능한...

Banana Bunches Banana Bunches 문제 (gpt 번역) 바버라는 앨런의 바나나 농장에 갔습니다. 농장에는 일렬로 나무가 N그루 있고, 이를 배열 B로 나타냅니다. i번째 나무에는 Bi개의 바나나 송이가 있습니다. 모든 나무의 가격은 동일하며, 한 나무를 사면 그 나무의 바나나를 전부 얻습니다. 앨런은 줄에 빈틈이 너무 많이 생...

dynamic programming dynamic programming은 하나의 문제를 패턴을 찾아 부분 문제로 나눠서 특정 범위에 대한 계산을 하고 그것을 이용해서 원하는 범위의 답을 계산하는 풀이 방법이라고 생각한다. 알고리즘 강의에서 교수님도 말했지만 dynamic이라는 영어 뜻과는 거리가 있다. 메모이제이션을 이용한 풀이? 재귀를 더 효율적...

Excellent Views Excellent Views 문제 Shiny City는 단 한 개의 거리, 모든 건물의 높이가 서로 다르다. 그리고 건물 옥상에서 보이는 압도적인 경관으로 유명한 아름다운 도시다. 팬데믹 이후 관광객이 크게 줄었다. 당신은 멋진 블로그 글을 써서 더 많은 관광객을 끌어오고, 사랑스럽지만 비효율적인 도시의 재정 위기를 ...

웜홀 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내...

라면 사기 시리즈 라면 사기(Small) 라면 사기(Large) 다이아 문제 중 푼 사람이 젤 많은 문제들이다. 이번에 랜덤 마라톤 풀다가 본 그리디랑 비슷한 느낌으로 접근했고 질문 게시판들에 있는 반례들과 질문 글들을 읽어보며 풀 수 있었다. 출제자의 증명 글은 밑에 있는데 간단하면서도 떠올리기 많이 힘든(나는 불가능..?) 아이디어이다. 그럼...

구슬 탈출 시리즈 구슬 탈출 시리즈 2048문제와 같이 백준 빡구현 문제 중 하나로 계속 들어왔던 문제라 한번 쭉 풀어봤다. 골드 1치고는 아이디어도 간단하고 구현을 하는 것에도 그렇게 어렵지 않았던 것 같다. 1번의 변형으로 2, 3, 4를 쉽게 풀 수 있으므로 1번만 신경써주면 됐다. 우선 구현하기 편했던 것으로 테두리가 벽으로 둘려 쌓여있...

백준 마라톤 (코스71) (8/8) 오랜만에 전부 풀었다. Polynomial Showdown (4682, S4) A번 문제 풀이 9개의 정수를 입력받아서 각각의 정수가 차수인 8차 방정식을 출력하는 문제다. -1, 1, 0이 나올 때 조건문으로 처리하는 과정이 아주 귀찮았다. int main() { ios_base ::sync_...