반응형 Coding Test/Baekjoon8 [ 백준 ] 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. 백준 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. [ 백준 ] 2630 색종이 만들기 파이썬python 풀이 // 문제 요약 위와 같이 절반씩 나누어서 만들 수 있는 가장 큰 정사각형 종이를 원할때 얻을 수 있는 종이 중에서 파란색과 흰색의 수는 각각 몇장씩인지 출력하여라 // 사고 분할 정복을 사실상 한번도 구현해보지 않은 상태에서 만난 문제 처음에는 종이를 나눈 횟수에 따라 정사각형의 시작점과 끝점을 구하고 그 안에서 탐색을 다시 하는 함수를 탑다운으로 짜고 있었는데 짜면서 바로 아 이방법으로는 안되겠다 하는 부분이 너무 많아서 그냥 풀이를 바로 찾아봤다. 이 풀이는 분할정복 중에서도 4개로 나뉘는 방식이라 하여 쿼드트리 방식이라고 한다. 코드를 보자. // 풀이 https://url.kr/1zmqlt hyun06000/coding_test_study_with_python It is a coding test.. 2021. 6. 23. 이전 1 2 다음 반응형
