본문 바로가기
반응형

알고리즘

[Python] 2. 파이썬의 기본 자료형(4) - 딕셔너리(Dictionary) & 집합(Set) [목차] 1. 딕셔너리(Dictionary) 만들기 2. 딕셔너리 사용하기 3. 집합(Set) 만들기 4. 집합 사용하기 1. 딕셔너리(Dictionary) 만들기 먼저 딕셔너리(Dictionary)란 각각의 키(key) 값마다 하나의 값이 대응된 쌍들을 모아놓은 자료형이다. 의미 그대로 사전에서 어떤 단어의 뜻을 찾기 위해서 해당 단어만 찾으면 되듯이 특정 값을 찾기 위해서는 대응된 key값으로 바로 찾을 수 있다는 장점이 있다. 리스트는 대괄호, 튜플은 소괄호를 이용했다면 딕셔너리는 중괄호 '{ }' 를 이용해서 생성한다. 다음은 기본적인 딕셔너리의 형태이다. {key1: value1, key2: value2, key3: value3 ...} 이처럼 key값과 value값을 콜론(:)으로 묶어서 저장..
[Python] 2. 파이썬의 기본 자료형(3) - 리스트(List) & 튜플(Tuple) 파이썬의 리스트는 전반적으로 문자열(String)과 유사한 부분이 많다. 겹치는 부분은 비교적 간단하게 설명하므로 문자열(String) 게시글(rebro.kr/123)과 비교해서 본다면 도움이 될 것 같다. [목차] 1. 리스트 생성, 연산자 2. 리스트의 인덱싱과 슬라이싱 3. 리스트의 수정, 변경, 삭제 4. 리스트 관련 함수 5. 튜플 (Tuple) 1. 리스트 생성, 연산자 파이썬에서 리스트를 생성하는 방법은 대괄호 '[ ]' 로 감싸주고, 리스트의 원소들은 쉼표 ','로 구분해준다. 리스트는 아무 원소를 포함하지 않는 빈 리스트일 수도 있고, 숫자를 원소로 가질 수도 있고 문자열을 원소로 가질 수도 있다. 즉, 어떠한 자료형도 원소로 가능하다. a = [] # 빈 리스트 a = [1,2,3,4]..
[Python] 2. 파이썬의 기본 자료형(2) - 문자열(String) 파이썬에서 문자열을 다루는 방법은 정말 다양하다. 특히 C/C++을 먼저 학습한 사람이라면 더 쉽고 다양한 방식이 많다는 것을 체감할 것이다. [목차] 1. 문자열 만들기 2. 문자열 연산하기 3. 문자열 인덱싱 4. 문자열 슬라이싱 5. 문자열 포매팅 6. 문자열 관련 함수 1. 문자열 만들기 문자열은 ' ' (작은따옴표), " " (큰따옴표), ''' ''' (작은따옴표 3개), """ """ (큰따옴표 3개) 이들을 이용하여 하나의 문자열로 묶을 수 있다. 이렇게 다양한 방법을 제공하는 이유는, 문자열 내에 따옴표가 포함될 수도 있기 때문이다. 예를 들어서 I'm Python을 만들고 싶다면, 문자열 안에 작은따옴표가 있기 때문에 해당 문자열을 작은따옴표로 묶게 되면, 'I'm Python'이 되어..
[Python] 2. 파이썬의 기본 자료형(1) - 숫자 자료형 파이썬에서 기본적으로 제공하는 숫자 자료형으로는 정수, 실수, 복소수, 8/16진수 등이 있다. 1. 정수형 정수형은 말 그대로 정수를 뜻하는 자료형이다. a = 13 a = -1 a = 0 이런 식으로, 우리가 흔히 아는 정수를 그대로 이용해주면 된다. 2. 실수형 실수형은 파이썬에서 소수점이 포함된 숫자를 말한다. 또, 컴퓨터에서 사용하는 지수 표현 방식대로도 표현할 수 있다. a = 2.4 a = -1.5 a = 1.2E10 a = 4.5e-10 위의 두 줄은 일반적으로 사용하는 실수의 소수점 표현 방식이다. 밑의 두 줄은 컴퓨터에서 사용하는 지수 표현 방식인데, E10은 $10^{10}$을 의미한다. 따라서, 1.2E10은 $1.2 × 10^{10}$을 의미하는 것이다. E와 e 둘 중 어느 것을..
[Codeforces] Round #559 (Div. 2) A ~ E 풀이 21.03.05 23:35 virtual 참가 / performance = 2391 A. A pile of stones (*800) +가 주어질 때는 돌이 1개 증가하고, -가 주어질 때는 돌이 1개 감소한다. 처음에 보유할 수 있는 돌은 임의로 정할 수 있고, 중간에 돌이 0개일 때 -가 들어오면 안 될 때, 최종적으로 가능한 최소 돌의 개수를 구하는 문제이다. 처음의 돌 수를 직접 정할 수 있으므로, 단순하게 -가 들어오는 경우, 만약 현재 돌이 0개이면 그대로 유지시켜주면 된다. 이 과정이 결국 처음의 돌 수를 1개 증가시키는 과정과 동일하다. [소스 코드] #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin..
[Codeforces] Educational Round 102 A ~ E 풀이 2달 만에 본계로 참가했다. 부계로 계속 못 올라가는 게 현타 와서 마음을 다 비우고 본계로 했는데 약간 올랐다... 한동안 1800 퍼포 이상을 찍어본적이 없었는데 아이디에 적응하는 건가....? CF 1473A. Replacing Elements 배열의 어떤 원소를 다른 두 원소의 합으로 바꿀 수 있다. 이때, 배열의 모든 원소를 d 이하로 만들 수 있는지에 대한 문제이다. 기본적으로 주어지는 모든 원소가 d 이하이면 아무런 작업을 하지 않아도 된다. 만약 d보다 큰 원소가 하나 이상 존재한다면, 해당 원소를 바꿔주는 최적의 경우는 배열의 모든 원소 중 제일 작은 값 2개를 골라 바꿔주는 경우이므로, 배열을 오름차순으로 정렬하여 A[1] + A[2]가 d이하이면 YES이다. [소스코드] #includ..
PS를 위한 정수론 - (4) 이항 계수 (nCr mod P) 구하는 다양한 방법 이항 계수 $_{n}C_r$을 소수 $p$로 나눈 나머지를 빠르게 구하는 다양한 방법들을 알아보자. 기본적으로 특정 $n$과 $r$에 대해서 이항 계수 $_{n}C_r$을 구하는 시간은 $O(1)$이 되어야 할 때, 즉, 많은 쿼리가 들어와도 문제가 없는 경우를 고려한다. 지금부터 소개하는 방법들의 시간복잡도는 전처리하는데 필요한 시간을 의미한다. 너무 작은 $n$과 $r$에 대해서 직접 분자와 분모를 모두 곱하는 경우는 생략한다. 1. $O(n^2)$ www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 파스칼의 삼각형을 이용하는 ..
PS를 위한 정수론 - (3) 페르마의 소정리와 활용 (이항 계수, 밀러-라빈) [목차] 1. 페르마의 소정리 2. 오일러 정리 3. 활용 1) 이항 계수 nCr 빠르게 구하기 4. 활용 2) 밀러-라빈(Miller-Rabin) 소수 판별법 1. 페르마의 소정리 (Fermat's little theorem) 페르마의 소정리는 다음과 같다. "소수 $p$와 정수 $a$에 대해서 $a^p \equiv a \; (mod\;p)$" 만약 $a$와 $p$가 서로소이면 $a^{p-1} \equiv 1 \; (mod \;p)$ 를 만족한다. 짧지만 생각보다 PS에서 되게 많이 사용되므로 꼭 알아두는 것이 좋다. 증명 과정은 수학적 귀납법을 이용한다. (이 블로그를 참고했다) 먼저, $a$가 $p$ 이상이면, modular의 성질에 의해서 $p$로 나눈 나머지로 계산해도 동일하므로, $0 \leq..

티스토리툴바