...
본문 바로가기

코딩테스트

(38)
프로그래머스 - 위클리 챌린지 7주차 - 입실 퇴실 - swift https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 문제 유형은 구현문제 일수도 있고, 나는 스택으로 풀어냈다. 구현문제로 접근하려고 논리를 세워봤지만 코드로 작성할 수 있는 깔끔한 논리가 떠오르지 않았다. 예를들어, 확실하게 만난 사람은, 다음과 같을 수 있겠다 1. 자신이 들어온다음에 들어온 사람들 중에서, 자신이 나가기전에 있는 사람들에 속한다면 반드시 만났겠다. 2. 자신이 들어오기 전에 사람들 중에서, 자..
백준 - 하노이 탑 이동 순서 - 11729 - swift https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제는 재귀 유형이다. 우선 풀이에 앞서 정말 감격스럽다. 코딩테스트 공부한지 1년만에 도움없이 혼자서 이해하고 풀었다. 그전까지 매번 하노이탑 볼 때 마다 이걸 어떻게 푸는건지 감도 오지 않았다. 심지어 예전에 풀이를 봤을때도 이해가 안갔었다. 하지만,... 1시간동안 고민 끝에 풀었다!ㅠㅠ 처음에는 완전탐색으로 접근했다가, 계속 이동하는 걸 그려보면서 다음과 같은 패턴을 찾을 수 ..
백준 - 도도의 음식 준비 - 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라고 정하고서 탐색하는 방법, 즉 이..
백준 - 빌런 호석 - 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를 반전시킬 수 있다...
백준 - 정보 상인 호석 - 22252 - swift https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 유형은 우선순위 큐 이용 문제다. swift에서는 우선순위 큐가 없기 때문에, 이진 힙으로 이용하여 따로 구현해야 한다. 몇 번 작성하다 보면은 저절로 외워진다. 우선순위 큐가 필요한 이유는, 쿼리가 다 주어진 다음에 계산을 시작하는 것이 아닌, 각 쿼리마다 그때그때 계산을 해야 한다. 한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다. 어느 시점..
백준 - 숨바꼭질 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를 통해서 풀 수 있다. ..
백준 - 늑대와 양 - 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를 돌리면서 양을 만나는...이런 생각을 하다가, 양을 기준으로 ..
백준 - 두 로봇 - 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번 방..