본문 바로가기
728x90
반응형

Study134

[프로그래머스][DP] 등굣길 python (201002) 1. 문제 설명 ** 유의해야할 제약 조건 집이 있는 곳의 좌표는 (1, 1) --> 1 인덱스 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. --> puddle의 경우 y,x 로 입력 되는 것 문제 핵심 : 결국 학교까지 가게되는 최단 경로의 경우의 수 (number of path) 를 구해야하는 것 ! 이 문제는 지난번에 푼 정수삼각형 문제와 거의 유사하다. 모든 경로를 탐색하면서 최단 거리 (step of path) 를 찾는 BFS, DFS 가 아니라 (ex. 게임 맵 최단 거리) 각 칸마다, 거기까지 도달하는 최단 경로의 경우의 수를 저장해두는 DP문제 였던 것 (ex. 정수 삼각형) huidea.tistory.com/101 [프로그래머스][DP] 정수삼각형 python (200917) 0.. 2020. 10. 3.
[프로그래머스] 없어진 기록 찾기 SQL - 200930 programmers.co.kr/learn/courses/30/lessons/59042 1. 문제 링크 코딩테스트 연습 - 없어진 기록 찾기 ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디 programmers.co.kr 2. 풀이 SELECT A.ANIMAL_ID, A.NAME FROM ANIMAL_OUTS A LEFT JOIN ANIMAL_INS B ON A.ANIMAL_ID = B.ANIMAL_ID WHERE B.ANIMAL_ID IS NULL ORDER BY A.. 2020. 9. 30.
[백준][binary search] 나무자르기 python (200930) 1. 문제 설명 2. 풀이 N, M = map(int, input().split(' ')) arr = list(map(int, input().split(' '))) arr = sorted(arr) high = arr[-1] low = 0 def summation(arr, cut): res = 0 for tree in arr: if cut > tree: continue res += tree-cut return res while True: mid = (low+high)//2 res = summation(arr, mid) if res == M: print(mid) exit() if high-1 M: low = mid else: high = mid print(mid) 2020. 9. 30.
[백준][binary search] 랜선 자르기 python (200928) 1. 문제 설명 www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 2. 풀이 우선 N개로 분할되는 최대 랜선 길이를 탐색해야한다 --> binary search @ 이때 최대로 되는 값을 찾기 때문에 일반적으로 알고 있는 이진 탐색 코드와는 조금 다르다. ## 1654- 랜선 길이 자르기 num_list_len, key = map(int,input().split()) global num_list num_list = [] for i .. 2020. 9. 28.
[백준][DP] 1946번 신입 사원 python (200926) 1. 문제 설명 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 2. 풀ㅇㅣ 1) 나의 기나긴 풀이 우선 문제 이해를 하는게 조금 어려웠는데 (예제 설명도 안되어있음 ㅜㅠ) 합격자들의 조건은 상대방보다 두점수가 낮지 않음 이다. 핵심은 A 지원자 두 영역 점수 모두가 B 지원자 두 영역 점수보다 클 경우에는 A, B 둘 중 하나만 합격리스트에 들어간다고 이해하면됨 그리고 여기서는 합격 인원을 최대로 할수 있는 경우에 대해 물었으니 A.. 2020. 9. 26.
[백준][DP] 11726번 2*N 타일링 python (200924) 1. 문제설명 2. 풀이 이것도 단순한 DP 문제이다. ! 1 -> 1개 2 -> 2개 3 -> 3개 4 -> 5개 5 -> 8개 6 -> 13개.... 점화식으로 표현하면 dp[n] = dp[n-1] + dp[n-2] 다. 그 이유를 살펴보면 가령 n 이 5라고 했을 때, 2*5로 채울수 있는 경우는 n = 3 일때 모든 경우에서 가로2칸 블럭을 모두 채우는 것 + n = 4 일때 모든 경우에서 가로 1칸 블럭을 모두 채우는 것이기 때문에 !! def solution(n): dp = [0,1,2,3,5] if n >= 5 : for idx in range(5,n+1): dp.append(dp[idx - 1] + dp[idx - 2]) else: return dp[n]%10007 return dp.pop.. 2020. 9. 25.
[백준][DP] 1003번 피보나치함수 python (200924) 1. 문제설명 2. 풀이 전형적인 DP 문제이다. 원래의 피보나치의 점화식은 DP[idx] = DP[idx-1] + DP[idx-2] 인데, 여기서는 약간 변형해서 0과 1의 출력 횟수를 구하는 문제다 이것도 크게 다르지 않은게 idx 에서의 0과 1의 출력 횟수는 idx-1 에서의 0과 1의 출력 횟수 + idx-2 에서의 0과 1의 출력 횟수 여서 DP 리스트에 숫자 대신 0과 1의 출력 횟수를 담아주고 dp 리스트를 쌓아나가면 되는 간단한 문제다. 하지만 아주 크리티컬한 실수로 시간을 날렸다 ... DP 초기화 타이밍 이다. 1) 나의 실수 import sys import operator N = int(sys.stdin.readline()) dp = [(1, 0), (0, 1)] for _ in r.. 2020. 9. 24.
[백준][DP] 9095번 1,2,3 더하기 python (200923) 1. 문제설명 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 2. 풀이 1은 --> 1개 1 2는 --> 2개 1, 1 2 3은 --> 4개 1, 1, 1 2, 1 1, 2 3 4는 --> 7개 1,3 1,1,2 2, 2 1,1,1,1 2,1,1 1,2,1, 3,1 5는 --> 13개 1,1,1,1,1 1,1,2,1 1,2,1,1 2,1,1,1 1,1,1,2 2,2,1 1,2,2 2,1,2 3,1,1 1,3,1 1,1,3 2 3 3 2 import sys N = int(sys.stdin.readline()) dp = [0,1,2,4] input_num_l.. 2020. 9. 23.
[백준][DP] 11053번 가장 긴 증가하는 부분 수열 python (200922) www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 문제 설명 2. 풀이 n = int(input()) a = list(map(int, input().split())) dp = [0 for i in range(n)] for i in range(n): for j in range(i): if a[i] > a[j] and dp[i] < dp[j]: dp[i] = dp[j] dp[i] .. 2020. 9. 22.
[백준][DP] 1463번 1로 만들기 python (200921) 1. 문제설명 2. 풀이 어제 설탕 문제처럼 단순히 조건문으로 풀수 있다고 생각했는데 아니었다 해당문제는 전형적인 DP 문제였음 우선 조건문으로 풀었을 때, def solution(input_num): chk = 0 num_dict = {} while input_num > 1: # print(input_num) if input_num % 2 !=0: # 홀수 경우 if input_num % 3 == 0: input_num /= 3 else: input_num -= 1 else: # 짝수 경우 if (input_num -1) % 3 == 0: input_num-=1 else: input_num /= 2 chk +=1 return chk 홀짝의 경우로 나누어서 풀었는데, 내 기준에서는 반례를 찾지 못했지만 .. 2020. 9. 21.
728x90
반응형

티스토리툴바