알고리즘 (28) 썸네일형 리스트형 대기업 코딩테스트 준비 1: 고난이도 알고리즘 정리 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) 계속 추가 예정 최소 공통 조상 (LCA) 두 노드의 공통된 조상 중에 가장 가까운 조상 찾기 노드의 깊이가 n일 때 n*log(n)개의 공간을 이용해 시간복잡도를 O(MlogN) M은 쿼리 갯수, N은 노드 갯수 1. DFS로 모든 노드 깊이를 계산함 2. 두 노드의 깊이를 맞춤 1. 깊은 놈 부모로 가서 노드 깊이 맞춤 2. 한칸씩 올라가며 찾는다. import sys input = sys.stdin.readline # 시간 초과를 피하기 위한 빠른 입력 함수 sys.setrecursionlimit(int(1e5)) # 런타임 .. [핵심 알고리즘 정리] 퀵소트 보통 내부 라이브러리는 퀵소트와 삽입 정렬을 믹스해서 만든 TIM SORT 라는 녀석으로 구현되어 있는 것으로 안다. 퀵 소트를 직접 구현할 일은 거의 없지만 문제의 구현 아이디어가 비슷하게 출제되는 경우도 있으므로 여러번 봐두면 도움이 된다. 쉬운 버전의 구현과 어려운 버전의 구현을 동시에 공부해보자. # https://www.daleseo.com/sort-quick/ 참고 URL # 시간복잡도 O(NolgN) # 거의 모든 정렬 중 제일 좋음. 기본으로 사용 # 최악이 N이라 안되는 경우 병합 정렬을 사용 # 쉽게 구현하기 def quick_sort(arr): if len(arr) pivot: # 내림차순 시 이부분 바꿔줌 right.append(num) else: equal.append(num) r.. [LV1] 프로그래머스 [1차] 다트 게임 python https://programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 갓이유가 광고한 게임이다. 문제 해결은 다음과 같다. 1. 숫자의 경우 스택에 넣는다. 2. 그 다음 나오는 싱글 더블 트리플을 제곱한다. 3.* 스타상인 경우, 스택의 맨 위를 2배하거나, 길이가 2 이상일 경우 그 이전 점수도 2배로 한다. 4. 아차는 직전 점수만 -1배 하기 때문에 스타 후 아차는 중첩이 안된다. 5. 아차 후 스타는 중첩될 수 있는데, 그냥 우직하게 하나씩 적용하면 된다. def solution(dartResult): temp = 0 point = {"S": 1, "D": 2, "T": 3} temp = ''.. [LV1] 프로그래머스 서울에서 김서방 찾기 python https://programmers.co.kr/learn/courses/30/lessons/12919 코딩테스트 연습 - 서울에서 김서방 찾기 String형 배열 seoul의 element중 Kim의 위치 x를 찾아, 김서방은 x에 있다는 String을 반환하는 함수, solution을 완성하세요. seoul에 Kim은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니다. 제 programmers.co.kr 파이썬의 format을 써먹어 볼 수 있는 문제다. def solution(seoul:list): # print( "김서방은 {0}에 {1}있다".format(seoul.index("Kim"),0)) # 김서방은 1에 0있다 return "김서방은 {0}에 있다".format(seoul.in.. [LV1] 프로그래머스 문자열 다루기 기본 python https://programmers.co.kr/learn/courses/30/lessons/12918 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 a234이면 False를 리턴하고 1234라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 이�� programmers.co.kr 단순 반복문 구현 def solution(s:str): if s.isdigit(): if len(s) in[4,6]: return True return False 한번 더 풀면서 수정한 코드 def solution(s:str): return True if s.isdigit() and len(s) in (4,.. [LV1] 프로그래머스 문자열 내림차순으로 배치하기 python https://programmers.co.kr/learn/courses/30/lessons/12917 코딩테스트 연습 - 문자열 내림차순으로 배치하기 문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 � programmers.co.kr 해당 문제는 연습이 제대로 안되어있으면 당황할 문제이다. 일단 문자열은 immutable인데... 재미있는게 문자열을 sort하면 배열로 바꿔 정렬해 버린다. 따라서 문자열을 다시 한번 배열로 합쳐줘야 한다. def solution(s): return "".join(sorted(s,reverse=True)) [LV1] 프로그래머스 문자열 내 마음대로 정렬하기 python 정렬 문제인데, key를 어떻게 사용하는지를 보여주는 아주 대표적인 문제이다. 이랑 비슷한 문제가 itertools의 cmp_to_key를 사용하는게 하나 더 있다. (x[n],x)로 하면 앞에 것을 먼저 적용한 뒤, 같을 경우 뒤 기준을 적용한다. 간단하게 이해하면, 퀵소트 같은 것을 하는데 비교를 대소 대신 이 함수를 쓸 수 있도록 해주는 것이다. 파이썬의 기본은 오름차순이다. 기억합시당. 뒤집으려면 reverse=True 인수를 넣어준다. def solution(strings, n): return sorted(strings, key = lambda x: (x[n],x)) 프로그래머스 DFS/BFS 단어 변환 Python 풀이 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 | 프로그래머스 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> programmers.co.kr 역시 이번에도 잘 푼 사람의 풀이를... 조금 더 python스럽게 최적.. 이전 1 2 3 4 다음
