짧은코딩

해결법 문제를 보고서 이 문제는 경로 압축으로 루트 노드를 찾는 함수를 팀 합치기 연산으로 사용한다. 그리고 루트 노드가 같은지 판단하는 함수를 같은 팀 여부 확인으로 풀었다. 코드(한번에 맞음) n, m = map(int, input().split()) def find_parent(parent, x): if parent[x] != x: find_parent(parent, parent[x]) return parent[x] def union(parent, a, b): a = find_parent(parent, a) b = find_parent(parent, b) if a < b: parent[b] = a else: parent[a] = b parent = [i for i in range(n+1)] answ..

데이터베이스(DataBase)는 일정한 규칙, 규약을 통해 구조화되어 저장된 데이터 모음이다. DBMS(DataBase Management System)는 DB를 제어, 관리하는 통합 시스템이다. DB 안에 있는 데이터들은 특정 DBMS마다 정의된 쿼리 언어(query language)를 통해 삽입, 삭제, 수정, 조회 등이 가능하고 DB는 실시간 접근, 동시 공유가 가능하다. 예를 들어 MySQL이라는 DBMS가 있고 Node.js, php 같은 응용 프로그램에서 DB안에 있는 데이터를 꺼내 데이터 관련 로직을 구축할 수 있다. 엔티티(entity) 엔티티는 사람, 장소, 물건, 사건, 개념 등 여러 개의 속성을 지닌 명사를 의미한다. 엔티티는 서비스 요구 사항에 맞춰 속성이 정해진다. 만약 주소라는 ..

위상 정렬 위상 정렬은 정렬 알고리즘의 일종이다. 순서가 정해져 있는 작업을 차례대로 수정할 때 사용하는 알고리즘이다. 예시로는 선수 과목을 고려한 학습 순서 설정이 있다. 예를 들어 자료구조, 알고리즘, 고급 알고리즘이 있다. 그리고 (알고리즘의 선수 과목은 자료구조), (고급 알고리즘의 선수 과목은 알고리즘)이면 자료구조 -> 알고리즘 -> 고급 알고리즘으로 수업을 들어야한다. 위상 정렬은 먼저 진입차수를 알아야 하는데, 진입차수느 특정 노드로 들어오는 간선의 개수를 의미한다. 잔입 차수가 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]..