집에가고싶을때마다

•  About
•  Project
•  IT
•  Travel
•  ETC

Network Flow 특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는 지를 측정하는 알고리즘 - 네트워크 데이터 전송, 교통 체증, 물류 시스템 등에 활용 - 내 컴퓨터에 1초에 몇 MB의 자료를 전송 받을 수 있는가에 대한 측정 유량(Flow)/용량(Capacity) 용량(Capacity): c(u, v) u → v로 갈 때, 보낼 수 있는 최대 용량 유량(Flow): f(u, v) 실제 보내는 용량 - 최대 유량: 간선 중 가장 용량이 작은 간선에 의해 결정 유량 네트워크 https://soobarkbar.tistory.com/198 (a) s → a → c → t의 경로를 따라 자료를 전송할 때, c → t 간선 용량이 10으로 가장 작음 ▶ 최대 유량 = 10 (b) 여러 개의 ..

백트래킹(Backtracking) 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 - 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 것 ▶ 가지치기 - DFS로 모든 경우의 수를 탐색하는 과정 👉 스택 사용 / 스택에 넣기 전 유망성 검사 - 현재 노드가 유망하지 않으면 부모 노드로 되돌아간 후 다른 자손 노드를 검색하는 방법 ▶ 풀이시간 단축 참고: https://idea-sketch.tistory.com/29

위상 정렬(Topological Sort) 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않고 모든 정점을 나열하는 것 특징 - 하나의 방향 그래프에서 여러 위상 정렬이 가능 ex 1) 대학생되기 → 4학년 되기 → 정보처리기사 합격하기 → 자격서류 제출하기 → 졸업시험 신청 → 졸업하기 2) 대학생되기 → 학과사이트 가입하기 → 졸업시험 신청하기 → 졸업하기 - DAG에만 적용이 가능 ▶ 사이클이 발생하는 경우 위상 정렬 수행 불가 DAG란? 2021.07.07 - [IT/CS] - [알고리즘] 방향 비순환 그래프 [알고리즘] 방향 비순환 그래프 Directed Acyclic Graph, DAG = 방향 비순환 그래프 = ..

Directed Acyclic Graph, DAG = 방향 비순환 그래프 = 유향 비순환 그래프 = ... 그래프 간선(Edge)에 이 있고, 처음 출발한 노드(정점) v에서 시작하여 다시 v로 돌아가는 방법이 없는 그래프 용어 선행자(predecessor)와 후행자(successor) DAG에서 어떤 정점 i, j에 대해 i에서 j로의 경로가 존재할 때, i = j의 선행자 j = i의 후행자 즉각 선행자(immediate predecessor)와 즉각후행자(immediate successor) DAG에서 어떤 정점 i, j에 대해 i에서 j로의 간선이 존재할 때, i = j의 즉각 선행자 j = i의 즉각 후행자 예시 - 작업의 우선순위 표현 > 선행 작업 완수 후 작업이 진행되어야 하는 경우

알고리즘을 풀다보면 종종 ArrayList와 LinkedList를 어떻게 적재적소에 사용해야하는 지 고민하게 된다. ArrayList LinkedList 특징 배열 노드 삽입/삭제 시 Shift 연산 다음 노드의 위치를 저장 메모리 공간 연속적 비연속적 저장 순서 논리적 저장 순서 = 물리적 저장 순서 논리적 저장 순서 != 물리적 저장 순서 메모리 할당 정적 메모리 할당 동적 메모리 할당 Search O(1) O(n) Random Access Insert O(n) 맨 앞/뒤: O(1) 중간: O(n) > ArrayList Delete O(n) O(n) > ArrayList ArrayList - 삽입/삭제가 일어날 때는 Shift 연산으로 인해 시간이 더 걸리게 된다. - 데이터 삽입 시, 모든 공간이 ..

문제 www.acmicpc.net/problem/11404 - N개의 지점과 M개의 간선이 주어진다. - 가중치를 가진 단방향 그래프 - 입/출력의 시작을 1로 봐야한다. 해설 및 코드 - 플로이드와샬 알고리즘으로 쉽게 풀 수 있다. - 개인적으로 골드4 정도는 아닌 듯... - 플로이드와샬 알고리즘을 할 때, 항상 배열의 초기화를 987654321로 한다. Intger. MaxValue를 쓰게 되면 + 계산 시 -가 나와서 최소 값을 제대로 찾지 못하기 때문이다. package 백준; import java.util.Arrays; import java.util.Scanner; public class 플로이드_11404 { public static void main(String[] args) { Scann..

Java가 주 언어이므로 Python을 공부할 겸 Python으로 문제를 풀었다. 따라서, Python 문법에 대한 설명이 포함되어 있다. 문제 - N개의 숫자 배열(arr)을 입력받았을 때, 각각의 숫자(총 M개)가 arr 배열에 포함이 되는지를 묻는 문제이다. - 배열을 모두 탐색하면서 숫자가 존재하는 지를 반복문을 통해 찾으면 된다고 생각했지만, 그러면 시간초과 오류가 난다! 해설 및 코드 - for문을 이용하여 탐색하면 O(N)의 시간이 걸린다. - 이진탐색은 O(logN)의 시간이 걸리므로 for문으로 탐색하는 것보다 더 적은 시간이 걸린다. - 하지만 이진 탐색 전에 반드시 탐색할 배열을 sort 해줘야 한다. 안하면은 절반으로 나누면서 가는 이유가 없잖아? # bs 함수 - 이진탐색 # lo..