본문 바로가기

파이썬

 (23)
대기업 코딩테스트 준비 6 : 다이나믹 프로그래밍 다이나믹 프로그래밍 중복된 연산을 줄이자 메모리 공간 활용을 통해 연산 속도 비약적 향상 탑다운 큰 문제를 해결하기 위해 작은 문제 호출 재귀 빅뱅 바텀 업 작은 문제부터 점진적 답 도출 반복문 메모이제이션 다이나믹 프로그램 실행 도중에 여기서는 이런 의미 아님 점화식 인접항 간 관계식 수열을 리스트로 표현 조건 큰 문제를 작은 문제를 나눌 수 있음 작은 문제에서 구한 정답은 큰 문제에서도 동일 메모이제이션 === 캐싱 practice : 1로 만들기 # 정수 X를 입력 받기 x = int(input()) # 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) for i in range(2, x ..
대기업 코딩테스트 준비 5 : 이진 탐색 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 이진 탐색 순차 탐색 : 맨 앞에서부터 하나씩 확인 정렬되지 않은 데이터 이진 탐색: 정렬된 데이터 ​ O(logN) 파라메트릭 서치 최적화 문제 > 결정 문제 원하는 조건을 만족하는 가장 알맞은 값 찾기 범위가 어마어마하게 큰 조건 떡 썰기 필요한 길이보다 크면 시작점 증가 필요한 길이보다 크면 끝점 감소 ..
대기업 코딩테스트 준비 5 : 정렬 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 정렬 데이터를 특정한 기준에 따라서 순서대로 나열 그리디랑 자주 쓰임 이진 탐색 계수 정렬을 꼭 써야 하는 경우가 아니면 기본 제공 정렬 라이브러리를 활용한다. 선택 정렬 for i in range(len(arr)): minIdx = i for j in range(i+1,len(arr)): if arr[min..
[LV2] 프로그래머스 문제풀이 섬 연결하기 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 해당 문제는 프림 알고리즘과 크루스칼 알고리즘을 활용하여 해결할 수 있다. 먼저 프림 알고리즘을 살펴보자 # 프림 알고리즘 import heapq as hq def solution(n, costs): graph = {} # 직전 노드 - 방문 노드 체크에도 사용 pi = {} # 해당 노드에 접근하는데 필요한 비용 - 다익스트라에서는 시작점에서 해당 점으로의 거리로 변경 d = {} answer = 0 # 프림 알고리즘은 지도를 만들어준다. for f, t, ..
[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))

티스토리툴바