문제 : https://www.acmicpc.net/problem/1197 import sysinput = sys.stdin.readlineV, E = map(int, input().split())Edges = []for _ in range(E): A, B, C = map(int, input().split()) Edges.append([A, B, C])def third_val(e): return(e[2])Edges.sort(key = third_val)# 각 정점이 들어있는 유니온을 기록함union = [i for i in range(V)]def kruskal(edge): s = union[edge[0]-1] e = union[edge[1]-1] if s == e: ..
그래프이미지 출처 : https://elisha0103.tistory.com/24 프로그래밍에서 그래프는 인접행렬, 인접리스트 방식으로 표현된다.인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식메모리를 더 많이 쓰는 대신, 두 정점이 연결되었는지 확인하는 속도가 빠르다.인접리스트: 리스트로 그래프의 연결 관계를 표현하는 방식메모리를 덜 쓰는 대신에 두 정점의 연결 여부를 확인하는 데 시간이 걸린다.간선의 개수가 많다면 인접 행렬이 유리하고, 간선의 개수가 적다면 인접 리스트가 유리하다. 그래프의 종류무방향 그래프(Undirected Graph):정점 간의 연결이 방향성을 가지지 않는 그래프입방향 그래프(Directed Graph):정점 간의 연결이 방향성을 가지는 그래프가중치 그래프(Weigh..
트리의 구조와 관련 용어트리 : 노드(node) + 가지(edge)루트 : 맨 위에 있는 노드리프 : 맨 아래에 있는 노드. [ = 단말 노드(terminal node), 외부 노드(external node) ]비단말 노드 : 리프를 제외한 노드. [ = 내부 노드(internal node) ]형제 : 부모가 같은 노드조상 : 어떤 노드에서 위쪽으로 가지를 따라가면 만나는 모든 노드자손 : 어떤 노드에서 아래쪽으로 가지를 따라가면 만나는 모든 노드레벨 : 루트에서 얼마나 멀리 떨어져 있는지 (루트는 0)차수 : 각 노드가 갖는 자식의 수높이 : 루트에서 가장 멀리 있는 리프까지의 거리 순서 트리와 무순서 트리순서 트리(ordered tree): 형제 노드의 순서 관계가 있음무순서 트리(unordered ..
해시법해시법 : '데이터를 저장할 위치' (= 인덱스) 를 간단한 연산으로 구하는 것을 말한다.키5614202934375169해시값 (키 % 13)56173811124 여기서 각각의 키를 13으로 나눈 값이 인덱스가 된다.키를 해시값으로 변환하는 과정을 해시 함수라 하고,해시 테이블에서 만들어진 인덱스를 버킷이라고 한다.해시 테이블을 크게 만들면 충돌 발생 없지만 메모리 낭비 + 느리다.해시 테이블 작게 만들면 충돌 발생하지만 검색, 추가, 삭제할 때 빠르다. 해시 충돌위에 있는 해시 테이블에 18 넣으면 18 % 13 == 5 이므로 인덱스가 5가 되어야 한다.하지만 인덱스 5는 자리가 이미 차 있다.이렇게 인덱스가 중복되는 것을 해시 충돌이라 한다. 해시충돌 대처법체인법 : 해시값이 같은 원소를 연결..
문제 : https://www.acmicpc.net/problem/11049 A, B, C = map(int, input().split())R = A % Cdef remainder(A, B, C): R = A % C if B == 1: return R elif B % 2 == 0: # 지수가 짝수면 R = remainder(R*R, B//2, C) return R else: R = remainder(R*R,B//2,C) * R return Rprint(remainder(A,B,C)%C) A를 C로 나눈 나머지가 R이라 하면,A^B % C == R^B % C 이다. A = (몫*C) + R 이므로,{(몫*C) + R} * ..
1. 패키지 관리자Ubuntu, Debian : APTFedora, Red Hat : YUM, DNF 각 리눅스 배포판의 기본 패키지 관리 시스템을 사용하여 프로그램을 설치할 수 있다.최적화, 안정성, 보안성이 좋지만, 특정 배포판에 종속적이고 최신 버전 제공이 늦어질 수 있다. 2. Flatpak리눅스 배포판에 관계없이 프로그램을 배포할 수 있는 시스템이다.Flatpak으로 패키지 만들어서 배포하면 모든 리눅스 배포판에서 동일하게 설치하고 실행될 수 있다.모든 필요한 라이브러리와 의존성을 포함하여 프로그램을 샌드박스 환경에서 실행한다.샌드박스 환경에서 실행돼서 보안성이 높다. 패키지 크기가 좀 더 크다. 3. SnapSnap은 Canonical(우분투의 개발 회사)에서 개발한, 리눅스 배포판에 독립적인..
1. 시간 복잡도 : 얼마나 빨리 작동되는가?🔷 느린 알고리즘 : O(n^2)◻️ 작은 데이터 세트나 거의 정렬된 데이터 : 버블 정렬, 삽입 정렬버블 정렬 : 정렬될때까지 순회하면서 2개씩 비교 후 순서 변경삽입 정렬 : 맨 앞에 크기 순으로 정렬된 영역 하나씩 키우기◻️ 메모리가 부족한 환경 : 선택 정렬선택 정렬 : 최솟값 찾고 앞으로 보내는거 반복 🔷 빠른 알고리즘 : O(n log n)◻️ 대부분의 일반적인 상황 : 퀵 정렬퀵 정렬 : 피벗 하나 고르고 왼쪽 오른쪽으로 보내버리는거 반복◻️ 안정성이 중요한 대규모 데이터 세트 : 병합 정렬병합 정렬 : 작게 쪼갠 다음 하나씩 합치는거 반복안정성 : 동일한 키를 가진 요소들이 정렬 전의 순서를 유지하는 것예를 들어, 학생들을 성적 순으로 정렬할..
버블 정렬이란?처음부터 끝까지 숫자 2개씩 비교하는거 반복하다보면 정렬되는 알고리즘 버블 정렬 구현 (기본)for i in range(n-1): for j in range(n-1, i, -1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] { 원소 수가 n인 배열에서 n-1번 비교, 정렬해주면 가장 작은 원소가 맨 앞으로 이동한다. } 완벽하게 전부 정렬되려면 패스를 n-1번 해야 한다. 버블 정렬 구현 (최적화 1)for i in range(n-1): exchng = False for j in range(n-1, i, -1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] ..
일반적인 소수 판별에는 '2. 2부터 n 제곱근까지 숫자들로만 나눠서 확인' 정도만 쓴다.범위 내의 소수를 모두 구하는 경우에는 '3. 에라토스테네스의 체'가 효율적이다. 판별 알고리즘1. 하나씩 전부 나눠보기2부터 목표 숫자-1까지 전부 나눠보고 안 나눠지면 소수def is_prime(n): if n 2. 2부터 n 제곱근까지 숫자들로만 나눠서 확인16을 예로 들면, 제곱근인 4까지만 확인해보면 4 초과부터는 확인할 필요 없다.import mathdef is_prime(n): if n 3. 에라토스테네스의 체아래에서 훑는데 각 수의 배수도 날림.한 개의 소수를 구할 때 적합한 방법이라기보단범위 내의 모든 소수를 구할 때 적합.n=1000a = [False,False] + [True]*(..
쿠키쿠키 : 정보가 적힌 텍스트김씨가 '빨간색'을 좋아한다고 서버에 말함'빨간색을 좋아한다'는 정보를 담은 쿠키를 서버에서 보내면 김씨 클라이언트에 저장됨다음부터 김씨는 서버에 쿠키만 보냄다음부터 김씨는 빨간색을 좋아한다고 또 알릴 필요 없이 빨간색 웹사이트 볼 수 있음단점 : 비밀번호 같은거 적어두면 탈취되면 큰일남 (= 보안 낮음) 세션김씨가 서버에 들어오면 서버가 김씨만을 위한 세션 ID(=daf2jkcg)가 적힌 쿠키를 보내줌다음부터 김씨는 서버에 쿠키만 보냄서버는 쿠키를 받아서 그 안에 있는 세션 ID가 세션 저장소에 있는지 확인김씨는 이제 비밀번호, 카드번호같은 거 또 입력할 필요 없이 서버에 저장된 정보 쓰면 됨다른 사람이 김씨라고 위장하고 서버에 들어왔음김씨는 그것을 알아차림서버에 요청해서..
