백준11 백준 - 도도의 음식 준비 - 22953 - swift https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 문제는 완전탐색과 이분탐색으로 볼 수 있다. 완전탐색에는 순열과 조합을 이용했다. 크게 문제는 최적의 시간을 찾는 것으로, 각 요리사들에는 요리 시간이 정해져있고, K개의 음식을 모두 준비하는데 걸리는 가장 빠른 시간을 찾는 문제다. 이러한 유형은 미리 최적의 시간이 X라고 정하고서 탐색하는 방법, 즉 이.. 2021. 9. 1. 백준 - 빌런 호석 - 22251 - swift https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 문제 유형은 구현, 완전탐색 또는 비트마스킹이 될 수 있다. 하나의 문제에서 다양한 접근법이 가능하므로 정말 좋은 문제인 것 같다. 어떻게 이런 문제를 만드는지 정말 대단하다. 내 기준에서는 조금 난이도가 있었다 내 접근법 우선 처음 접근법( 구현 + 완전탐색 ) 은 다음과 같았다. 하나의 디스플레이에 0부터 9까지 숫자를 표현할 수 있고, 각 숫자마다 필요한 LED가 다르다. 또, 각 디스플레이마다 LED는 최대 7개이다. 호석이는 1부터 최대 P개까지 LED를 반전시킬 수 있다... 2021. 8. 27. 백준 - 정보 상인 호석 - 22252 - swift https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 유형은 우선순위 큐 이용 문제다. swift에서는 우선순위 큐가 없기 때문에, 이진 힙으로 이용하여 따로 구현해야 한다. 몇 번 작성하다 보면은 저절로 외워진다. 우선순위 큐가 필요한 이유는, 쿼리가 다 주어진 다음에 계산을 시작하는 것이 아닌, 각 쿼리마다 그때그때 계산을 해야 한다. 한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다. 어느 시점.. 2021. 8. 26. 백준 - 숨바꼭질 4 - 13913 - swift https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제는 너비 우선 탐색 - bfs 유형이다. X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 총 3가지의 움직임이 있는데, 3가지 모두 다 1초 후에 발생한다. 문제는 가장 빠르게 동생을 찾을 수 있는 시간을 묻고 있다. 모두 1초이므로, 간단하게 bfs를 통해서 풀 수 있다. .. 2021. 8. 26. 백준 - 늑대와 양 - 16956 - swift https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 실버 4의 낮은 난이도지만, 재밌는 문제였다. 문제 유형은 구현에 가깝다. 또는 bfs로도 풀 수 있긴 하다. 즉 bfs를 몰라도 풀 수 있는 문제다. 사실 나도 문제를 보자마자 bfs가 딱 떠올랐다. 대체로 bfs나 dfs가 들어가면 최소 실버1~2의 난이도를 갖는데, 의아했다. 왜 실버 4일까? 처음에는 늑대를 기준으로 bfs를 돌리면서 양을 만나는...이런 생각을 하다가, 양을 기준으로 .. 2021. 8. 25. 백준 - 두 로봇 - 15971 - swift https://www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net bfs 또는 dfs , 그래프탐색 유형이다. 굉장히 좋은 문제라고 생각한다. 그래프탐색의 골드5의 난이도는 그렇게 어렵지 않지만, 핵심을 파악하는게 꽤 걸렸다. ( 사실 그마저도 다른 분의 코드를 참고해서 깨달았다. ) 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방.. 2021. 8. 25. 백준 - 회의준비 - 2610 - swift https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 유형은 bfs탐색 또는 플로이드 워셜로 볼 수 있다. 문제를 푸는 데 있어서 핵심 로직은 다음과 같다. 1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다. 2. 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. 사실 1번을 만족한다면 2번은 자동적으로 만족할 수밖에 없다. 즉 2번은 그다지 고려하지 않아도 되는 부분이다. 그러므로, 위원회를 만들어주기 위한 그룹핑이 필요.. 2021. 8. 24. 백준 - 쇠막대기 - 10799 - swift https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제는 스택 유형이다. 나름 재밌는 문제 였다. 특정 문제들은 특정 알고리즘을 쓰면 풀 수 있는 그런 뻔한 문제들이 있는데, 그런 문제 말고 이렇게 직접 문제 해결 과정을 오롯이 찾아가는 문제가 재밌다. 처음 봤을때는 이걸 어떻게 접근해야하는지, 감이 안왔다. 레이저기준으로 양옆을 확인해야하는지... 등등 시도 해봤지만 다 영 아니였다. 그러다가, 스택으로, 앞에서부터 순차적으로 확인하는걸로 생각해봤다. 만.. 2021. 8. 24. 이전 1 2 다음
