데이터사이언스 기록기📚

1. 다양한 그래프 알고리즘 이미 배운 내용을 훑어보자 - 그래프 알고리즘 유형 DFS/BFS 최단경로 크루스칼 알고리즘(그리디) 위상 정렬 알고리즘(큐, 스택 자료구조) - 그래프 알고리즘 문제 & 구현 방법 '서로 다른 개체(혹은 객체)가 연결되어 있다' '여러 개의 도시가 연결되어 있다' 구현 방법 : 인접 행렬(2차원 배열 사용), 인접 리스트(리스트 사용) * V : 노드의 개수, E : 선의 개수 인접행렬(플로이드 워셜) - 메모리 정보 O(V**2) (간선 정보 저장하기 위함) / 간선 비용 O(1) (A →B 이동) 인접 리스트(다익스트라) - 메모리 정보 O(E) (간선의 개수만큼) / 간선 비용 O(V) (A →B 이동) ⭐ 어떤 문제를 만나든 메모리, 시간을 염두해두고 알고리즘 선택하..

📌한 장으로 보는 알고리즘 DFS 문제풀이 - 스택 이용 - 재귀구조 이용 BFS 문제풀이 - 큐 이용 (파이썬 deque 사용) 📌Q.15 특정 거리의 도시 찾기 ✔️문제 유형 그래프 이론, 그래프 탐색, 너비 우선 탐색, 데이크스트라 ✔️문제 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net ✔️나의 문제풀이 - 시간 초과 from collections import deque import sys n,m,k,x = map(int,input..

📌한 장으로 보는 알고리즘 다이나믹 프로그래밍 - 정의 : 한 번 해결된 부분 문제의 정답을 메모리에 기록 → 한 번 계산한 답은 다시 계산하지 않도록 함 - 구현 : 점화식을 코드로 구현 탑다운과 보텀업 - 다이나믹 프로그래밍을 이용한 소스코드 작성 방법 - 탑다운 : 재귀함수를 이용, 큰 문제를 해결 위해 작은 문제 호출 - 보텀업 : 반복문을 이용, 작은 문제 해결 후 작은 문제를 모아 큰 문제 해결 📌Q.31) 금광 ✔️문제 n*m 크기의 금광, 금광은 1*1 크기의 칸으로 나누어져 있으며 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽,..

📌한 장으로 보는 알고리즘 구현 - 머릿속에 있는 알고리즘 → 프로그램으로 작성 - 간결하고 효율적으로 작성한 코드가 중요 완전 탐색과 시뮬레이션 - 완점 탐색 : 모든 경우의 수를 빠짐없이 다 계산하는 해결방법 → BFS/DFS 알고리즘 이용(반복,재귀 이용한 예외 케이스 모두 활용) - 시뮬레이션 : 문제에서 제시하는 논리, 동작 과정을 그대로 코드로 옮기는 것 +) 원소를 나열하는 모든 경우의 수 : 순열, 조합 라이브러리 사용 📌Q.7) 럭키 스트레이트 ✔️ 문제 유형 구현, 문자열 ✔️ 문제 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net ✔️ 나의 문..