본문 바로가기
728x90
반응형

분류 전체보기150

[백준] 스타트와링크 python (201004) 1. 문제 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 2. 풀이 import sys from itertools import permutations, combinations num = int(sys.stdin.readline()) skill_matrix = [] for idx in range(num): skill_matrix.append(list(map(int, sys.stdin.readline().split()))) players = list(range(num)) team_.. 2020. 10. 4.
[백준] 톱니바퀴 python (201004) 1. 문제 www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 2. 풀이 import sys import collections wheels = [] turns = [] def turnLeft(i, d): if i 3: return if wheels[i][.. 2020. 10. 4.
[프로그래머스][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.
728x90
반응형

티스토리툴바