짧은코딩

위상 정렬 위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져 있는 작업을 차례대로 수정할 때 사용하는 알고리즘이다. 예시로는 선수 과목을 고려한 학습 순서 설정이 있다. 예를 들어 자료구조, 알고리즘, 고급 알고리즘이 있다. 그리고 (알고리즘의 선수 과목은 자료구조), (고급 알고리즘의 선수 과목은 알고리즘)이면 자료구조 -> 알고리즘 -> 고급 알고리즘으로 수업을 들어야한다. 위상 정렬은 먼저 진입차수를 알아야 하는데, 진입차수느 특정 노드로 들어오는 간선의 개수를 의미한다. 잔입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지, 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 위 과정을 거치다가 모든 원소를 방문하기 전에 큐..

신장 트리 신장 트리는 그래프가 있을 때, 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 크루스칼 알고리즘 -크루스칼 알고리즘 원리 https://shortcoding.tistory.com/141?category=1009070 그래프(1) 완전 그래프 각 정점에서 다른 모든 정점을 연결해 최대로 많은 간선 수를 가진 그래프 무방향 그래프 최대 간선 수: n(n-1)/2개 방향 그래프 최대 간선 수: n(n-1)개 그래프 구현 -인접 행렬 무방향 shortcoding.tistory.com 원리는 이전에 알고리즘 수업을 정리했던 글을 참고하면 될 것이다. 특징으로는 최종적으로 신장 트리에 포함되는 간선의 개수가 (노드의 개수 - 1)이다. -예시 코드 # 특정 원소가 속한 집합을 찾..

-html -css body { margin: 0; } .big-box { background-color: #ff6446; height: 100vh; display: flex; justify-content: center; align-items: center; } .middle-box { border: 3px solid black; padding: 10px; width: 300px; height: 300px; background-color: #f5deb3; display: flex; flex-direction: column; justify-content: space-evenly; align-items: center; } .small-box, .long-box { background-color: #00808..

운영체제의 역할과 구조 -운영체제의 역할 1. CPU 스케줄링과 프로세스 관리: CPU 소유권을 어떤 프로세스에 줄지, 프로세스 생성과 삭제, 자원 할당 및 반환을 관리 2. 메모리 관리: 한정된 메모리를 어떤 프로세스에 얼만큼 할당 할지 관리 3. 디스크 파일 관리: 디스크 파일을 어떤 방법으로 보관할지 관리 4. I/O 디바이스 관리: I/O 디바이스들인 마우스, 키보드와 컴퓨터 간에 데이터를 주고 받는 것을 관리 -운영체제 구조 여기서 GUI, 시스템콜, 커널, 드라이버가 운영체제이다. 리눅스 서버는 GUI가 없고 CUI만 있다. GUI: 사용자와 장치와의 상호 작용이 가능한 사용자 인터페이스 형태, 마우스로 클릭하면서 컴퓨터와 상호 작용할 수 있다. 드라이버: 하드웨어를 제어하기 위한 소프트웨어 ..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 해결법 이 문제는 다익스트라 알고리즘을 활용해서 푸는 문제다. graph에 연결된 노드를 저장할 때는 플로이드 알고리즘과 다르게 저장한다는 점을 다시 기억하면 좋을 것 같다. 다익스트라 알고리즘에서 graph에 연결된 노드를 저장하는 법은 시작 노드 a, 연결된 노드 b, 가중치 c를 graph[a].append(b, c)이다. 이 점을 유의하고 푼다면 좀 더..

네트워크는 노드와 링크가 서로 연결되어 있거나 연결되지 않은 집합체를 의미한다. 여기서 노드란 서버, 라우터, 스위치 등 네트워크 장치를 의미하고 링크는 유선 혹은 무선을 의미한다. 처리량과 지연 시간 좋은 네트워크란 많은 처리량을 처리 할 수 있고 지연 시간이 짧고 장애 빈도가 적으며 좋은 보안을 갖춘 네트워크를 말한다. -처리량(throughput) 처리량은 링크를 통해 전달되는 단위 시간당 데이터양을 말한다. 단위로는 초당 전송/수신되는 비트 수라는 의미의 bps(bits per second)를 사용한다. 처리량은 이용자가 많아질 때 커지는 트래픽, 네트워크 장치 간의 대역폭, 네트워크에서 발생하는 에러, 하드웨어 스팩에 영향을 받는다. 대역폭(bandwidth): 주어진 시간 동안 네트워크 연결을..

그래프 구현 방법 그래프 구현 방법은 2가지 방식이 존재한다. 하나는 2차원 배열을 사용하는 방식인 인접 행렬(Adjacency Matrix)이 있고 다른 하나는 리스트를 사용하는 방식인 인접 리스트(Adjacency List) 방식이 있다. 노드의 개수가 V개, 간선의 개수가 E인 그래프가 있다고 하고 두 방식을 비교한다. 1. 인접 행렬 메모리 공간: 간선의 정보를 저장하기 위해 O(v^2)의 메모리 공간 필요 다른 노드까지의 가중치를 알아내는 시간: O(1)의 시간으로 즉시 알아낼 수 있음 2. 인접 리스트 메모리 공간: 간선의 개수만큼인 O(E)의 메모리 공간이 필요 다른 노드까지의 가중치를 알아내는 시간: O(V)만큼의 시간이 요소 앞에서 배운 다익스트라 알고리즘은 인접 리스트를 이용하는 방식이..

해결법 내 풀이는 플로이드 알고리즘을 활용해서 먼저 그래프를 만들었다. 그리고 출발 노드인 지점에서 몇 개의 노드가 연결되어 있는지 확인하고 가중치가 가장 긴 시간의 노드의 값을 구하면된다. 내 풀이 INF = int(1e9) n, m, c = map(int, input().split()) graph = [[INF] * (n+1) for i in range(n+1)] for i in range(1, n+1): graph[i][i] = 0 for i in range(m): x, y, z = map(int, input().split()) graph[x][y] = z for k in range(1, n+1): for a in range(1, n+1): for b in range(1, n+1): graph[a]..

풀이법 이 문제는 최소 이동 경로를 찾아야해서 플로이드 알고리즘으로 풀어야 한다. 모든 회사 사이의 가중치는 1이며 양방향 연결로 구성되어 있다. graph 이중 리스트를 만들고 이 안에 자기 자신으로 향하는 방향은 0을 넣어줬다. 그리고 삼중 배열로 최단 거리를 구해주면 된다. 코드 INF = int(1e9) n, m = map(int, input().split()) graph = [[INF] * (n+1) for i in range(n+1)] for i in range(m): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 for i in range(1, n+1): graph[i][i] = 0 x, k = map(int, input(..

branch -설명 branch는 코드들의 멀티버스라고 볼 수 있다. git은 어떤 commit이라도 받을 수 있게 해준다. 그림에서 동그라미는 commit이다. 어떤 commit라도 거기에서 Master branch와 다른 프로젝트를 시작할 수 있다. 대부분의 사람들은 어느 정도 검증된 코드를 commit한다. branch1, branch2는 각각 다른 commit을 갖는데, 다른 기능을 추가하거나 실험하고 싶을 때 이렇게 나눌 수 있다. 그리고 나중에 갈라진 branch를 master branch에 합칠 수 있다. -적용법 예시 깃허브 데스크탑에서 experimental이라는 새로운 branch를 만들어준다. 새로 만든 experimental branch의 history에 가도 master와 같은 기..