전체보기 (460) 썸네일형 리스트형 [420] 파이썬 큐(Queue) 구현하기 1. 큐(Queue)큐는 자료구조 중 하나로 선입선출(First In First Out, FIFO) 하는 추상적인 개념을 말합니다.보통 큐를 연결리스트를 이용하여 구현합니다.https://ko.wikipedia.org/wiki/큐_(자료_구조) 큐 (자료 구조) - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬ko.wikipedia.org 2. 큐 구현하기가. 노드 class 만들기연결리스트를 사용하기 때문에 먼저 노드 class를 만듭니다.노드 객체는 값을 저장하는 data와 다음 연결되는 노드를 저.. [419] 제곱수의 합 1. 소수(prime number)의 기초적인 상식소수(prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 2를 제외한 모든 소수는 2로 나누어 떨어지지 않기 때문에 홀수입니다.2보다 큰 임의의 소수를 p라고 했을 때, p ≡ 1(mod 2)(2에 대한 나머지가 1)입니다. 그리고 홀수인 소수(2를 제외한 소수)는 4로 나누어 떨어지지 않습니다.따라서 홀수인 소수 p ≡ 1(mod 4)(4에 대한 나머지가 1) 또는 p ≡ 3(mod 4)(4에 대한 나머지가 3)입니다.2. 페르마의 두 제곱수 정리홀수인 소수(2를 제외한 소수)가 두 개의 제곱수의 합이 될 필요충분조건이 p ≡ 1(mod 4)라는 정리입니다.반대로 말하면 홀수인 임의의 소수가 4로 나누었을 때 나.. [418] 그림으로 알아보는 좌표 압축(파이썬 코드 포함) 1. 좌표 압축주어진 수의 범위가 매우 클 때, 수의 값을 수의 순서(대소관계)로 치환하여 전체 범위를 줄이는 테크닉을 말합니다.좌표 압축만 가지고 문제를 해결하기 보다는 복잡한 문제를 단순하게 만드는 데 많이 활용됩니다.주로 세그먼트 트리 자료구조와 스위핑 알고리즘과 함께 많이 사용됩니다.https://wikidocs.net/214469 10. 좌표 압축## 좌표 압축 좌표 압축은 알고리즘이라기 보다 테크닉에 가깝습니다. 좌표 압축을 통해 어떤 문제를 해결하기 보다는 복잡한 문제를 해결하는데 도움을 주기 때문입니다. 여러 좌표…wikidocs.net 좌표 압축 과정을 살펴봅시다.5, 2, 10, 4, 2 이 다섯 개의 숫자를 좌표 압축하는 과정을 그림을 보며 알아보겠습니다. 가. 인덱스 값(순서 값).. [417] 세그먼트 트리 파이썬 코드 1. 세그먼트 트리 개념이번 글에서는 세그먼트 트리를 파이썬 코드로 어떻게 구현할 수 있는지 알아봅시다.세그먼트 트리의 개념이 궁금하신 분은 지난 글을 참고해주세요.https://kimwooil.tistory.com/416 [416] 세그먼트 트리의 개념1. 세그먼트 트리영어 단어 segment는 분할, 구간, 분절 등의 뜻을 지니고 있습니다.알고리즘에서 세그먼트 트리는 여러 값을 가지는 리스트의 특정 구간의 정보를 이진 트리 형태로 관리하는 자료kimwooil.tistory.com 지난 글에서 예시로 다루었던 1~10까지의 누적합을 담는 세그먼트 트리를 파이썬 코드로 구현해보겠습니다.트리를 다시 보면, 노드들이 다음과 같은 범위의 정보를 가집니다.해당 범위의 누적합(구간합)은 다음과 같이 그려집니다.2.. [416] 세그먼트 트리의 개념 1. 세그먼트 트리영어 단어 segment는 분할, 구간, 분절 등의 뜻을 지니고 있습니다.알고리즘에서 세그먼트 트리는 여러 값을 가지는 리스트의 특정 구간의 정보를 이진 트리 형태로 관리하는 자료구조를 말합니다. 2. 세그먼트 트리가 만들어지는 과정예를 들어, 1 ~ 10까지 10개의 숫자(원소)의 합을 세그먼트 트리로 만들면 다음과 같습니다.가장 먼저 루트는 전체 범위의 정보를 가집니다.그 정보가 숫자들의 합이므로 1~10까지의 합이 됩니다.다만, 아직 그 정보의 값은 정해지지 않습니다.왜냐하면 재귀적으로 자식을 만들고, 리프가 완성되었을 때 반환값을 통해 값이 정해지기 때문입니다.이제 루트의 자식을 만듭니다.이진 트리이므로 자식은 둘이며 범위는 반으로 나누어 줍니다.그럼 자식은 각각 1~5, 6~.. [415] 타잔의 SCC(강한 연결 요소) 알고리즘(파이썬 코드) 1. 강한 연결 요소 개념이번 글에서는 파이썬으로 타잔의 SCC 알고리즘을 구현한 코드를 살펴보겠습니다.강한 연결 요소에 대해 알고 싶으시다면 지난 글을 참고하세요.https://kimwooil.tistory.com/380 [380] 강한 연결 요소(SCC)와 타잔의 SCC 알고리즘(Tarjan's SCC algorithm)1. 강한 연결 요소(SCC; Strongly Connected Components) 유향 그래프(Directed Graph)에서 모든 정점이 다른 모든 정점에 도달할 수 있는 경우, 강하게 연결되었다고 합니다. 다시 말하면, 임의의 두 정점 사이kimwooil.tistory.com2. 타잔의 SCC 알고리즘 파이썬 코드위 이미지와 같이 그래프의 강한 연결 요소를 찾아보겠습니다. 가... [414] 2-SAT 문제(개념만, 코드 없음) 1. SAT(충족 가능성 문제)다음과 같은 논리식이 있다고 하면(∧는 and 연산입니다.),논리식 = 변수1 ∧ 변수2 ∧ 변수3변수1, 2, 3이 어떤 값을 가지냐에 따라 논리식은 참이 될 수도 있지만, 다음과 같은 논리식에서는논리식 = 변수1 ∧ not 변수1만약 변수1이 참이면 not 변수1은 거짓이 되기 때문에 위 논리식은 절대 참이 될 수 없습니다. 이렇게 참/거짓을 가지는 변수들로 이루어진 논리식이 주어졌을 때, 그 논리식이 참이 되는 변수값이 존재하는지 찾는 문제를 충족 가능성 문제(SAT)라고 부릅니다.https://ko.wikipedia.org/wiki/충족_가능성_문제 충족 가능성 문제 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 충족 가능성 문제(充足可能性問題,.. [413] 확률및통계 14차시 연속확률분포2 보호되어 있는 글입니다. 이전 1 ··· 3 4 5 6 7 8 9 ··· 58 다음
