야뱝이

비트마스킹 비트마스킹의 장점 간결 빠름 메모리 True False True 를 101 로 표기하는 것.. 비트 연산 AND & 둘다 1이면 1 bin(0b1010 & 0b1101) >>> 0b1010 OR | 둘 중 하나라도 1이면 1 bin(0b1010 & 0b1101) >>> 0b1111 XOR ^ 둘이 서로 다르면 1 bin(0b1010 & 0b1101) >>> 0b0111 SHIFT >> > 2) >>> 0b11 bin(0b1010 >> 3) >>> 0b1 bin(0b1100 >> 0b110000 #중요 NOT ~ -(x+1) 을 반환 bin(~0b1010) # -(0b1010 + 1) # -(0b1011) >>> -0b1011 문제 풀때 사용하는 것들 #중요 bin(1 >> 0b10 bin(1 ..

트리의 지름 (가장 먼 곳의 가장 먼 곳) (백준 1167 파이썬) https://www.acmicpc.net/problem/1167 문제의 이해는 쉽지만 어떻게 풀어야 할지.. 방법을 떠올리기 어려웠다. (나만 그런 듯) 지하철을 떠올리면 이해하기 쉽다. 3호선과 7호선만 생각해보자. 그림을 보면 이해가 갈 것이다. 녹번역(임의의 역)에서 출발하여 가장 먼 역까지 간다. 곧, 녹번역에서부터 가장 거리가 먼 종점까지 갔다는 것이다. 그 종점에서 가장 거리가 먼 또 다른 종점까지 간다. 두 종점의 거리가 가장 먼 거리가 된다. 실제 문제로 돌아와서, 트리의 한 노드에서 가장 거리가 먼 노드까지 도달하는 방법을 생각해보자 DFS혹은 BFS를 이용할 수 있겠다. 뭘 이용하던 완전탐색만 하면 된다. 또는 다익스..

활동 선택, 스케쥴링 문제 (그리디) 쉬운 유형의 문제로 코딩테스트에서 자주 본 적 있다. 백준 1931 참고 https://www.acmicpc.net/problem/1931 # 회의 시작 시간, 회의 끝나는 시간 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 # 여러 회의 시간이 주어진다. # 최대한 많은 회의를 하려면 ? 그림을 보면 해당 예제는 최대 4번의 회의를 할 수 있다. 그리디 알고리즘은 매 순간 마다의 최적의 선택을 하는 알고리즘 설계법이다. 하지만 매 순간 최적의 선택을 한다고 해서, 최종적으로 결과가 최적을 보장하지는 않기에, 문제를 잘 읽어 보아야 한다. 즉, 지금 현재 가장 좋아 보이는 것을 계속 선택해도 최적의 해가 되는가를 검토해봐야 ..

탐색과정에서 시간이 오래걸릴 때 예를 들어서 포켓몬 도감을 구현한다고 할때, pokemons = [Bulbasaur, Ivysaur, Venusaur, Charmander, Charmeleon] # 첫 번째 포켓몬부터 1번이라고 하자 사전 번호를 이용해서 포켓몬을 찾아야하는 경우가 있고, ex) 3번 포켓몬 이름은? ----- Venusaur 포켓몬 이름을 이용해서 사전 번호를 알아내야 하는 경우가 있다. ex) Charmander 의 사전 번호는 ? ----- 4번 이럴 때는 리스트와 딕셔너리를 둘다 생성해서 이용해보자. pokemons_dict['포켓몬이름'] = '사전번호' 가 되도록 하면 O(1) 만에 접근 가능하다. 두개의 리스트를 비교할 때도 딕셔너리를 자주 활용한..

파이썬 예외 처리 기본 숫자와 문자열이 랜덤하게 입력될 때 어떻게 구별할까 # 입력 25 Raichu 3 Pidgey Kakuna 보통 입력받을 때는 문자열로 받아진다. int("Raichu") 무작정 이런식으로 해버리면 에러가 난다. 입력이 정수형으로 타입변환이 가능한지 어떻게 알아볼수 있을까? try, except 구문을 사용해보자.. try : except : # 오류의 종류에 상관없이 오류 발생 시 except 블록 수행 for n in range(5) : a = sys.stdin.readline().rstrip() try : b = int(a) except : b = a print(b, type(b)) >>> # 출력 25 Raichu 3 Pidgey Kakuna 예외처리에 대해 더 배우고 싶다..

파이썬의 연산 시간에 대하여 파이썬은 1초에 2000만 = 20,000,000 번 연산이 가능하다고 생각해두면 좋다. 따라서 시간제한이 1초, n = 100,000 (10만) 이라고 할 때 O(N^2) 으로 알고리즘을 짜게 되면 10,000,000,000 = 100억 번의 연산이 필요하므로, 시간초과가 나게 된다. 이 경우엔 O(NlogN) 으로 알고리즘을 짜야 1,600,000 번의 연산으로 수행 가능하다. (log 100,000 = 약 16) 일단 이것만 꼭 알아두자 1초에 2000만! -dnlxo

DP와 메모이제이션 기본 피보나치 수열 함수 구현을 통해 DP와 메모이제이션에 대해 알아보자 피보나치 수열 = 0, 1, 1, 2, 3, 5 ,8, 13, 21, 34, .... DP란 Dynamic Programmig의 약자 동적계획법 문제를 해결하기 위한 접근 방식 중 하나이다. dp의 핵심 재귀적, 귀납적, 분할적으로 문제 해결.. 작은 문제는 해결되어 있다고 생각하고 큰 문제를 해결하는 방법! 피보나치 수열을 구하는 방법으로 생각해보면 F(n) = F(n-1) + F(n-2) (n >= 2) F(n-1) 와 F(n-2) 가 해결되어 있다고 생각하고 큰 문제를 해결한다! 반복적이고 불필요한 계산을 줄이기 메모이제이션 이라는 방법을 사용해서 줄이는 방법이 있다. 이미 했던 계산은 따로 저장해둔 뒤, ..

최대공약수와 최소공배수 b 와 a - bq 가 서로소인 것의 증명은 간단하다. b 와 a - bq 가 서로소가 아니라고(공약수가 존재한다) 가정하면 모순이 쉽게 찾아진다. 실제 예를 들어보자 gcd(18,12) = gcd(12,6) # 18 = 12*1 + 6 gcd(12,6) = gcd(6,0) # 12 = 6*2 + 0 여기서 나머지가 0 이 된다는 소리는, 12가 6으로 정확히 나누어 떨어진다는 뜻이며, 즉, 6이 바로 12와 6의 최대공약수가 된다. 서로소의 최대공약수를 구할 때는 어떻게 되는지 살펴보자 # 서로소 일 때 gcd(18,7) = gcd(7,4) gcd(7,4) = gcd(4,3) gcd(4,3) = gcd(3,1) gcd(3,1) # 3 = 1*3 + 0 예상대로 1이 최대공약수가 ..

소수 판별 소수(Prime Number)를 판별하는 방법 중 한 가지 : 에라토스테네스의 체 2부터 시작하는 순차적인 자연수의 집합이 있다고 하자. ex) 2, 3, 4, 5, 6, ..., 120 자기자신을 제외한 2의 배수를 모두 지운다. 남은 수 중 다음 수는 3 자기자신을 제외한 3의 배수를 모두 지운다. 남은 수 중 다음 수는 5 자기자신을 제외한 5의 배수를 모두 지운다. 이 과정을 반복하면 해당 집합에서 소수만 남는다. 중요한 점 이 과정에서 120^(0.5) < 11 이므로 11보다 작은 수의 배수들 까지만 지우면 된다. (13의 배수, 17의 배수 등 지울 필요 없음...) 왜 ???? 예를 들어서 7의 배수를 지우고 있다고 하자7*3 = 21 ... 7*16 = 112 7*17 = 11..

백준 입력 받기 여러줄 한번에 입력받기 (몇 줄인지 모름) 1 3 3 5 4 2 3 5 while True : try : a, b = map(int, sys.stdin.readline().split()) except : break 몇 줄인지 모르는데 마지막 줄 조건 주어짐 1 3 3 5 4 2 3 5 3 1 0 0 # 마지막줄은 0 0 while True : try : a, b = map(int, sys.stdin.readline().split()) if a, b == 0, 0 : break except : break -dnlxo