Programming

구현 코딩테스트에서 자주 출제되는 유형 (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제 피지컬을 요구하는 문제 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우 구현하기 어려운 문제 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 ..

구현 코딩테스트에서 자주 출제되는 유형 (1) 정확한 풀이 방법, (2) 프로그래밍 언어 문법의 이해를 바탕으로 완벽한 구현 구현 : '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제' 알고리즘 설계 후, 먼저 풀 문제가 없을 때 푸는 문제 피지컬을 요구하는 문제 언어의 문법(라이브러리)을 잘 이해하고 경험이 있어야만 바로 떠올릴 수 있는 해결 방법 코테에서 1~2번 문제는 대부분 그리디 or 구현 → 합격을 좌우 구현하기 어려운 문제 코드가 지나칠 만큼 길어지는 문제 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는(파싱) 문제 등 유형 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 ..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형 문제 풀이1 : 단순 ver. # 변수 : N 어떤 수, K 나누는 수 # N, K를 공백으로 구분하여 입력받기 n, k = map(int, input().split()) result = 0 # N이 K 이상이라면 K로 계속 나누기 while n >= k: # N이 K로 나누어 떨어지지 않는다면 N에서 1씩 빼기 while n % k != 0: n -= 1 result += 1 # K로 나누기 n //= k result += 1 # 마지막으로 남은 수에 대하여 1씩 빼기 while n > 1: n -= 1 result += 1 pr..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형 문제 풀이1 : min() 함수 이용 # 변수 : N 행의 수, M 열의 수 # N, M을 공백으로 구분하여 입력받기 n, m = map(int, input().split()) result = 0 # 한 줄씩 입력받아 확인 for i in range(n): data = list(map(int, input().split())) # 현재 줄에서 '가장 작은 수' 찾기 min_value = min(data) # '가장 작은 수'들 중에서 가장 큰 수 찾기 result = max(result, min_value) print(result) ..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형 문제 풀이1 : 기본적인 풀이 # 변수 : N 숫자 개수, M 더하는 횟수, K 연속 횟수, result 합 # N, M, K를 공백으로 구분하여 입력받기 n, m, k = map(int, input().split()) result = 0 # N개의 수를 공백으로 구분하여 입력받기 data = list(map(int, input().split())) data.sort() # 입력받은 수들 정렬 first = data[n-1] # 가장 큰 수 second = data[n-2] # 두 번째로 큰 수 while True: # 무한 루프 ..

그리디 알고리즘 현재 상황에서 지금 당장 좋은 것만 고르는 방법 암기하지 않아도 풀 수 있는 가능성이 높은 문제 유형 유형이 매우 다양하여 암기해도 풀기 쉽지 않은 문제 유형 문제 풀이 # 변수 설정 : 현재 잔액, 동전 개수 n = 1260 count = 0 # 큰 단위의 화폐부터 차례대로 확인 coin_types = [500, 100, 50, 10] for coin in coin_types: count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기 n %= coin print(count) 해석 시간 복잡도 : O(K) 단위가 큰 돈부터 순서대로 거슬러준다. 이때 몫을 남기는 // 연산자를 이용하여 개수를 세고, 나머지를 남기는 % 연산자를 이용하여 잔액을 업데이트 한다...