어제보다 나은 내가 되기 위한 여정

그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용된다는 특징이 있다. 다익스트라(Dijkstra, 데이크스트라) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 이 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 다익스트라 최단 경로 알고리즘은 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 알고리즘 원리 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 (--> 그..

코딩 테스트에서 구현이란 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 파이썬에서 리스트의 크기 제약 대체로 코딩 테스트에서는 128 ~ 512MB로 메모리를 제한하는데 알고리즘 문제 중 때로는 수백만 개 이상의 데이터를 처리해야 하는 문제가 출제되기도 함. 데이터의 개수(리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 일반적인 기업 코딩 테스트 환경에서는 파이썬으로 제출한 코드가 1초에 2,000만 번의 연산을 수행한다고 가정하면 크게 무리가 없다. 시간 제한이 1초이고, 데이터의 개수가 100만..

1025. Divisor Game https://leetcode.com/problems/divisor-game/ Divisor Game - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제를 푸는데 전혀 감이 오지 않아서 고민하다가 바로 Discussion으로 넘어갔다. class Solution: def divisorGame(self, n: int) -> bool: return n % 2 == 0 1. Top-Down 방식 1) n이 짝수일 때 Alice가 ..

338. Counting Bits https://leetcode.com/problems/counting-bits/ Counting Bits - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com # 나의 코드 class Solution: def countBits(self, n: int) -> List[int]: answer = [] for i in range(n+1): answer.append(bin(i)[2:].count('1')) return answer # Ti..

다이나믹 프로그래밍 : 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. - 중복되는 연산을 줄이자! - 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있다. - DP의 대표적인 예시 : 피보나치수열 다음 조건을 만족할 때 사용할 수 있다. 1) 큰 문제를 작은 문제로 나눌 수 있을 때 2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 메모이제이션(Memoization) 기법 : 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 - 캐싱(Cashing)이라고도 함. 메모이제이션 기법은 어떻게 구현? ->..

programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 1. 첫 번째 시도 정확성: 75.0 효율성: 8.3 합계: 83.3 / 100.0 def solution(phone_book): phone_book.sort() for i in range(len(phone_book)): for j in range(i+1, len(phone_book)): if phone_book[i] in phone_book[j]: return False..