본문 바로가기
728x90

백준 풀이103

[백준/BOJ] - 10844번 python 풀이 - dp https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 규칙 찾는 것이 중요한 dp 문제이다. dp 문제를 해결하기 위해선 점화식 즉, 규칙을 먼저 찾는 것이 중요하다. 그렇기에 표를 만들고 n이 1,2 일 경우를 직접 채워 넣어 어떤 규칙이 있는지 찾아보자. 아래 코드에는 행을 n으로 하고 열을 0~9로 했으나 예시 그림은 반전 형태이다. 해당 그림에선 행(가로)이 맨 끝에 무엇이 올지, 열(n값)이다. 앞선 열의 행값 맨끝값 0 or 2에 위치한 값을 더하면 다음 열의 맨 끝에 1을 넣을 수 있는 경우의 수를 구할 수 있다. 하지만 다음 열의 맨끝 값에 0을 넣.. 2023. 8. 16.
[백준/BOJ] - 14889번 python 풀이 - backtracking https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 백트래킹 조합문제를 풀 땐 1. 가지치기의 기준을 어떻게 할 것인가. 2. 조합은 순열과는 다르게 순서가 의미가 없으므로 재귀함수를 반복할 때 변수 뽑는 것을 어떻게 처리해 줄 것인가 이 정도가 중요하다. 아래 코드에선 depth 즉, 몇개를 뽑았는지의 지표 변수가 주어진 n의 절반 만큼 뽑았을 경우를 기준으로 가지치기를 해줬다. 뽑은 변수는 매번 방문처리를 해주었기에 2중 for문을 돌리며 각 for문의 변수인 i,.. 2023. 7. 2.
[백준/BOJ] - 1182번 python 풀이 - backtracking 백트래킹이란 쉽게 말해 가지 치기를 하는 알고리즘. 해당 문제는 depth를 기준으로 depth가 주어진 정수의 개수를 넘어 갔을 경우 더이상 탐색이 불가하므로 장치를 걸어놓아 함수를 리턴시켜 문제를 해결하는 백트래킹 문제이다. 트리를 생각해보면 맨처음 depth 0부터 주어진 정수의 개수-1 만큼의 depth가 허용 범위이다. 즉, 주어진 정수의 개수 = depth가 될 경우 문제가 생긴다는 것. 이를 중점으로 해결해보자. import sys input = sys.stdin.readline m,n = map(int,input().split()) #정수 개수, 원하는 합 arr = list(map(int,input().split())) ans = 0 def recur(depth,T_sum): global.. 2023. 6. 30.
[백준/BOJ] - 5568번 python 풀이 - backtracking 처음 풀어보는 backtracking 문제. 방문처리를 하며 재귀적 호출을 하는 알고리즘이므로 기본적으로 방문 처리용 list인 ok를 선언하고 최종 정수의 조합을 저장하기 위한 set 자료형 rs를 선언했다. set을 선택한 이유는 중복 저장이 안되는 점을 활용 맨처음 재귀함수를 호출할 때 매개변수를 0으로 보내어 임시 list인 temp의 길이가 0임을 표현한다. 추후에 반복문을 통해 카드에 적힌 숫자를 temp에 넣는 과정을 할 때 마다 해당 매개변수의 값을 증가 시킨다. 매개변수 값이 뽑으려는 카드의 수만큼 도달했다면, 최종 결과 값을 저장시킬 rs에 add 해주고 return을 한다. 재귀함수에서 return을 하게 되면 이전 재귀 함수로 돌아가게 된다. 그렇기에 마지막으로 추가해줬던 값을 제거.. 2023. 6. 30.
[백준/BOJ] - 1927번 python 풀이 - minheap 1. heapq를 활용하여 간단하게 구현할 수 있다. 2. heapq.heappush를 사용하면 heap에 push가 된다. 3. heqpq.heappop을 사용하면 가장 작은 값이 pop된다. 번외로 maxheap을 활용하려면 import heapq heap = [] a = 3 b = 4 heapq.heappush(heap, -a) heapq.heappush(heap, -b) print(-heapq.heappop(heap)) 마이너스를 붙이는 개념으로 활용 import heapq import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): num = int(input()) if num != 0: heapq.heap.. 2023. 5. 11.
[백준/BOJ] - 1065번 python 풀이 - 숫자의 각 자릿수를 list에 int형으로 변환 하는법 1~99까지 수는 모두 한수에 해당함. 100부터 등차수열에 해당하는 수인지 확인해야 하는데 이는 해당 수를 str 형으로 변경한 후, list(map())을 통해 각각의 자릿수를 list의 각 element에 할당하는 방식으로 구현가능하다. #1~99까진 무조건 #100이상일땐 100으로 나눈 몫 a, 나머지를 10으로 나눈 몫 b 나머지 c n= int(input()) #110 cnt = 0 for i in range(1,n+1): if i < 100: cnt += 1 else: nums = list(map(int,str(i))) if nums[0] - nums[1] == nums[1] - nums[2]: cnt+=1 print(cnt) 2023. 5. 10.
728x90

티스토리툴바