CS/Algorithm

[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..

[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] ..

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. 완료