본문 바로가기

ETC

 (69)
대기업 코딩테스트 준비 7 : 최단 경로 ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. (github.com) 최단 경로 한 지점 특정 지점까지의 거리 이 경우가 많음 다익스트라 그리디 알고리즘 with 우선순위큐(heap) and 다이나믹프로그래밍 O(ElogV) GPS 방문하지 않은 노드 중 최단거리가 가장 짧은 노드 선택 import heapq import sys input = sys.stdin.readline INF = int(1e9) # 무한을 의미하는 값으로 10억을 설정 # 노드의 개수, 간선의 개수를 입력받기 n, m = map(int, input().split()) # 시작 노드 번호를 입력받기 start = int(inpu..
대기업 코딩테스트 준비 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..
대기업 코딩테스트 준비 3 : 구현 python-for-coding-test/8.py at master · ndb796/python-for-coding-test (github.com) ndb796/python-for-coding-test [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - ndb796/python-for-coding-test github.com 구현 완전 탐색 모든 경우 다 계산 DFS/BFS itertools 순열/조합 시뮬레이션 문제에서 시키는 대로 한다 시간을 초로 column = int(ord(inputData[0]))-int(ord('a'))+1 방향 dx, dy dxy = [(1,2),(2,1),(1,-2),(2,-1)] 공간 제한 if 1
대기업 코딩테스트 준비 2 : 그리디 https://github.com/ndb796/python-for-coding-test 해당 내용을 보고 정리한 글임 그리디 현재 상황에서 지금 당장 좋은 것만 고르는 방법 정렬과 자주 사용된다. 거스름돈 대부분의 문제는 그리디 알고리즘으로 최적해를 찾을 수 없음 coin_types = [500,100,50,0] for coin in coin_types: count += n // coin n %= coin print(count) 탐욕적으로 답을 찾을 수 있다는 보장이 있어야 함. 큰 단위가 가장 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없음 무작위면 불가능 큰 수의 법칙 주어진 수를 연속 사용 가능하게 M번 더하여 가장 큰 수를 만드는 법 특정 인덱스에 해당하는 수가 K이상..
대기업 코딩테스트 준비 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)) # 런타임 ..
[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, ..

티스토리툴바