알고리즘

처음에는 완전 나이브 하게 코드를 짰었다. for i in range(n): for j in range(n): if i==j: continue if len(phone_book[i]) > len(phone_book[j]):continue if phone_book[i] == phone_book[j][0:len(phone_book[i])]: print(phone_book[i]) return False 하지만 시간복잡도가 O(N^2)이다 보니 효율성 테스트에서 떨어지는 문제가 발생했다. def solution(phone_book): n = len(phone_book) phone_book.sort() for i in range(1,n): if phone_book[i-1] in phone_book[i] return..

https://www.codetree.ai/missions/5/problems/maximum-product-of-three-numbers?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai import sys n = int(input()) nums = list(map(int,input().split())) p,m = [],[] for n in nums: if n=0: p.append(n) p.sort() m.sort() ans = -sys.maxsize if len(p) >= 3: ans ..

https://www.codetree.ai/missions/5/problems/square-made-of-two-points?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai x1, y1, x2, y2 = tuple(map(int, input().split())) a1, b1, a2, b2 = tuple(map(int, input().split())) width = max(x2, a2) - min(x1, a1) height = max(y2, b2) - min(y1, b1) print(ma..

https://www.codetree.ai/missions/5/problems/l-r-and-b?utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai arr = [list(input()) for _ in range(10)] bx,by = 0,0 lx,ly = 0,0 rx,ry = 0,0 for i in range(10): for j in range(10): if arr[i][j] == 'B': bx,by =j,i elif arr[i][j] == 'L': lx,ly = j,i elif arr[..

그리디 알고리즘은 탐욕법으로 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. - 이것이 코딩테스트다 with 파이썬 중에서 - 그리디를 공부하나보니 그리디 자체는 그래프나 정렬문제처럼 정해진 풀이법이 있는 것은 아니다 그리디는 전체조건이나 부분조건에서 한 가지 자신이 구성한 로직이 그리디의 정당성에 부합하고 그것이 곧 최적의 답일때 유효한 것이다 내가 그리디 알고리즘을 어렵게 느끼는 이유는 그리디를 위한 로직의 유형이 다양하다는 데 있을 것이다. 거스름돈 문제같은 간단한 문제 뿐만 아니라 다익스트라 알고리즘도 그리디이기 때문이다. 그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다..

코드 ''' 세탁소 사장 동혁 https://www.acmicpc.net/problem/2720 ''' t = int(input()) m = [25,10,5,1] for _ in range(t): result = [] n = int(input()) for i in m: result.append(str(n//i)) n %= i print(' '.join(result)) 해설 이 문제는 그리디 문제이다. 그리디하게 가장 단순하게 생각해서 최대한 적게 주어야 한다면 가장 큰 단위를 최대한 많이 주는 것이다. 예를들어 돈의 단위가 10과 1이 있다고 해보자 거슬러 주어야 할 돈이 20이라 해보자. 최대한 적게 주어야 한다면 10을 최대한 많이 주어야 한다. 따라서 10을 2개주면 된다. 이에따라 결론을 내리자면..

https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 위 문제는 숫자 1,2,3으로 특정 숫자를 만들 수 있는 경우의 수를 구하는 문제이다. 예를들어 4라면 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 총 7개가 된다. 이 문제는 다이나믹 프로그래밍으로 분류가 된다. 1,2,3으로 만들어야 하는 숫자가 n이라 해보자. n = 1 일때는 1 n = 2 일때는 2 n = 3 일때는 4 n = 4 일때는 7 n = 4인 경우는 n이 1일 때와 2일 때와 3일때를 더한 경우와 같다. 따라서 아래와 같은 점화식을 유도할 수 있고 코드..

오늘은 다이나믹 프로그래밍 문제 중 가장 기초적인 문제 중 하나를 풀어봤습니다. 다이나믹 프로그래밍은 큰 문제를 작은 문제들로 해결할 수 있는 경우 사용할 수 있는 알고리즘 기법입니다. 접근 1003번에서는 f(0)과 f(1)이 호출되는 횟수를 구하라고 합니다. 제한시간을 보시면 0.25초 입니다. 문제에 나와 있는대로 재귀함수로 구성하면 100% 시간이 부족합니다. 왜냐하면 그림대로라면 O(2^n)의 시간복잡도를 가지고 있는데 (이는 함수 호출을 그래프로 그리면 답이 나옵니다.) n은 40이하입니다. 2^40은 대략 1000000000000 입니다. 10억의 연산을 1초로 수행한다고 하면 0.25초를 훨씬 초과합니다. 이때 적용할 수 있는 방법은 다이나믹 프로그래밍, 동적 계획법입니다. 그 중에서도 b..