몽상실현개발주의

[종만북] 연결 리스트 / 선형 자료 구조 연결 리스트 배열의 원소들의 순서를 유지하면서 임의의 위치에 원소를 삽입하거나, 임의의 위치에서 원소를 삭제하는것은 시간이 오래 걸리는 작업이다. 해당 위치 뒤에 있는 원소들을 하나씩 뒤칸 혹은 앞칸으로 옮겨야 하기 때문이다. 정확한 수행시간은 삽입이나 삭제 위치에 따라 다르지만, 평균적인 경우 이 작업들에는 원소들의 개수에 선형 비례하는 시간이 소요된다. 이와 같은 문제를 해결하기 위해 고안된 자료구조가 연결 리스트(Linked List) 이다. 연결 리스트는 특정 위치에서의 삽입과 삭제를 상수 시간에 할 수 있게 해 준다. 배열에서는 메모리의 연속된 위치에 각 원소들이 저장되어 있지만, 연결 리스트는 원소들이 메모리 여기저기 흩어져 있고 각 원소들은 이전과 ..

[종만북] 동적 배열 / 선형 자료 구조 동적 배열 배열의 큰 문제중 하나는 배열이 선언 될 때, 지정된 크기 이상의 자료를 넣을수 없는 것. 이와 같은 문제를 해결하기 위해 고안된 것이 자료의 개수가 변함에 따라 크기가 변경되는 동적 배열 (Dynamic Array) 배열을 이용해 만들어 낸 별도의 자료구조 배열의 특성 - 원소들은 메모리의 연속된 위치에 저장됨 - 주어진 위치의 원소를 반환하거나 변경하는 동작을 O(1) 에 완수 동적 배열의 추가 특성 - 배열의 크기를 변경하는 resize() 연산이 가능. 이 동작을 수행하는데는 배열의 크기 N 에 비례하는 시간이 소요 - 주어진 원소를 배열의 맨 끝에 추가함으로써 크기를 1 늘리는 append() 연산을 지원. 이 동작을 수행하는데 상수 시간 소요..

https://www.algospot.com/judge/problem/read/GRADUATION algospot.com :: GRADUATION 졸업 학기 문제 정보 문제 1학년은 노는 게 남는 거란 선배의 말을 철석같이 믿고, 전공 과목은 다 수강철회하고 교양 과목은 다 F 받는 방탕한 1학년을 보냈던 태우는 이제 와서 자신의 행동을 www.algospot.com 풀이 비트마스크를 사용하여 효율적인 해결이 가능한 DP 문제이다. 어렵다!!!! 1. 각 학기별 수강 가능한 과목 확인 2. 수강 가능한 모든 경우 고려, 각 경우에 대한 memorization 3. 졸업이 가능한 조건 시, 최소학기 확인 모든 경우를 고려하면서 최적화를 위해 각 학기별 수강과목 경우에 따라 수강여부를 기록 해야 한다. 하지..

[종만북] 비트마스크 / 자료구조 / Python 파이썬 비트마스크 정수 의 이진수 표현을 자료 구조로 쓰는 기법 비트마스크는 엄밀하게 말해 자료 구조라고 할수는 없지만, 종종 굉장히 유용하게 사용됨. 비트마스크 장점 더 빠른 수행 시간 비트마스크 연산은 0(1)에 구현되는 것이 많기 때문에, 다른 자료 구조를 사용하는 것보다 훨씬 빨리 동작 연산을 굉장히 여러번 수행 해야 할 경우, 작은 최적화로 큰 속도 향상 더 간절한 코드 다양한 집합 연산들을 반복문 없이 한 줄에 쓸 수 있기 때문에 짧은 코드로 작성 더 작은 메모리 사용량 같은 데이터를 더 적은 메모리를 사용해 표현 많은 데이터를 미리 계산해 두어 있으면 프로그램도 속도 향상 캐시 효율 좋음 연관 배열을 배열로 대체 같은 정보를 객체가 아닌 정수..

[종만북] 모듈라 연산 / 정수론 모듈라 연산 (Modular Arithmetic) 모듈라 M 에 도달 하면, 다시 0으로 돌아가는 정수들로 하는 연산 모듈라 연산에서 모든 정수는 M 으로 나눈 나머지로 표현됨 ex) 시계 모듈라 덧셈 두 수의 합의 모듈라 연산은, 두 수의 모듈라 연산 결과의 합과 같다. (a + b) % M = (a' + b') % M a % M = a' , b % M = b' -> (a + b) % M = ? a = Mx + a' , b = My + b' (a + b) = (Mx + a') + (My + b') = M(x+y) + ( a'+b') (a + b) % M = ( M(x+y) + a' + b') % M = (a' + b') % M -> (a + b) % M = (a' + ..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com [종만북] POTION / solution 효율적인 알고리즘 / Python 파이썬 Solution 효율적인 알고리즘 - r_list 들의 약수를 찾아 해결 1. 모든 재료 중 가장 많이 들어간 재료 찾기 -> X = max( p_list[i] / r_list[i] ), 모든 재료는 X 배 이상 들어야가한다. 2. r_list[i] * X 는 항상 정수 ..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com [종만북] POTION / solution 직관적인 알고리즘 / Python 파이썬 Solution 직관적인 알고리즘 - 비율이 맞을 때까지 재료들을 계속 더 넣어보는 방법 1. 첫번째 재료는 4숟가락을 넣어야 하는데, 7 숟가락을 넣음 -> 다른 재료들도 최소 7/4 배 넣어야 함 2. 두번째 재료는 6 x ( 7/4 ) = 10.5 숟가락 넣어야 하는..

https://www.algospot.com/judge/problem/read/POTION# algospot.com :: POTION 마법의 약 문제 정보 문제 마법의 약 수업 시간에 교수님의 설명을 안 듣고 졸던 헤리는 실수로 냄비에 몇 가지 재료의 양을 잘못 넣고 말았습니다. 약의 색깔이 심상치 않게 변하는 것을 눈치챈 www.algospot.com 풀이 주어진 정수 배열의 최대공약수를 구하여 해결하는 문제이다. 최대공약수를 구하기위해 유클리드 알고리즘 을 활용하였다. c = int(input()) def get_gcd(p, q): if q == 0: return p return get_gcd(q, p % q) def get_r_gcd(r_list): for i in range(1000, 0, -1)..