CS

[Algorithm][벨만포드] 백준 11657 : 타임머신

"""BOJ 타임머신 문제 (https://www.acmicpc.net/problem/11657)1 벨만포드 알고리즘2. 시간복잡도- O(VE)3. 자료구조"""import sysinput = sys.stdin.readlineN,M = map(int, input().split())edges = [] #간선 테이블INF = int(1e9)distance = [INF]*(N+1) #최단 거리 테이블for _ in range(M): a, b, c = map(int, input().split()) edges.append((a,b,c))def bellmanford(start): distance[start]=0 for i in range(N): for j in range(M): #..

[Algorithm][다익스트라]

"""시간복잡도 :최단 거리 테이블에서 가장 짧은 거리의 노드를 매번 탐색.해당 노드와 연결된 노드를 또 탐색.=> V = 노드의 개수, O(V^2)* 노드의 개수가 만개 이상이라면, 다른 개선된 알고리즘을 사용해야 한다. """import sysinput = sys.stdin.readlineINF = int(1e9)n, m = map(int, input().split())start = int(input())graph = [[] for _ in range(n+1)]visited = [False] * (n+1)distance = [INF] * (n+1)for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b,c))# 최단..

[Algorithm] 이코테 : 두 배열의 원소 교체

시간복잡도를 잘못 계산했나?왜 계수 정렬이 더 좋아보이지.. """문제: 배열A의 모든 원소의 합이 최대가 되도록 하라.최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값(1 B의 가장 큰 원소2. 시간복잡도(1) 계수 정렬- A, B 정렬 : O(N+R)=10만+10만=20만   참고 - https://www.youtube.com/watch?v=KGyK-pNvWos&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=4

[Algorithm] 선택정렬, 삽입정렬, 계수정렬

1. 선택정렬""" 1. 특징- average,worst,best : 모두 O(N^2)로 동일2. 시간 복잡도 : O(N^2)N + (N-1) + (N-2) + ... + 1 (N^2+N-2)/2 => O(N^2)"""array = [7,4,6,2,1,9,0]for i in range(len(array)): min_index = i #가장 작은 원소의 인덱스 for j in range(i+1, len(array)): print(j, end=' ') if array[min_index] > array[j]: min_index = j print() array[i], array[min_index] = array[min_index], array[i..

[Algorithm][이진탐색] 백준 1920 : 수찾기

"""1. 아이디어- N개의 수 먼저 정렬- M개를 for문 돌면서, 이진탐색- 이진탐색 안에서 데이터를 찾으면 1출력, 아니면 0출력2. 시간복잡도일반) O(N*M) = 1e5 * 1e5 = 1e10 (100억) >> 2억 초과 !이진탐색 개선) - N개의 입력값 정렬 : O(N*logN)- M개를 N개 중에서 이진탐색 : O(M*logN)- 총합 : O((N+M)*logN)=(2e5)*20=4e6 => 가능!3. 자료구조- N개 숫자 : int[] - 모든 수 범위: -2^31   참고 - https://www.youtube.com/watch?v=D1ad7UCbWHY&list=PLi-xJrVzQaxXC2Aausv_6mlOZZ2g2J6YB&index=7

[Algorithm][dfs, bfs] 백준 1260 : dfs와 bfs

