안토니 블로그 안토니 블로그

Union-find? 그래프 알고리즘의 일종으로 상호 배타적 집합(Disjoint Set)이라고도 합니다. 즉 서로 공통되는 원소가 없는 집합이 없게 만들어야 한다는 것이죠. 이를 위해 두가지의 연산이 존재합니다. - Find: X가 속한 대표값을 반환합니다. (트리 형태로 구현하기에 여기선 root 노드를 의미) - Union: X가 속한 집합과 Y가 속한 집합을 합칩니다. 즉 합집합 연산을 의미합니다. 기본 구성 var parent = Array(0...100) func find(_ num: Int) -> Int { if parent[num] == num { return num } return find(parent[num]) } func union(_ a: Int, _ b: Int) { let a ..

1. 간선이 듬성듬성하다 연결리스트를 활용 인접리스트 : O(V+ E) 2. 간선이 빽빽하다 이차원리스트 활용 인접행렬 : O(V^2)

알고리즘 문제를 풀때 어떤 자료구조를 사용해야하는가? python snake = [] snake.append((1,3)) snake.append((1,2)) snake.append((1,1)) (1,3) (1,2) (1,1) => (1,4) (1,3) (1,2) 1. 단일 객체에 대한 표현 - Point : 간단하기 때문에 굳이 자료구조를 사용하지 않음. 2. 단일 객체에 대한 표현 - Array 1. 탐색 : O(N) 2. 삽입 : O(N) but 맨 뒤 삽입은 O(1) 3. 삭제 : O(N) but 맨 뒤 삭제는 O(1) 4. 값 조회 : O(1) - 머리 추가 : O(N) - 뱀 옮기기 : O(N) 3. 단일 객체에 대한 표현 - LinkedList 참고로 파이썬에선 링크드리스트가 없어 deque로..

파이썬에서 2차원 이상의 리스트를 초기화할땐 list = [[0]*n for _ in range(n)] 와 같이 해야한다. list = [[0]*n]*n 처럼 초기화를 할 경우 n개의 [0]*n이 모두 같은 객체를 가리키기 때문이다. ex) n = 4 # case 1 list_1 = [[0]*n]*n print(list_1) list_1[2][3] += 1 print(list_1) """ [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] [[0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 1]] """ # case 2 list_2 = [[0]*n for _ in range(n)] print(list_2) lis..

# case 1 - for문과 append를 이용해 만든 리스트 numbers = [] for i in range(1,11): numbers.append(i) print(numbers) output [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # case 2 - list comprehension을 이용해 만든 리스트 numbers2 = [i for i in range(1,11)] print(numbers2) output [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # case 3 - 조건문이 추가된 list comprehension numbers3 = [i for i in range(1,11) if i%2 == 1] print(numbers3) output [1, 3, 5, 7,..

■ 알고리즘의 분석 □ 정확성 분석: 모든 입력 사례에 대해서 정확한 해답을 찾는다는 것을 증명 □ 효율성 분석: 입력 크기가 커지는 정도에 따라 성능의 변화량을 증명 - 시간 복잡도: 시간을 기준으로 알고리즘의 효율성 분석 - 공간 복잡도: 공간을 기준으로 알고리즘의 효율성 분석 ■ 알고리즘의 성능 분석 □ 퍼포먼스 측정: 실행 시간을 직접 측정하거나 실행 명령의 숫자 세기 - 컴퓨터의 성능이나 프로그래밍 언어에 따라 달라짐 □ 복잡도 분석: 컴퓨터나 프로그래밍 언어와 무관하게 성능 분석 - 입력 크기에 따른 단위 연산의 실행 횟수 세기 ■ 복잡도 분석 □ 입력 크기: 문제가 가진 파라미터, 즉, 입력 사례의 크기 □ 단위 연산: 알고리즘 실행의 기본이 되는 명령어들의 집합 ■ 알고리즘의 시간 비교 □..

알고리즘 공부를 하다보니 예전 자료구조 내용도 다까먹었고 기본적인 부분이 부족한 것 같아 인강을 보기 시작했어요 백준 인강 들으려고 했었는데 무료강의가 찾아보니 있더라구요 https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B8%B0%EC%B4%88#curriculum [무료] 파이썬으로 배우는 알고리즘 기초 - 인프런 | 강의 Pseudo 코드로 설명하는 알고리즘 강의에 지치셨나요? 실행 가능한 Python 소스 코드로 알고리즘의 기초를 다져봅시다!, 알고리즘 학습, 파이썬 코딩으로 장벽을 낮춰보세요! 파이썬으로 배우는 www.inflearn.com 무료라고 하니 한번 들어보..