본문 바로가기

프로그래밍

(27)

python 의 변경가능(Mutable) vs 변경불가능(Immutable) 객체들 python 의 모든것은 객체(object) 입니다. 그리고 객체는 mutable(변경가능) 하거나 immutable(변경불가능) 하죠. 조금더 자세히 들어가 보겠습니다. python 의 모든것은 객체로 표현된다고 했기때문에 모든 변수들은 object instance 를 가지고 있습니다. (쉽게 말하면 붕어빵을 만들때, object는 붕어빵을 만드는 틀이고 instance는 찍어나온 붕어빵이라 생각하시면 되겠습니다.) 그리고 object가 개시(initiate)되면, unique 한 object id를 부여받습니다. object 의 타입은 프로그램 실행 시간에 정해지며, 한번 정해진 이상 절대 바뀌지 않습니다. 하지만 object의 상태는 만약 object가 mutable 하다면 바뀔 수 있습니다. 간단..

[DP] 부분집합의 합 구하기 (Subset Sum Problem) DP 연습 문제 : 부분집합의 합 구하기음수가 아닌 정수들의 집합들과 $sum$ 이라는 하나의 값이 주어지면, 집합들의 부분집합 중에 집합 내의 모든 숫자들을 더할때 $sum$ 과 같은 값이 있는지 알아내세요.예제 : set[] = {3, 34, 4, 12, 5, 2} , $sum = 9$ 출력값 : True // {4, 5} 의 부분집합의 합이 9 로 $sum$ 과 같습니다. 이 문제는 여기서 연습할 수 있습니다.$isSubSetSum(int \ set[], int \ n, int \ sum)$ 이 $set[]$ 의 부분집합의 합이 $sum$ 과 같은게 있는지 알아내는 함수라고 합시다. $n$ 은 $set[]$ 집합 원소의 개수 입니다.$isSubSetSum$ 문제는 두가지의 서브문제로 분리될 수 있습..

Python 팁 프로그래밍 문제를 풀때 도움 될만한 팁을 여기에 적습니다. 일련의 숫자 입력받아서 list 로 만들기 omg = list(map(int, input().strip().split(' '))) 예시로 입력이 1 2 3 4 면, omg 는 [1,2,3,4] 의 list 가 됩니다. list 오름차순 또는 내림차순으로 정렬하기 omg.sort() # 오름차순 정렬 omg.sort(reverse=True) #내림차순 정렬 변수의 주소값 알아내기 z = [1] * 3 print(hex(id(z[0]))) id() 함수로 주소값을 찾아서 hex() 함수로 16진수로 변환합니다. 주어진 문자열 거꾸로 출력하기 str = 'hello' print(str[::-1]) 출력값은 'olle..

[DP] 막대기 자르기 아직 DP 를 푸는 전반적인 방법은 여기를 참조해 주세요.DP 연습 문제 : 막대기 자르기 n 인치 길이의 막대기와 n 보다 작은 조각들의 길이에 따른 가격이 적힌 배열이 주어집니다. 막대기를 쪼개어 조각들로 나눴을때 얻을 수 있는 최대의 값을 찾으세요. 예를 들면, 8 인치 막대기와 사이즈에 따른 값은 아래와 같습니다. length | 1 2 3 4 5 6 7 8 -------------------------------------------- price | 1 5 8 9 10 17 17 20그렇다면 얻을 수 있는 최대 값은 22 입니다. (2 와 6으로 자르면서 얻을 수 있음)그리고 가격이 아래와 같이 달라진다면, 얻을 수 있는 최대 값은 24 입니다. (1 인치 짜리를 8개로 만듦)length | 1..

C 의 비트연산자에 대한 흥미로운 사실들 저의 글은 geeksforgeeks 의 글을 참조해 작성했습니다. C 에는 6가지의 비트 연산자가 있습니다. & (bitwise AND) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 AND 연산을 수행합니다. 양쪽 비트가 모두 1이면 1을 출력합니다. 그 외에는 0.| (bitwise OR) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 OR 연산을 수행합니다. 두개의 비트들중 하나가 1이라면 1을 출력합니다. 그 외에는 0.^ (bitwise XOR) : 2개의 숫자의 이용해 각 숫자들의 모든 비트의 XOR연산을 수행합니다. 양쪽 비트가 다르면 (1,0 또는 0,1), 1을 출력합니다. 그 외에는 0.> (right shift) : 2개의 숫자를 입력받아 비트들을 오른쪽으로 옮깁니다. ~ (N..

동적계획법 (Dynamic Programming) 는 어떻게 풀까? 이 포스팅은 Nitish Kumar 의 기사를 참고하여 만들었습니다. [출처] 동적계획법 (Dynamic Programming), DP 는 다항(Polynomial)한 시간안에 특정 문제를 풀기위한 기술입니다. DP 를 이용한 솔루션은 지수형태의 단순한 방법보다 훨씬 빠르고, 솔루션이 맞다는것을 쉽게 증명할 수 있습니다. DP를 풀기위한 4 step문제가 DP 를 쓰면 풀리는지 확인하기최소 매개변수를 이용해 어떻게 상태를 표현할지 정하기상태 관계를 수식화 하기도표 작성(tabulation) 하기 (또는 메모이제이션(memoization) 을 추가하기)Step 1 : DP 문제를 어떻게 구분하나요?- 일반적으로, 특정 수량의 최대 최소를 구하는 문제들 (대표적으로는 Knapsack 문제), 특정 조건을 만..

Definition of congruence relation (합동 관계 정의) $ a \equiv b \quad (mod \ n)$ 은 무슨뜻일까요?이 방정식은 합동 관계라는 개념으로 추상대수학에서 쓰이는 방정식 입니다. 합동 관계에서 가장 기본적인 예죠. 저도 자세히는 모르니까, 이번 글에서는 저 방정식만 해석해보겠습니다.양의 정수인 $n$이 주어졌을때, 만약 $a-b$ 가 $n$ 으로 나눠질 수 있다면 ( 또는 $a$ 와 $b$ 가 $n$ 으로 나눠져서 나오는 나머지값이 서로 같다면 ) $a, b$ 는 $n$ 의 합동 모듈로 라고 부릅니다. 수식으로는 다음과 같습니다.$ a \equiv b \quad (mod \ n)$ 예시$37$과 $57$이 $10$ 의 합동 모듈로라고 하겠습니다. 그렇다면,$ 37 \equiv 57 (mod \ 10) $입니다. $37 - 57 = -20$..

기본 숫자 이론 - 1 이번 포스팅에서는 프로그래밍 문제를 해결할때 자주 쓰이는 기본 수학에 대해 다뤄보려 합니다. 오늘 소개할 주제는 총 5가지 입니다. 나머지 연산 나머지 연산 $\%$ 지수 최대 공약수 : Greatest Common Divisor (GCD) 확장된 유클리드 알고리즘 (for GCD) 모듈로 연산 곱의 역원 (Modular multiplicative inverse)아래에 작성된 모든 내용은 ('여기')를 참조하여 제 방식대로 재해석했습니다. 1. 나머지 연산 (Modular arithmetic) - 어떤 숫자가 다른 숫자로 나눠질때 나머지 연산자는 나머지 값을 찾아냅니다. 기호로는 % 로 표현합니다. 예제5와 2의 숫자가 있다고 가정합시다. 5%2 는 1 입니다. 왜냐하면 5는 2로 나눠지고 나머지가 1이..

이전 1 2 3 4 다음

티스토리툴바