본문 바로가기
728x90

그 땐 Algorithm했지/그 땐 Python했지

 (21)
[TAVE/이코테] ch10 그래프 이론 | 실전 문제 참고자료: 이것이 코딩테스트다 2. 실전 - 팀 결성 team_count, calculation = map(int, input().split()) parent = [0] * (team_count + 1) #[0, 0, 0, 0, 0, 0, 0, 0] #각 num번 팀에 num번 학생을 속하게 한다. for num in range(team_count + 1): #[0, 1, 2, 3, 4, 5, 6, 7] parent[num] = num def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return parent[x] for _ in range(calculation): cal, student1, studen..
[TAVE/이코테] ch10 그래프 이론 | 개념 정리 참고자료: 이것이 코딩테스트다 그래프 📌노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 👉🏻그래프 구현 방식 인접 행렬: 2차원 배열을 사용하는 방식 인접 리스트: 리스트를 사용하는 방식 🐰다양한 그래프 알고리즘을 알아보자! 1️⃣ 서로소 집합 📌공통 원소가 없는 두 집합 ✅서로소 집합 자료구조 📌서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조를 말한다. 👉🏻union(합집합)연산과 find(찾기)연산으로 조작할 수 있어 union-find 자료구조로 불리기도 한다. 👉🏻트리 자료구조를 이용해 집합을 표현하고 계산 알고리즘은 다음과 같다. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 노드 A', B'를 각각 찾는다...
[TAVE/이코테] ch09 최단 경로 | 실전 문제 참고자료: 이것이 코딩테스트다 실전 - 미래 도시 INF = int(1e9) company_count, road_count = map(int, input().split) graph = [[INF] * (company_count + 1) for i in range(company_count + 1)] for i in range(1, company_count + 1): for j in range(1, company_count + 1): if i == j: graph[i][j] = 0 for _ in range(road_count): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 x, k = map(int, input.split()) for ..
[TAVE/이코테] ch09 최단 경로 | 개념 정리 참고자료: 이것이 코딩테스트다 가장 빠르게 도달하는 방법 📌최단경로: 가장 짧은 경로를 찾는 알고리즘 👉🏻보통 그래프를 이용해 표현한다. 각 지점은 그래프에서 '노드'로 표현되고 지점간 연결된 도로는 그래프에서 '간선으로'표현된다. 최단경로 알고리즘 종류는 다음과 같다. 다익스트라 알고리즘 플로이드 워셜 벨만 포드 알고리즘 다익스트라 최단 경로 알고리즘 📌그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구한다. '음의 간선'이 없을 때 정상적으로 동작하는데 이러한 특성으로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 👉🏻기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 원리는 ..
[TAVE/파이썬 알고리즘 인터뷰] Ch13 | 최단 경로 문제 - 개념 정리 참고자료: 파이썬 알고리즘 인터뷰 최단 경로 문제 📌최단 경로 문제: 각 간선의 가중치 합이 최소가 되는 두 정점(또는 노드) 사이의 경로를 찾는 문제다. 정점: 교차로 간선: 길 가중치: 거리나 시간과 같은 이동 비용 👉🏻그래프의 종류와 특성에 따라 각각 최적화된 다양한 최단 경로 알고리즘이 존재한다. 다익스트라 알고리즘 📌최단 경로 알고리즘 중 가장 유명하다. 네덜란드의 유명한 컴퓨터과학자 에츠허르 다익스트라가 대학원생 여자친구와 카페에 가서 20분 만에 고안한 알고리즘이다. 단순한 알고리즘이 가장 훌륭한 알고리즘이라는 것을 증명하는 대표적인 알고리즘이다. 1️⃣그리디 알고리즘 👉🏻구현하기 쉽지만 느리게 동작한다. 👉🏻다익스트라의 최초 구현에서는 시간 복잡도가 O(V제곱)였다. 왜냐하면 방문하지 않은..
[TAVE/파이썬 알고리즘 인터뷰] Ch11 | 해시 테이블 - 개념 정리 참고 자료: 파이썬 알고리즘 인터뷰 📌해시 테이블 또는 해시 맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료이다. 👉🏻대부분의 연산이 분할 상환 분석에 따른 시간 복잡도가 O(1)이다. 해시 📌해시 함수: 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수 📌해싱: 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것 ABC → A1 1234BC → CB AF32B → D5 👉🏻위의 각각 3글자, 6글자. 5글자인 문자열을 모두 2바이트의 고정 크기 값으로 매핑했다. 여기서 화살표 역할을 하는 함수가 해시 함수이다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용한다. 생일 문제 더보기 💡 여러 사람이 모였을 때 생일이 같은 2명이 존재할..
[TAVE/이코테] ch08 다이나믹 프로그래밍 | 실전 문제 참고자료: 이것이 코딩테스트다 실전 - 1로 만들기 x = int(input()) d = [0] * 30001 for i in range(2, x + 1): d[i] = d[i - 1] + 1 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1) if i % 5 == 0: d[i] = min(d[i], d[i // 5] + 1) print(d[x]) 👉🏻d의 각 자리에 연산을 얼마나 했는지 저장해주는 것이 point다. 숫자를 for문 돌리면서 각 연산을 모두 시도해준다. if-else문이 아닌 3개의 if문을 쓴 건 모든 연산을 다 가능한지 확인하기 위함이다. d[i]의 이전값이 d[x-1..
[TAVE/이코테] ch08 다이나믹 프로그래밍 | 개념 정리 참고자료: 이것이 코딩테스트다 중복되는 연산을 줄이자 📌동적 계획법이라고도 하며 메모리 공간을 약간 더 사용해 연산 속도를 비약적으로 증가시키는 방법이다. 👉🏻다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 파이썬에서 이러한 수열을 배열이나 리스트로 표현할 수 있다. 📌피보나치 수열: 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열 👉🏻점화식: \( a_{n+2} = f(a_{n+1}, a_n) = a_{n+1}, a_n )\ n번째 피보나치 수 = (n-1)번째 피보나치 수 + (n-2)번째 피보나치 수 단, 첫번째와 두번째 피보나치 수 = 1 👉🏻위의 점화식을 프로그래밍을 표현하려면 재귀 함수를 사용하면 간단하다. def fibo(x): if x == 1 o..
728x90

티스토리툴바