데이터사이언스 기록기📚

1. 가장 빠른 길 찾기 가장 빠르게 도달하는 방법 - 최단경로(Shortest Path): 가장 짧은 경로 찾는 길 찾기 문제 - 문제 보통 그래프 이용하여 표현 (지점 - 노드, 지점 간 연결된 도로 - 간선) 코테 : 최단 거리 출력 >> 최단 경로 출력 - 최단 거리 알고리즘 최단 거리 = 그리디 + 다이나믹 프로그래밍 종류 : 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 - 다익스트라(Dijkstra) : 특정한 노드 출발 → 다른 노드로 가는 각각의 최단 경로를 구함 음의 간선(0보다 작은값)이 없을 때 정상적으로 동작 그리디 알고리즘으로 분류 (가장 비용이 적은 노드 선택하여 임의의 과정 반복) - 원리 방문하지 않은 노드 중에서 가장 최..

1. 다이나믹 프로그래밍 중복되는 연산을 줄이자 - 컴퓨터를 활용해도 해결하기 어려운 문제 최적의 해를 구하기에 시간이 매우 많이 필요 (연산 속도의 한계) 메모리 공간이 매우 많이 필요한 문제 (메모리 공간을 사용할 수 있는 데이터 개수 한정) → 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성 - 다이나믹 프로그래밍 / 동적 계획법(Dynamic Programming) 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 - 예시) 피보나치 수열 : 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 점화식 - 인접한 항들 사이의 관계식, 점화식으로 수열의 항이 이어지는 형태 간결하게 표현. 프로그래밍에서 피보나치 수열을 배열, 리스트로 표..

1. 범위를 반씩 좁혀가는 탐색 순차 탐색 - 이진 탐색 알고리즘 : 리스트 내에서 데이터를 매우 빠르게 탐색 - 순차 탐색(Sequential Search) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 정렬되지 않은 리스트에서 데이터 찾아야 할 때 사용 리스트 내에 데이터가 아무리 많아도 시간만 충분하면 항상 원하는 데이터를 찾을 수 있다. - 사용되는 예시 리스트에 특정 값의 원소가 있는지 체크 리스트 자료형에서 특정한 값을 가지는 원소의 개수 세는 count() 메서드 이용 - 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in r..

1. 기준에 따라 데이터를 정렬 정렬 알고리즘 개요 - 정렬(Sorting) : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것. 정렬 알고리즘 특징 : 이진 탐색의 전처리 과정 정렬 알고리즘 종류 : 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 알고리즘의 효율성 이해할 수 있음(상황에 적절하지 못한 알고리즘 사용 → 비효율적 동작) 더보기 리스트를 뒤집는 연산 : O(N)의 시간복잡도 선택 정렬 - 선택 정렬(Selection Sort) : 매번 가장 작은 것을 선택 데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택하여 맨 앞 데이터와 바꿈. 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복. - 예제 가장 작은 데이터를 앞으로 보내는 과정 N - 1..

1. 아이디어를 코드로 바꾸는 구현 피지컬로 승부하기 1) 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 - (알고리즘에서의) 구현 : 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 문법이 능숙하고 코드 작성 속도가 빠른 사람이 유리 2) 까다로운 구현의 문제 - 사소한 설정이 많을 수록 코드 구현 까다로움 알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제 특정 소수점 자리까지 출력해야하는 문제 문자열이 입력으로 주어질 때 → 한 문자 단위로 끊어서 넣는 문제 - 라이브러리 사용 경험 있어야 함 - 프로그래밍 문법 정확하게 숙지하기 3) 구현의 '종류' - 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결방법 - 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 ..

1. 그리디의 개념 그리디(탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법, 나중에 미칠 영향은 고려하지 않음 - 코딩테스트에서 만나는 그리디 알고리즘 문제 유형 특징 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 (다른 알고리즘 유형은 사용 방법 정확히 알고 있어야 함) 많은 유형을 접해보고 문제를 풀어보며 훈련 창의력을 요함 (최소한의 아이디어를 떠올릴 수 있는 능력) 현재 상황에서 가장 좋아보이는 것만 선택해도 문제 풀 수 있는지 파악하기 예시) '가장 큰 순서대로', '가장 작은 순서대로' +) 정렬 알고리즘과 짝을 이루어 출제 📌예제 3-1) 거스름돈 ✔️문제 (거스름돈으로 사용할 500원, 100원, 50원, 10원짜리의 동전이 무한히 존재한다고 가정) 손님에게 ..