Algorithm
Coding Test(그리디 & 구현)
그리티 알고리즘(탐욕법) - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 최소한의 아이디어를 떠올릴 수 있는 능력을 요구 - 정당성 분석 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론 구현 - 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 시뮬레이션 및 완전 탐색 문제에서는 방향 벡터 자주 사용 #방향벡터 #동, 북, 서, 남 dx = [0,-1,0,1] dy = [1,0,-1,0]
백준 15649,15650 N과 M(Backtracking)
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net def DFS(): if len(s) == M: print(*s) return fo..
백준 1931 회의실 배정
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net n = int(input()) data = [] for i in range(n): start_time, end_time = map(int,input().split()) data.append([start_time,end_time]) data.sort(key=lambda x: (x[1], x[0])) last = 0 conut = 0 for i, j in data: if i >= last: conut += 1 last = j print(conut) 회의 시간이 겹치지 않으면서 가능한 회의를 가장 많이 할 수 있게 하..
백준 6064 카잉 달력
https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net import sys num = int(sys.stdin.readline()) for _ in range(num): m,n,x,y = map(int,sys.stdin.readline().split()) cnt = 0 i = 0 j = 0 while True: if i < m and j < n: i += 1 j += 1 cnt += 1 elif i == m: i = 1 j += 1 cnt += 1 eli..
Coding Test(Algorithm) - Python
문제 해결 과정 1. 지문 읽기 및 컴퓨터적 사고 2. 요구사항(복잡도) 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 시간 복잡도 O(n^2) => O(xlogx) => O(x) => O(logx) N의 범위 500 : O(N^3) N의 범위 2,000: O(N^2) N의 범위 100,000 : O(NlogN) N의 범위 10,000,000 : O(N) 수행 시간 측정 import time start_time = time.time() # 측정 시작 # 프로그램 소스코드 end_time = time.time() # 측정 종료 print("time:", end_time - start_time) # 수행 시간 출력 지수 표현 방식 #1,000,000,000 지수 표현 방식 a = 1..
Coding Test(Grammar) - Python
Input # map()을 이용하여 list에 저장 data = list(map(int,input().split())) [1, 1] #map()을 이용하여 두 변수에 저장 a,b = map(int,input().split()) 1 1 #sys.stdin.readline()을 사용하면 줄 바꿈 기호가 입력 되기때문에 rstrip() 같이 사용 data = list(map(str,sys.stdin.readline())) #['w', 'a', '\n'] num = list(map(str,input())) #['w', 'a'] # 123 => [1,2,3], 각 자리수 따로따로 저장됨 data = list(map(int,str(i))) data = list(map(int,input())) Dictionary #..