📊 Algorithm91 🧚♂️알고리즘🧚♂️ - 그래프 - 플로이드 워셜 🧚♂️플로이드 - 워셜🧚♂️ 모든 노드 간 최단 경로 탐색 (음수 가중치 있어도 가능) (종적 계획법(DP) 원리 이용) 시간복잡도 : O(V^3) 노드 개수의 범위가 작아야 함. (모든 노드부터 모든 노드까지의 최단거리 구하기 때문. 시작노드 하나부터 모든 노드까지의 최단 구하는 다익스트라/벨만포드 와는 다름) 최단 경로 위에 어떤 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로임. => 전체 경로의 최단 경로는 부분 경로의 최단 경로 조합으로 이뤄진다. -> 점화식 : "S에서 E까지의 최단 거리" = Math.min("원래 S에서 E까지의 최단 거리", "S에서 K까지의 최단 거리"+"K에서 E까지의 최단 거리") ! 중간다리(K,연결지점) 에 핵심이 있는 알고리즘 1. 리스트 선언하.. 2023. 7. 12. 🧚♂️알고리즘🧚♂️ - 그래프 - 벨만 포드 🧚♂️벨만-포드🧚♂️ 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 "음수 가중치 에지" 가 있어도 수행 가능! 전체 그래프에서 "음수 사이클의 존재 여부" 판단 가능! 다익스트라는 음수 있으면 불가!! 세으니 추천글 [알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm) 벨만-포드 알고리즘(Bellman-Ford Algorithm)이란? velog.io 1. 에지 리스트 이용해서 그래프를 구현하고 최단 경로 리스트(결과) 초기화 2. 모든 에지를 확인해 정답 리스트 업데이트하기 노드 개수 -1 만큼 업데이트 진행 ( 두 노드 사이 거리는 "노드 개수 -1" 이 최대이기 때문) '종료노드의 결과 리스트값'이 '시작 노드의 결과 리스트값' + '가중치'보다 클 때 이 값.. 2023. 7. 8. 🧚♂️알고리즘🧚♂️ - 그래프 - 다익스트라 Dijkstra Algorithm 그래프에서 최단 거리를 구하는 알고리즘 특정 노드에서 다른 노드들의 최단 거리 구하기 기능 출발 노드와 모든 노드 간의 최단 거리 탐색 특징 에지가 모두 양수 시간 복잡도 O(에지 수*log(노드수)) 최단거리 구하기이기 때문에 BFS와 상당히 유사 (큐 이용/방문리스트활용) 그 세부 버전 같기도(최단거리 계산 추가된) 🥇골드5 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1) 거리 리스트에서 방문하지 않은, 현재 값이 가장 작은 노드.. 2023. 7. 5. 🧚알고리즘🧚-그래프- 위상 정렬 🧚위상 정렬🧚 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 시간 복잡도 : O(노드 수 + 에지 수) 사이클이 존재하면 안 됨 -> 노드 간의 순서를 명확하게 정의할 수 없기 때문 위상 정렬이 늘 같은 정렬 결과를 보장하지는 않음(위상이 같은 노드가 존재할 시) 진입 차수(in-degree) : 자기 자신을 가르키는 에지의 개수 1. 인접 리스트를 만든 후 이를 이용해 진입 차수 리스트를 만든다. 2. 진입 차수가 0인 노트를 선택하고 -> 선택된 노드를 결과 리스트에 저장 / 인접 리스트에서 선택된 노드들의 진입 차수를 1씩 빼기 3. 모든 노드가 정렬될 때까지 2 반복하기. (0이 생기지 않는 경우 없음) 🥇골드 3 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(.. 2023. 7. 1. 🧚알고리즘🧚-그래프- 유니온 파인드 🧚유니온 파인드🧚 두 노드가 같은 그래프에 속하는지 판별하는 그래프 알고리즘 union 연산 : 각 노드가 속한 집합을 하나로 합치는 연산 1. 리스트를 자신의 인덱스값으로 초기화하기 2. 2개의 노드를 선택해 각각의 대표 노드를 찾아 연결하는 연산을 수행 (인덱스값과 밸류값이 같지 않을 시 대표 노드가 아니므로 대표노드를 찾을 때까지 수행하여 그 값을 밸류값에 넣기) find 연산 : 특정 노드가 속한 집합의 대표 노드를 반환하는 연산 1. 대상 노드 리스트의 '인덱스값==밸류값' 인지 확인 2. 아닐 시 밸류값이 가진 값을 인덱스값으로 한 노드로 이동 3. '인덱스값==밸류값' 일 때까지 1,2를 반복(재귀함수) 4. 대표 노드를 발견하면 거쳐나온 모든 노드의 밸류값을 대표 노드값으로 변경! 시간 복.. 2023. 6. 28. 🧚♂️알고리즘🧚♂️ - 그래프 - 그래프기초 🧚🏻♀️그래프🧚🏻♀️ 노드 : 데이터를 표현하는 단위 에지 : 노드를 연결 🧚🏻♀️그래프 구현법🧚🏻♀️ 1. 에지 리스트 에지를 중심으로 그래프 표현 [출발 노드 / 도착 노드 / (가중치가 있을 시) 가중치] 로 표현 + 벨만 포드 알고리즘 / 크루스칼 알고리즘 등에 사용(노드 중심 알고리즘엔 잘 사용되지 않음) 2. 인접 행렬 노드를 중심으로 그래프 표현 가중치가 존재할 시 1 대신 가중치로 표현 + 노드 개수에 비해 에지가 적을 때는 비효율적 3. 인접 리스트 인덱스 번호의 리스트에 인접한 노드를 다 넣어두기 가중치가 있을 시 [(a,b),(c,d)] 형태로 저장 + 젤 편한 듯 리스트에 같은 값 쉽게 넣는 방법 ([0,0,0] 예시) 1. [0]*3 2. [0 for _ in range(3.. 2023. 6. 24. 📝 알고리즘 목표 📝 📝 알고리즘 목표📝 (2023년 6월 5일 기준) ✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪✪ ⌯⌯ ❃ solved.ac 티어 ❃ ⌯⌯ 2023 2학기 개강 전까지 ❇️플래티넘❇️ 달기 ⌯⌯ ❃ 백준(BOJ) 문제 수 ❃ ⌯⌯ 2023 2학기 개강 전까지 500 Solve+ ⌯⌯ ❃ 클래스 깨기 ❃ ⌯⌯ 2023 7월까지 클래스 3++깨고 4 넘어가기 ⌯⌯ ❃ 백준(BOJ) 단계별 풀기 ❃ ⌯⌯ 2023 2학기 개강 전까지 28단계까지 깨기 (우선순위 큐까지 / 대략 65문제 남) ⌯⌯ ❃ 대회 ❃ ⌯⌯ - 2023 summer SUAPC 출전 4solve 하기 - ICPC 출전 : ?? 멋진언니들사이에끼어가기 백준에서 열리는 대회 확인해보기 ⌯⌯ ❃ 스터디 ❃ ⌯⌯.. 2023. 6. 5. 🧚♂️ !기본편 끝! 🧚♂️ '프로그래밍/알고리즘 - python' 카테고리의 글 목록 코딩공부(동아리.스터디.공모전.대외활동)/책/등등 junggoldchae-coding.tistory.com 책(DOIT 알고리즘 코딩 테스트!) 의 기본편이 끝났다!! 여기까지 오는 데 이렇게 오래 걸릴 줄 몰랐다. 실전편이 더 어렵고 길던데 방학 안에 다 끝내보게 노력하겠다. 그리고 완독 후에는 "파이 한 조각을 조" 알고리즘 스터디로 summer SUAPC에 출전할 계획이다. 또 아직 실력이 부족하지만ㅇ.. 알고리즘 과 동아리 EDOC의 회장이랑 (+신촌 SUAPC 운영진 + 전국 대학생 프로그래밍 대회 동아리 연합단) 학교 알고리즘 e-class 알튜비튜의 튜터를 맡게 되었다! 이대는 알고리즘 활성화가 잘 안 되어 있는 것 같아서..ㅜ 항상.. 2023. 5. 31. 🧚♂️알고리즘🧚♂️ - 정수론2(유클리드 호제법) 🔢유클리드 호제법🔢 두 수의 최대공약수 gcd()를 구하는 알고리즘 🍀기본 방법 소인수 분해를 이용 / 공통된 소수들의 곱 구하기 🍀유클리드 호제법 1 ) 큰 수를 작은 수로 나누는 MOD 연산 수행 2 ) 앞 단계에서의 작은 수와 MOD 연산 결과값(나머지)로 MOD 연산 수행 3 ) 단계 2를 반복하다가 MOD 값이 0이 되는 순간의 작은 수가 최대공약수 + MOD 연산 : 두 값을 나눈 나머지를 구하는 연산 (%) + 최소공배수 : 두 수의 곱을 최대공약수로 나누면 됨 최대공약수/ 최소공배수 구하는 보편적 코드 # 최대공약수 def gcd(n, m): for i in range(min(n,m),0,-1): if n%i ==0 and m%i==0: return i # 최소공배수 def lcd(n, m.. 2023. 5. 26. 🧚🏻♀️알고리즘 tip! 모으기🧚🏻♀️ 🧚🏻♀️알고리즘 tip!🧚🏻♀️ - 반복해서 쓰이는 것이 있을 시 한번만 구해 리스트에 넣어놓고 사용한다. + 구간합! - 자료구조 여러 개 쓸 때 '인덱스 번호' 활용하여 쓰기 ( 인덱스 번호와 실제 값 유리시키기) 라고 써놨는데 무슨말이냐 과거의 은체야 이해가 안 돼 - 펠린드롬 수를 구할 때 - "연속된" 뭔가에 대한 값을 구할 때 - 두 개를 골라야 할 때 등 투 포인터를 이용하자 - 리스트에서 범위를 유지시키며 탐색할 때 (IOIOI문제같이) 슬라이딩 윈도우를 이용하자 - 2차원 리스트에서 깊이 등 찾기 리스트에 표시하며 활용하기 - 백트래킹(역순 문자열 만들기, 등) - 깊이 우선 탐색할 떼 - 두개 짝지어서 연결할 때 등 선입후출 필요시 스택 쓰기 - 원형 형태의 데이터 필요 시 - 너비.. 2023. 5. 20. 이전 1 ··· 4 5 6 7 8 9 10 다음
