분류 전체보기

[99클럽 코테 스터디 14일차 TIL] 거스름돈 - 백준 14916

오늘도 Greedy이다.굉장히 쉽게 풀렸다. https://www.acmicpc.net/problem/14916춘향이는 편의점 카운터에서 일한다.손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다.2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오.예를 들어,거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다.[입력]첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.[출력]거스름돈 동전의 최소 ..

[GoF Design Patterns] Composite

Composite Pattern에 대해 알아봅시다.Composite 패턴은 복합체 패턴이라고도 불리는 만큼, Composite는 합성물이라는 의미를 가지고 있습니다.실제 패턴에서도 그러한지 살펴봅시다.1. 목적객체를 트리 구조로 구성한 다음 개별 객체와 객체 그룹을 동일하게 다룰 수 있도록 하는 패턴입니다.2. 문제 상황객체를 트리 구조로 구성해야 한다는 점에서 어플리케이션의 핵심 모델을 트리구조로 표현할 수 있는 경우에만 패턴을 사용하는 의미가 있습니다.Products와 Boxes 두 가지 객체가 있습니다.Box에는 여러 개의 Products와 Boxes이 포함될 수 있습니다.물론 다시 하위 Boxes에도 여러 개의 Products와 Boxes가 다시 포함될 수 있습니다.그림을 거꾸로 보면 나무와 같은..

[99클럽 코테 스터디 13일차 TIL] 고양이는 많을수록 좋다 - 백준 27961

13일만에 세번째 키워드가 등장했다. Greedy! https://www.acmicpc.net/problem/27961마법소녀인 마도카는 너무나도 고양이를 좋아하는 나머지 마법을 이용하여 고양이 N마리를 집에서 키우기로 결심했다!마도카는 한 번의 행동에서 다음 2가지 마법 중 하나를 선택하여 사용한다. 처음에는 마도카의 집에 고양이가 존재하지 않는다.- 생성 마법: 고양이 1마리를 마도카의 집에 생성한다.- 복제 마법: 마도카의 집에 있는 고양이 일부 또는 전부를 대상으로 하여 복제한다. 즉, 만약 현재 마도카의 집에 고양이가 k마리 존재한다면, 0마리 이상 k마리 이하의 고양이를 마도카의 집에 추가할 수 있다.마도카는 위의 2가지 마법을 적절히 사용하여, 최소의 행동 횟수로 마도카의 집에 정확히 N..

[99클럽 코테 스터디 12일차 TIL] 토마토 - 백준 7569

BFS인데 오랜만에 풀면서 재밌다고 생각했다. https://www.acmicpc.net/problem/7569철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토에 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고..

[99클럽 코테 스터디 11일차 TIL] Yes or yes - 백준 25195

오늘은 DFS/BFS 주제로 DFS와 BFS 모두 활용하여 풀 수 있는 문제였다. https://www.acmicpc.net/problem/25195N개의 정점과 M개의 간선으로 이루어진, 사이클이 없는 방향그래프(DAG)가 주어진다.투어리스트 곰곰이는 종종 이 그래프 위에서 여행을 떠난다.투어리스트 곰곰이의 여행은 1번 정점에서 출발해 간선을 따라서 이동한다.그러다가 더 이상 간선을 따라서 이동할 수 없는 경우 투어리스트의 여행은 종료된다.투어리스트 곰곰이의 열성 팬인 팬클럽 곰곰이는 투어리스트를 만나기 위해 그래프 위의 정점 일부에서 잠복하곤 한다.팬클럽 곰곰이가 잠복한 정점 위에 투어리스트 곰곰이가 서 있게 되면 투어리스트 곰곰이와 팬클럽 곰곰이가 만나게 된다.오늘도 투어리스트 곰곰이는 음악을 들으..