인기 글
-
3. 알고리즘 공부
[248] 비트마스크 + 동적 프로그래밍(DP)
1. 비트마스크 비트마스크(BitMask)는 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법을 말합니다. 이진수는 0 또는 1을 이용하므로 하나의 비트(bit)가 표현할 수 있는 경우는 두 가지입니다. 보통 어떤 비트가 1이면 "켜져 있다"라고 말하며, 0이면 "꺼져 있다"라고 말합니다. https://ko.wikipedia.org/wiki/마스크_(컴퓨팅) 마스크 (컴퓨팅) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 마스크(mask) 또는 비트마스크(bitmask)는 특히 비트 필드에서 비트 연산에 사용되는 데이터이다. 마스크를 사용하면 바이트, 니블, 워드 등의 다 ko.wikipedia.org 가. 비트 크기 ..
-
3. 알고리즘 공부
[463] 이분 매칭 알고리즘 과정 살펴보기(파이썬 코드)
1. 입력 정보왼쪽 정점(a그룹)의 개수 N, 오른쪽 정점(b그룹)의 개수 M다음 N개의 줄에 왼쪽 정점에 연결된 간선의 개수와 오른쪽 정점의 정보5 52 1 33 1 2 42 1 22 1 21 3N, M = map(int, input().split()) 2. 필요한 자료구조 살펴보기가. 각 왼쪽 정점에 연결되어 있는 오른쪽 정점들: b_list나. 왼쪽 정점의 방문 기록: visited다. 오른쪽 정점에 짝지어진 왼쪽 정점: b_matchb_list =[[] for _ in range(N+1)]for i in range(1, N+1): b_list[i].extend([*map(int, input().split())][1:])visited = [False] * (N+1)b_match = [-1] *..
-
3. 알고리즘 공부
[473] 다각형 내부의 점 판정법
1. 임의의 점이 다각형 내부에 있는지 판정하는 방법단순한 다각형과 외부의 점을 생각해봅시다.외부의 점에서 반직선을 그리면 다각형과 만나는 점의 개수가 0개 아니면 2개입니다.만약 다각형 내부에 점이 있다면 어떨까요?점에서 반직선을 그리면 다각형과 만나는 점의 개수가 1개입니다.오목 다각형과 같이 복잡한 다각형에서는 어떨까요?외부의 점은 0개 또는 짝수 개의 교점이 생깁니다.내부의 점은 홀수 개의 교점이 생깁니다.특정 점에서 반직선을 그렸을 때, 다각형과의 교점의 개수가 홀수 개이면 내부에 있는 점으로 판정할 수 있습니다.2. 반직선과 선분의 교차 여부 판정이제 특정 점에서 그린 반직선과, 다각형의 모든 선분이 교차하는지 확인하여 교점의 개수를 세면 됩니다.반직선과 선분의 교차 여부는 어떻게 판정할 수 ..
-
2. 정보영재교육 수업 자료
[436] 피보나치 수열을 구하는 여러 가지 방법(파이썬 코드)
1. 피보나치 수열?다음 문제들을 살펴보고 공통점을 생각해봅시다. 한번에 한 칸 또는 두 칸의 계단을 올라갈 수 있습니다.이 때, n칸을 올라가는 경우의 수는 몇 가지일까요? n개의 육각형이 두 줄로 그림과 같이 배치되어 있습니다.인접한 칸으로 이동이 가능하고, 현재 칸보다 숫자가 더 큰 칸으로 이동할 수 있습니다.1에서 n까지 이동하는 경우의 수는 몇 가지일까요? 첫번째 달에는 어린 암수 토끼 한 쌍이 있습니다.어린 암수 토끼 한 쌍은 한 달이 지나면 다 큰 암수 토끼 한 쌍이 됩니다.다 큰 암수 토끼 한 쌍은 한 달이 지나면 어린 암수 토끼 한 쌍을 낳습니다.n번째 달에는 토끼가 몇 쌍일까요? 문제는 모두 다르지만, 모든 문제의 공통점은 n번째의 수가 (n-1)번째와 (n-2)번째를 더한 수가 된다는..
-
3. 알고리즘 공부
[462] 이분 매칭 알고리즘(파이썬 코드)
위와 같은 이분 그래프가 있을 때 이분 매칭을 구해봅시다. 1. 종만북 참고 소스코드종만북 코드는 C언어이므로 파이썬 코드로 옮기면 다음과 같습니다.n, m = 5, 5adj = [ [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 1], ]a_match, b_match = [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]def dfs(a): if visited[a]: return False visited[a] = True for b in range(m): if adj[a][b]: if b_match[b]..
-
3. 알고리즘 공부
[443] 순열, 조합, 중복순열, 중복조합 구현하기(파이썬 코드) - itertools 없이
1. 순열arr = [1, 2, 3]used = [False] * len(arr)def perm(arr, r): for i in range(len(arr)): if not used[i]: used[i] = True if r == 1: yield [arr[i]] else: for nxt in perm(arr, r-1): yield [arr[i]] + nxt used[i] = False print(*perm(arr, 3), sep="\n")# [1, 2, 3]# [1, 3, 2]# [2, 1, 3]# [2,..
