본문 바로가기

코딩테스트

 (46)
[Python] 다양한 문제 풀어보기 동아리 마지막 과제여러 문제 풀어보기!  https://www.acmicpc.net/workbook/view/8708여기에 있는 다양한 유형의 문제들을 풀어본다.https://www.acmicpc.net/problem/23971import sysinput = sys.stdin.readline# 예제 : 10 10 2 2 -> 16# 예제 : 50000 50000 11 9 -> 20835000H, W, N, M = map(int, input().split()) a = H//(N+1)if H%(N+1)!=0: a+=1b = W//(M+1)if W%(M+1)!=0: b+=1print(a*b)단순 사칙연산 문제.나는 if문을 이용했지만, 그냥 나누기 연산 후 반올림을 해주는게 편할 듯 https://..
[Python] 기하 # 12-1. 기하 알아보기기하 핵심 이론CCW(Counter-ClockWise)는 평면상의 3개의 점과 관련된 점들의 위치 관계를 판단하는 알고리즘이다.세 점을 A(X1, Y1), B(X2, Y2), C(X3, Y3)라 할 때, CCW = (X1Y2 + Y2X3 + X3Y1) - (X2Y1 + X3Y2 + X1Y2)CCW의 결과가 0인 경우 반시계 방향으로 세 점이 위치한다. https://www.acmicpc.net/problem/11758import sysinput = sys.stdin.readlinex1 ,y1 = map(int, input().split())x2 ,y2 = map(int, input().split())x3 ,y3 = map(int, input().split())# CCW 공식re..
[Python] 동적 프로그래밍 문제 풀이 정리(1) https://www.acmicpc.net/problem/9095# 내 풀이import sysinput = sys.stdin.readlineT=int(input())D = [0]*11D[1] = 1D[2] = 2D[3] = 4for i in range(4, 11): D[i] = D[i-1]+D[i-2]+D[i-3]# print(D)# [0, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274]for _ in range(T): n = int(input()) print(D[n])D[n] = 1,2,3으로 n을 만들 수 있는 경우의 수라고 가정하고, 4까지 직접 구해보니 직관적으로 점화식이 나왔다.D[i] =D[i-1]+D[i-2]+D[i-3]늘 직관적으로 찾을 수..
[Python] 동적 계획법 # 11-1. 동적 계획법 알아보기동적 계획법(dynamic programming)이란?복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제를 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법DP의 핵심 이론원리큰 문제들을 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.메모제이션(memozation) 기법 : 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.DP는 top-down 혹은 bottom-up 방식으로 구현할 수 있다.예시(피보나치 수열) : D[N] = D[N-1] + D[N-2]https://www.acmicpc.net/problem/2747top-do..
[Python] 조합 문제 풀이 정리(2) https://www.acmicpc.net/problem/6603python 라이브러리 combinations을 사용하면 쉽게 풀 수 있지만...직접 구현해서 풀자# 정답 풀이import sysinput = sys.stdin.readlinedef dfs(depth, idx): if depth == 6: print(*out) return for i in range(idx, k): out.append(S[i]) dfs(depth + 1, i + 1) out.pop()while True: array = list(map(int, input().split())) k = array[0] S = array[1:] out =..
[Python] 조합 문제 풀이 정리(1) 조합 어렵다..확통 다 까먹음.조합은 기초를 다질겸 브론즈부터 천천히 올라가겠다. https://www.acmicpc.net/problem/16968s = input()if s[0] == 'c': answer = 26else: answer = 10for i in range(1, len(s)): # 연속 판단을 위해 1부터 시작 if s[i] == 'c': if s[i - 1] == 'c': answer *= 25 else: answer *= 26 else: if s[i - 1] == 'd': answer *= 9 else: answer *= 10print(..
[Python] 조합 # 10-1. 조합 알아보기조합(Combination)이란?nCr로 표현하며, n개의 숫자 중에서 r개를 뽑는 경우의 수순열은 nPr로 표현되며, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기 한다. 조합의 핵심 이론순열 공식 nPr = n!/(n-r)!조합 공식 nCr = n!/(n-r)!r!알고리즘에서 조합을 구현할 때는 위 공식을 코드화하지 않고 점화식을 사용해 표현한다.예를 들어, 5개의 데이터 중 3개를 선택하는 경우는 5개의 데이터 중 4개의 데이터의 선택 여부가 결정된 상태로 가정한다.따라서 5번째 데이터의 선택 여부에 따라 이전 4개의 데이터 중 2개 혹은 3개를 선택하는 경우의 수로 나뉜다.위를 점화식으로 표현하면 D[5][3] = D[4][2]+D[4][3]이 된..
[Python] 트리 문제 풀이 정리 https://www.acmicpc.net/problem/9934완전 이진 트리 + 중위순회 문제중위순회의 결과를 보고 트리를 만들 수 있어야 한다. 손으로는 풀 수 있는데...코드로는 구현을 못하겠다..# 정답 풀이import sysinput = sys.stdin.readlineK = int(input())tree = [[] for _ in range(K)]p = list(map(int, input().split()))def inOrder(p, depth): # 트리의 root index 찾기 mid = (len(p)//2) # 해당 깊이에 해당하는 node 추가 tree[depth].append(p[mid]) if len(p)==1: return inOrd..

티스토리툴바