BOJ67 [BOJ] 3079. 입국심사(Python) / Binary Search 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 입국 심사대의 개수 N과, 심사를 받을 인원 M이 주어지고, 각 입국 심사대의 심사에 걸리는 시간이 주어질 때 모든 인원이 심사를 받는 최소 시간을 구하는 문제 사용 알고리즘 : 이분 탐색 Binary Search 최소, 최대 시간을 left, right라 두고 그 중간값을 mid로 하여 전원 total 이 입국심사 가능한 시간이라면 mid-1를 right로 최대 시간을 줄여 다음 턴 때의 탐색 범위를 좁힌다. 불가능하다면 left를 mid + 1.. 2021. 3. 30. [BOJ] 1038. 감소하는 수(Python) / DFS 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 사용 알고리즘 : DFS 10보다 작은 수에 대해서는 input값 그대로 출력 depth를 최대 1.. 2021. 3. 26. [BOJ] 9019. DSLR(Python) / BFS www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 처음에는 DFS로 접근했다가 그렇게 해서는 답도 없을 것 같아서 BFS를 떠올렸는데, 결국 혼자 힘으로 못 풀고 다른 사람의 풀이를 봤다ㅠㅠ 사용 알고리즘 : BFS(최단거리 알고리즘) 여러 설명보다 아래 코드를 보면 이해할 수 있을 것이다. 4자리 숫자이므로 일차원 배열 visited를 10000 크기로 만든다. while문을 돌 때마다 현재 temp에 D, S, L, R 연산을 해주며 큐에 (연.. 2021. 3. 25. [BOJ] 2665. 미로만들기(Python) / BFS www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 고민을 꽤 했던 BFS 최단거리 미로 만들기 문제였다. 벽이 있을 때, 뚫을 수 있되 가장 적게 벽을 뚫고 목적지까지 도달하도록 하는 것이다. visited를 각 위치별로 최댓값 float('inf')으로 초기화한다. maze[nr][nc]가 vistied의 해당 위치를 최솟값으로 갱신할 수 있을 때만 갱신하고 큐에 값을 담는다. 이 때, 빈 공간이라면 벽을 뚫지 않고도 그냥 이동할 수 있으므로 해당 빈 공간의 위치를.. 2021. 3. 25. [BOJ] 17836. 공주님을 구해라!(Python) / BFS 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 재미있는 BFS 너비우선탐색 문제였다. # 45분 소요 처음에 풀 때 한 번에 답이 나왔지만, 세세한 케이스들을 미처 다 생각하지 못해서 여러 번 제출하며 조건문을 계속 추가했고, 결국 맞았다! 기본적인 BFS 틀에서 내가 고려한 조건은 다음과 같다. 격자에서 이동 중 그람(2)를 만났을 때, 현 위치에서 목적지까지는 거리를 절댓값의 합(minTime)으로 구해 미리 저장해둔다. 목적지까지 정상 도달한 경우도 도중에 그람을 구했든 아니든 반드시! .. 2021. 3. 25. [BOJ] 2846. 오르막길(Python) www.acmicpc.net/problem/2846 2846번: 오르막길 상근이는 자전거를 타고 등교한다. 자전거 길은 오르막길, 내리막길, 평지로 이루어져 있다. 상근이는 개강 첫 날 자전거를 타고 가면서 일정 거리마다 높이를 측정했다. 상근이는 가장 큰 오르 www.acmicpc.net 브론즈 문제로, 최장 길이를 구하기보다 가장 차이가 많이 나는 오르막길을 구하는 것이다. 이중 for문으로 오르막을 만날 때마다 가장 낮은 부분과 비교해 차이(maxDis)를 갱신해준다. 설명보다 아래 코드를 보는 것이 더 빠른 이해를 도울 것 같다. 파이썬 코드는 다음과 같다. from sys import stdin input = stdin.readline N = int(input()) A = list(map(int.. 2021. 3. 23. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음