"""1. 아이디어- DFS : 재귀- BFS : Queue2. 시간복잡도- graph 초기화 : O(N^2)- BFS : O(N+M)- DFS : O(N+M)3. 자료구조- BFS graph : bool[N+1][N+1] 사용 (popleft가 구현되어있다. 시간복잡도가 낮다)- visited : bool[N+1]- BFS deque4. 학습- 4방향 벡터는 2차원 행렬에서 필요. 이 문제는 1차원 리스트 형태.- queue의 FIFO 특성을 구현한 것: deque"""import sysfrom collections import dequeinput = sys.stdin.readlineN,M,V = map(int, input().split())graph = [[False]*(N+1) for _ in ra..

[Algorithm] 백준 11660 : 구간합 구하기

* 구간합 사용 이유Prefix Sum을 사용하면 배열의 특정 구간의 합을 O(1) 시간에 구할 수 있기 때문이다. 배열의 크기가 크고, 구간 합을 여러 번 계산해야 하는 경우에 유용하다.=> 데이터 분석, 이미지 처리, 게임 개발, 금융 데이터 분석 등 대용량 데이터에서 특정 구간의 통계치를 빠르게 계산해야 하는 경우에 유용 """문제: 11660. 구간합 구하기1. 아이디어- M이 매우 크기 때문에 미리 합이 구해진 구간합 배열: prefix_arr- D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1]2. 시간복잡도O(N^2+M)3. 자료구조prefix_arr = int[N+1][N+1]"""import sysinput = sys.stdin.readline..

[Network] IGRP 라우팅 프로토콜

RIP와 같이 Distance Vector 라우팅 프로토콜에 속한다. Distance-Vector Routing Protocol / Dynamic Routing Protocol / 내부용 라우팅 프로토콜   IGRP (Interior Gateway Routing Protocol)* 배경RIP가 초기에 만들어져서 인터넷이 이렇게 규모가 커질 줄 몰랐다.홉 카운트가 15개 제한..=> IGRP 등장 * 특징1홉 카운트로만 경로를 결정하지 않고,bandwidth, delay, Reliability, Load, MTU => 5가지 요인으로 경로 선택을 한다.속도가 빠른 길 찾아감. RIP보다 똑똑!  * 특징2 최대 홉 카운트: 255 -> 좀 더 큰 네트워크에 사용 가능. * 특징3VLSM(Variable L..

[Algorithm][dfs] 백준-2667

그래프 탐색 알고리즘!DFS = Depth-first search 깊이 우선 탐색자료구조: Stack, 재귀함수 * 재귀함수: 자기 자신을 호출하는 함수종료되는 시점을 정확히 명시하기. 너무 깊어지면 Stack overflow 발생.=> DFS, 백트래킹에서 주로 사용 시간복잡도: O(V+E), vertex + edge  https://www.acmicpc.net/problem/2667"""1. 아이디어- 2중 for, 값이 1이고 방문하지 않았다면 => DFS- DFS를 통해 찾은 값을 저장 후 정렬해서 출력2. 시간복잡도DFS = O(V+E)V : n * nE : n * 4 * nV + E : 5 * n^2O(V+E) : 5n^2=n^2 => 25 * 25 = 625    참고 - 유튜브 선생님 :)..

[Algorithm][bfs] 백준-1926

https://www.acmicpc.net/problem/1926 import sysinput = sys.stdin.readlinen,m = map(int, input().split())arr = [list(map(int, input().split())) for _ in range(n)]chk = [[False]*m for _ in range(n)]# 암기 - 4방향 벡터, 오-위-왼-아dy = [0, 1, 0, -1]dx = [1, 0, -1, 0]def bfs(y, x): # bfs 구현 암기 rs = 1 q = [(y,x)] while q: ey, ex = q.pop() for k in range(4): ny = ey + dy[k] ..

[Network] Distance-Vector 라우팅 알고리즘

v 이더넷과 시리얼 인터페이스는 서로 다른 네트워크여야 한다 v 한 라우터에서 라우팅 프로토콜을 2개 이상 사용해야 한다면 Adminstrative Distance가 가장 작은 게 우선 ! * 라우팅 프로토콜별 Adminstrative DistanceRIP(120), IGRP(100), OSPF(110)Connected interface(0),Static route out an interface(0),Static route to a next hop(1) Distance-Vector 라우팅 알고리즘 라우팅 테이블 정보를 주기적으로 (30초) 계속 전달 업데이트가 모든 네트워크에 전달되는 시간 Convergence Time이 많이 발생한다.=> 루핑 발생 v 루핑이 발생하는 이유한 라우터가 라우팅 정보에 대..

[Network] 라우팅 테이블을 유지&관리하는 방식 2가지

1. Static Routing Protocol: 사용자가 목적지까지 경로를 직접 지정해줌 2. Dynamic Routing Protocol: 라우터가 자동으로 가장 빠른 경로를 찾음  (라우팅 테이블을 유지&관리하는 방식의 차이)(1) Distance Vector Algorithm특징: 각 라우터가 목적지까지의 모든 경로를 라우팅 테이블에 저장하는 것이 아니라, 목적지까지의 거리(홉 카운트) 와 어떤 인접 라우터를 거쳐야 하는지 방향만을 저장한다. 인접 라우터와 주기적으로 라우터 정보를 공유하여 라우팅 테이블을 구성한다. 소형 네트워크에 적합. 장점: 메모리가 적게 들고, 구성이 쉬움. 단점: 라우터 정보가 바뀌든 안 바뀌든 주기적으로 정보를 공유해야 하기 때문에 불필요한 트래픽이 발생함. 한번 정보 ..

VSCode C++ 환경설정

상세 참고 - https://rasino.tistory.com/307 【 C 환경설정 】 VS code에서 C/C++ 코딩환경 구축하기 【 C 환경설정 】 VS code에서 C/C++ 코딩 환경 구축하기 요즘 파이썬(python)이나 자바(JAVA), javascript C# 등등 하이레벨 언어를 학습하던 사람들이 프로그래밍의 근간을 튼튼히 한다거나? 여러 가지 이 rasino.tistory.com => 설명 아주 잘 나와 있다😀 1. vscode 설치 + 확장프로그램 C++ 설치 2. MingGW 설치 https://sourceforge.net/projects/mingw/ 3. 환경 변수 등록 4. vscode 재실행 후 tasks.json, keybingings.json 설정 5. 완료

이클립스 - console 한글 깨짐 오류

python venv 버전 downgrade - virtualenv

python3에서 python2로 다운그레이드 하는 방법 ! python3 pip install virtualenv python버전 지정해서 가상환경 디렉터리 생성: virtualenv venv --python=python2.7 가상환경 들어가기 : ( activate가 있는 곳에서) source ./activate 가상환경 나가기 : deactivate 파이썬에서 venv로 가상 환경 사용하기 Engineering Blog by Dale Seo www.daleseo.com

윈도우에서 python2, python3 실행하기

python2, python3 둘다 python.exe 여서 이름이 겹친다. 구분시켜줘야한다. 1. python2, python3 다운로드 받기 2. python2, python3 설치 경로 파악 ( python.exe 가 있는 경로 ) python2 : C:\Python27 python3 : C:\Users\esther\AppData\Local\Programs\Python\Python310 3. 심볼릭 링크 생성 python2 : mklink C:\Windows\python2.exe C:\Python27\python.exe python3 : mklink C:\Windows\python3.exe C:\Users\esther\AppData\Local\Programs\Python\Python310\pytho..

strcmp함수

두 문자열이 같은지 비교하는 함수이다. strcmp 원형 int strcmp(const *_Str1, char const *_Str2); strcmp 반환값 - 아스키코드 기준 str1 > str2 : 1반환 str1 < str2 : -1반환 str1 = str2 : 0반환 예제코드 #include #include #include int main() { char password[] = "aaaa"; char user[] = "b"; int result = strcmp(password, user); if ( result == 0) { printf("\nFlag is \"Welcome\"\n"); } else if (result < 0) { printf("\nResult : %d\n", result); } ..