본문 바로가기

분류 전체보기

 (38)
Palindrome, 팰린드롬(회문) 만들기 - 1부 이 포스팅은 Shubham Chaudhary 가 작성한 문서를 참조해서 작성했습니다. 문제 문자열 s 가 주어졌을때 s에 문자를 붙여서 (끝 부분에 삽입한다 생각) 회문(palindrome)을 만들 수 있는 최소의 문자 갯수를 찾아라. 예시 Input : s = "abede" Output : 2 "abedeba" 로 회문을 만들 수 있습니다. 끝에 ba 를 추가했습니다. Input : s = "aabb" Output : 2 "aabbaa" 로 회문을 만들 수 있습니다. 끝에 aa 를 추가했습니다. 정답 문제와 달리 정답은 정 반대로 접근합니다. 솔루션은 다음과 같습니다 : 문자열의 가장 처음부터 하나씩 제거하고 그 문자열이 회문인지 확인합니다. 예를 들자면, 문자열 s = "abede" 을 생각해보세요...
[DP] 게임을 위한 최적의 전략 본 포스팅은 Aashish Barnwal 에 의해 작성된 여기를 참고로 재구성했습니다. 문제 값이 $v_1, v_2 \cdots v_n$ 인 $n$ 개의 동전들을 일렬로 나열한 테이블을 상상해보자. 이 게임은 1:1 대전으로 상대방과 턴을 돌아가면서 한다. 각 턴에, 턴을 가진 플레이어는 일렬로 나열한 동전 중에서 가장 처음 또는 가장 끝에 있는 동전을 선택하고 가져간다. 가져간 동전은 절대로 테이블 위에 올려놓을 수 없다. 또한 가져간 동전의 값은 해당 턴을 가진 플레이어의 점수로 바뀐다. 당신이 게임에 참가한 플레이어라면 무조건 이기기 위한 최대 값을 만드는 경우의 수를 찾아라. (단, 게임의 시작은 당신이 먼저다.) 참고 : 상대방 역시 당신과 같이 똑똑하며, 최적의 수를 둔다고 가정한다. 이 문제..
자다가 봉창 두드린다 라는 말은 무슨뜻일까요? 봉창(封窓)은 토담집 같은 가옥 구조에서 흙벽을 조그맣게 뚫어 창틀을 대지 않고 그냥 창호지를 발라 붙인 일종의 통풍을 위한 혹은 채광을 위한 창을 말합니다. 예전엔 환풍기가 없으니 이런 방식으로 통풍을 했다고 합니다. 들어가고 나가게 설계된 곳은 아니구요. 구설에 의하면, 예전에 바람을 피려고 남녀가 서로 상대방 집의 봉창을 두드려서 비밀신호 를 보낸것 같습니다. 후에는 봉창 두드리는데에 정신이 팔려서 서로의 집에 있는 봉창을 두들겨야 하는데 자기집의 봉창을 두드리는 웃지 못할 이상한 해프닝이 생겨버리는 경우가 있다 합니다. 이처럼 남이 이해할 수 없는 말이나 일을 불현듯 한다는 속뜻으로 '자다가 봉창 두드린다' 라는 속담이 생겨났다고 하네요. (출처 위키백과)
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..
'나는 불만족해서 스트레스예요' 를 줄이자. 만족함과 불만족함에는 객관적인 기준은 없습니다. 어떤게 만족스럽다 불만족스럽다라는것은 개인적 선택 입니다.만족하려면 원하는것을 가지면 됩니다. 이것은 이룸과 성취라고 표현을 하죠. 그런데 대부분은 그 만족감이라는 것이 자신이 목표로 하는것을 이뤄서 오는것이 아니라, 우리 사회가 원하는것을 목적으로 해서 열심히 달려갑니다. 하지만 자신이 아닌 사회의 기대에 부응하기 위한 노력은 굉장히 힘이들죠. 그리고 어떤 목적이든 원하는 것을 얻기위해 노력해서 성취를 이룰 수 있는 사람은 굉장히 소수입니다. 노력은 사실 비슷하게 하고 있지만 대부분은 제자리에 머물게 됩니다. 그런데 제자리에 머물기만 하면 괜찮은데, 노력한것에 비해 결과가 좋지않아 많이 스트레스를 받아서 기존의 상태보다 더욱 망가지는 사람들이 있습니다. ..

티스토리툴바