알고리즘31 [BFS] 백준 14395 : 4연산 - 파이썬 Python https://www.acmicpc.net/problem/14395 14395번: 4연산 첫째 줄에 정수 s를 t로 바꾸는 방법을 출력한다. s와 t가 같은 경우에는 0을, 바꿀 수 없는 경우에는 -1을 출력한다. 가능한 방법이 여러 가지라면, 사전 순으로 앞서는 것을 출력한다. 연산의 아 www.acmicpc.net 생각하기 최소의 변환을 찾으면 되는 문제이기 때문에 BFS로 접근해야겠다고 생각 평소처럼 visited 배열(list)을 통해서 방문 여부를 검사려고하니, 메모리 문제가 발생 -> 각 연산의 특성을 잘 생각해보면 모든 10^9숫자를 다 사용하지는 않음 뺄셈을 만나면 S - S 로 0이 되므로 사실상 끝 나눗셈을 만나면 S / S 로 1이 되므로 사실상 2의 배수가 된다 S^a * 2^b 형.. 2022. 2. 7. [DP] 백준 1496번 : 기타리스트 - 파이썬 Python https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 생각하기 N개의 연주곡 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주 V[i] - i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨 (차이) -> P + V[i] 혹은 P - V[i] 로 연주 가능 이때, 0 2022. 2. 4. [이분탐색] 프로그래머스 입국심사 - 파이썬 Python https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 생각하기 처음에는 모든 경우를 살펴보자는 생각이었지만 n의 개수와 시간이 너무 커서 불가했다 이분 탐색으로 풀기 위해서 기준을 정해야 하지만 어떤 기준을 정해야할지 생각하는데에 오래 걸렸다 이분 탐색의 기준을 심사 시간이라고 가정 = 각 심사관이 사람을 처리할 수 있는 시간 right (max)는 가장 오랜 시간이 걸리는 심사관이 모든 사람(n)을 처리했을 때, .. 2022. 2. 1. [구현] 백준 16234 : 인구이동 - 파이썬 Python https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 생각하기 문제에서 제시된 기준을 기반으로 인구가 각 날에 이동할 수 있는 블락들을 bfs를 이용하여 묶어본다 묶을 수 있다면 계속 이동해도 된다는 얘기 -> 묶지 못할 때까지 계속 day를 증가시켜가면서 이동해보자 시간복잡도 모든 칸에 대해서 조사 : O(N^2) 최대 인구 이동 가능 : 2000 2000 x ( N^2 ) 구현하기 united - bfs를 돌면서 묶을 수 있는 박스.. 2022. 1. 31. 이전 1 2 3 4 5 6 ··· 8 다음
