파이썬에서 아주 중요한 점! -> 들여쓰기( 공백 4개 ) 꼭 맞춰서 써야 함! 쓰지 않으면 실행 오류 발생 ❗if문 1. if문의 기본적인 구조 if 조건문: 수행할 문장1 수행할 문장2 ... elif 조건문: 수행할 문장1 수행할 문장2 ... else: 수행할 문장1 수행할 문장2 ... if문의 조건문이 참이라면 그 아래의 문장을 실행한다 거짓이라면 elif로 이동 후 elif의 조건문이 참이라면 그 아래 문장 실행 elif의 조건문도 거짓이라면 else 아래에 있는 문장을 실행 2. 조건문: 참과 거짓을 판단하는 문장 ex) 3 > 5 -> false 3. 비교연산자 x y: x가 y보다 크다 x == y: x와 y가 같다 x != y: x와 y가 다르다 x ..

1. 플로이드-와샬이란? 다익스트라 알고리즘과 같이 최단 거리를 구할 수 있는 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 한번에 구하는 알고리즘 모든 쌍을 행렬로 선언하고 DP를 이용해 각 쌍의 최단 거리를 업데이트한다 거쳐가는 정점을 기준으로 최단 거리를 업데이트한다. 2. 동작 원리 정점 i에서 정점 j까의 최단 경로 dp[i][j] = min(dp[i][j], dp[i][n] + dp[n][j]) n -> 경유점 i에서 j로 곧바로 가는 경우 vs i에서 다른 정점 k를 거쳐 j로 가는 경로 3. 코드 void floyd() { for (int k = 0; k < N; k++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { a..

❗자료형 1. 정수형 Integer: 양의 정수, 음의 정수, 0 2. 실수형 Float: 소수점이 포함된 숫자 3. 문자열 자료형 String: 문자, 단어 등으로 구성된 문자들의 집합 ex) "programming", "Python is fun!" 등 " " ' ' """ """ ''' ''' 작은 따옴표가 쓰일 경우엔 " "으로 전체 문자열을 감싸고 사용한다 큰 따옴표가 쓰일 경우엔 ' '으로 전체 문자열을 감싸고 사용한다 백슬래시(\) 사용: \', \", \\ -> 문자열 안에서 그대로 표현하기 위해 사용한다 익스케이프 코드(줄바꿈): \n 4. 불 자료형 bool: 참과 거짓을 나나내는 자료형 ❗연산자 +, -, *, /, **, %, // -특수한 사칙연산 x ** y: x의 y제곱 x //..

1. 벨만 포드 알고리즘이란? 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 간선의 가중치가 음수일 때도 최단 거리를 구할 수 있다. 다익스트라 알고리즘과 달리 매 반복마다 모든 간선을 확인한다. 시간복잡도가 느리다. -> O(VE) 2. 동작 원리 시작점에서 한 정점 x까지의 최단 경로를 구하다고 하면, x를 제외한 모든 노드(V-1)가 시작점과 x 사이의 최단 경로를 구성한다. 모든 정점으로 가는 최단 경로 갱신 과정을 V-1번 반복하면 된다. 음수사이클이 있는지 알아보려면 1번 더 돌려서 최단 거리가 갱신되는지 확인하기 3. 코드 #define INF 987654321 typedef pair P; long long dist[510]; //각 도시의 거리 계산 long long 필수 vec..

1. 다익스트라 알고리즘이란? Dijkstra 알고리즘은 한 노드에서 다른 노드까지의 최단 거리를 구하는 알고리즘 특정 노드에서 그래프의 모든 노드로 가는 최단 경로를 찾는 알고리즘 1:N관계이며 음수가중치는 없다 2. 동작 원리 dist배열은 시작 노드에서 i번째 노드까지의 거리를 뜻하고, 처음 시작점을 제외한 모든 노드를 INF로 초기화해줘야 함 방문하지 않은 정점 중에서 시작 노드로부터 거리가 가장 가까운 정점을 방문하고 방문한 정점에서 인접한 정점들에 대해서 거리를 갱신해줌 시간복잡도를 줄이기 위해 우선순위 큐를 이용 우선순위 큐는 내림차순으로 정렬되기 때문에 값을 넣을 때 -를 붙여주고 값을 빼낼 때도 -를 붙여서 빼준다 3. 코드 int start; int dist[20010]; vector ..

1. DFS, BFS란? 그래프 탐색: 하나의 정점으로부터 시작해서 차례대로 모든 정점을 한 번씩 방문하는 것 DFS와 BFS는 그래프 탐색의 일종 2. 동작 방식 DFS: 깊이우선탐색 stack이나 재귀함수를 이용함. 루트 노드에서 시작해서 해당 노드의 자식 노드를 먼저 탐색 이동할 때마다 가중치가 있거나 이동 과정에서 제약이 있는 경우 BFS: 너비우선탐색 queue를 이용함. 루트 노드에서 시작해서 해당 노드의 인접 노드를 우선적으로 탐색 단순 최단 경로를 찾는 문제 3. 코드 //1차원 DFS vector adj[1010]; bool visited[1010]; //dfs방문 void dfs(int now) { Dvisited[now] = true; printf("%d ", now); for (in..