본문 바로가기

Coding Test33

[ 백준 ] 1867 돌멩이 제거 파이썬 풀이 // 문제 요약 n x n 격자의 운동장에 k 돌멩이가 있다. 격자 하나당 둘 이상의 돌멩이가 있을 수 없을 때 하나의 행이나 열을 따라 직선으로 달려가며 돌멩이를 주워 모두 줍는 최소 달리기 수를 구하여라 // 사고 처음에는 그때 그때 열과 행의 모든 돌멩이 수를 구하고 거기서 가장 많은 돌멩이가 있는 열 혹은 행을 따라 돌멩이를 지우며 제귀적으로 풀이하는 Greedy 방식을 사용했다. 아래의 방법은 결과적으로 실패했다. ### 백준 1867 돌멩이 제거 # https://www.acmicpc.net/problem/1867 n, k = map(int, input().strip().split(" ")) board = [[0 for _ in range(n)] for _ in range(n)] for _ i.. 2022. 4. 25.

[ 백준 ] 2749 피보나치 수 // 문제 요약 $N$이 ${10}^{18}$ 이하의 자연수일 때 $N$번째 피보나치 수를 ${10}^{6}$으로 나눈 나머지를 구하여라. // 사고 피보나치 수를 구하는 간단한 문제처럼 보이지만 DP로 풀었을 경우 $O(N)$ 의 복잡도를 가지므로 $N$이 $10^{18}$승 정도 되는 큰 수인 경우 DP로 돌리는 루프가 너무 오래 돌아가게되는 문제가 생긴다. 그러므로 $O(N)$을 따르되 $N$에 비례하지 않는 새로운 방법을 찾아야 한다. // 풀이 우선 이 문제의 풀이는 정해져 있다. 알면 풀고 모르면 못푸는 수학 문제다. 여기서는 피사노 주기를 이용하며 피사노 주기 중에서도 특수한 경우에 해당하는 ${10}^{k}$ 로 나누었을 때의 주기를 이용한다. 피보나치 수를 어떤 정수 $m$으로 나눈 나머.. 2022. 4. 19.

[ 프로그래머스 ] N으로 표현 // 문제 요약 정수 N과 number 이 주어졌을 때 N과 4칙 연산 기호를 여러 번 사용하여서 number를 만들 수 있는 경우 중 N이 가장 적게 사용된 횟수를 구하여라 (단 8번 이상인 경우 -1을 return 해라) // 사고 놀랍게도 태뷸레이션 문제다. 규칙을 발견하기 쉽지 않았는데 태뷸레이션으로 생각하지 않으면 다른 설명들도 이해하기 굉장히 난해하다. (가지치기 처럼 생각하고 메모이제이션으로 볼 수도 있다.) 문제의 예시로 나왔던 5를 이용하는 경우를 보도록 하자. N을 여러 번 사용하는 경우는 크게 두가지로 나눌 수 있는데 N을 그냥 여러 번 적어서 55나 555처럼 만드는 방법이고 연산기호를 넣어서 한번 더 적는 방법이다. 이때 N의 수를 1, 2, 3 이런 식으로 늘려가면서 경우의 수를.. 2022. 2. 25.

백준 1655 가운데를 말해요 //문제 요약 일련의 숫자들이 1회당 1개 주어지는 경우 매 회마다 주어졌던 숫자들의 중간값을 말하는 프로그램을 짜시오 //사고 가장 먼저 해볼 수 있는 생각은 리스트를 만들어서 2칸짜리 윈도우를 만들고 슬라이딩하면서 주어진 숫자가 두 수의 사이값인 경우 삽입하는 식으로 주어진 숫자들을 나열하고 그 배열을 중간값을 불러주면 될 것 같다. 하지만 그렇게 되면 최악의 경우 계속해서 배열의 가장 끝에 숫자를 더해야 하고 더하기 위해서 배열을 모두 훑어야 하므로 굉장히 비효율적인 방식이라고 할 수 있다. 사실 알아야하는 부분은 가운데 숫자가 무엇인가인데 계속해서 가운데에 두 숫자만 관찰할 경우 어떤 숫자들은 삽입되어도 가운데 수를 변화시키지 않으므로 그런 연산들은 생략하여 낭비하지 않을 수 있다. 예를 들면 [.. 2022. 1. 5.

백준 12865 번 배낭문제 //문제 K 만큼 담을 수 있는 배낭에 W의 무게와 V의 가치를 가진 물건들을 담을 때 최고로 가치있는 배낭을 만들면 배낭의 가치는 얼마인가 //사고 배낭문제는 크게 2가지로 나뉘는데 분할 가능 배낭 문제와 분할 불가능 배낭문제로 나뉜다. 분할 가능 배낭 문제는 말 그대로 물건을 쪼개서 넣을 수 있을 경우, 분할 불가능은 지금처럼 쪼갤 수 없는 물건들을 넣는 경우다. 보통 어떤 변수의 총량을 결정하는 단위를 찾을 수 있을 때 예를 들면 1kg으로 나눌 수 있거나 2kg 단위로 나눌 수 있을 때 그리디 방식을 사용하고 그럴 수 없을 때 다이나믹 프로그래밍, 그 중에서도 타뷸레이션 방법을 사용한다. 이 문제의 결우 타뷸레이션을 사용해서 쉽게 풀 수 있는 전형적인 문제다. //풀이 N, K = list(map.. 2022. 1. 5.

[ 백준 ] 10451 번 순열 사이클 파이썬python 풀이 // 문제 요약 1부터 N 까지 정수로 만들 수 있는 순열의 한 가지 경우가 주어질 경우 1부터 N 까지 오름차순으로 정렬한 순열과 1대 1 대응 하여 만들 수 있는 그래프에서 순환 구조는 몇개가 생기는지 리턴하는 함수를 만들어라. //사고 문제를 이해하는게 어려운 문제다. 문제의 참고자료를 보면 그림이 아주 잘 나와있는데 이런 행렬이 주어지면 첫번째 행이 from 두번째 행이 to 가 되는 그래프를 그릴 수 있다. 그려본다면 이런식이다. 모두 같은 숫자로 이루어진 순열이므로 뻗어나가고 끝나는 가지는 존재하지 않게 되고 순환구조가 발생하게 된다. 파이썬에서는 dfs를 이용하면 순환구조를 간단하게 찾을 수 있는 테크닉이 존재하는데 바로 파이썬의 set() 를 이용한 진행경로 추적이다. dfs의 경우 깊이를.. 2021. 7. 29.

이전 1 2 3 4 ··· 6 다음

티스토리툴바