본문 바로가기

Problem Solving/boj68

[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] 1261. 알고스팟(Python) / BFS www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 이 문제는 어제 풀었던 미로만들기 문제 2021.03.25 - [Problem Solving/boj] - [BOJ] 2665. 미로만들기(Python) / BFS와 완전 같은 문제이다. 어제 풀었던 덕인지 30분 정도 소요했다. 사용 알고리즘 : BFS check 배열을 주어진 맵의 크기와 같게 만들고, 최댓값으로 초기화했다. 빈 공간일 때와 벽을 만났을 때 모두 이동 위치에 있는 값을 최.. 2021. 3. 26.
[BOJ] 1405. 미친 로봇(Python) / DFS www.acmicpc.net/problem/1405 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 생각보다 시간이 좀 걸렸다.. 문제 이해하는데 난독증이 심해 한참 걸렸다ㅠㅠ 문제만 잘 이해하고 나니 어렵지 않게 바로 술술 풀렸던 문제다. 사용 알고리즘 : DFS 인풋 받으면서 사용하기 편하도록 동서남북 방향별 percentage는 100으로 각각 나누어 리스트로 저장했다. 미리 한 방향으로만 갔을 때 상하좌우에 대해 최대 N만큼 갈 수 있으므로 현 위치를 중간으로 봤을 때 현 위치 포함해 N*2 + 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.

티스토리툴바