무니화니

안녕하세요! 2021년 마지막 날에도 이 문제를 풀고 있네요 ㅎㅎ https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 바로 이 문제입니다! n=int(input()) data=[[0]*4 for _ in range(100001)] data[1]=[0,1,0,0] data[2]=[0,0,1,0] data[3]=[0,1,1,1] for i in range(4,100001): data[i][1]=data[i-1][2]+data[i-1][3] data[i][2]=data[i-2][1]+data[i-2][3..

어제 백신을 맞아서 포스팅을 못 했는데, 오늘은 상태가 매우 괜찮아서 이렇게 왔습니다! 오늘의 문제 보시죠! 사실 이 문제도 예전에 스웨덴에서 있을 때 봤던 문제다. 그때는 알고리즘에 대한 기초 지식이 아예 없어서 어떻게 풀어야하는지 몰랐어서 굉장히 오랜 시간 고민하고 방황했었는데, 알고리즘 책도 읽고 다양한 문제를 풀면서 해결 방안을 바로 찾아냈다. 이렇게 간단한 코드로 해결한다. 우선, data라는 파일에 각 index별로 최소의 연산을 계산한다. 예를 들면 data[3]은 3을 만드는 데에 드는 연산의 수라고 할 수 있겠다. 이런 식으로 했을 때, 이미 있는 데이터보다 1을 더하거나, 2를 곱하거나, 3을 곱했을때 더 연산의 수가 적어지는 수로 업데이트한다. good!

안녕하세요! 벌써 2021년 한 해가 저물어 갑니다. 본론으로 들어가서, 코드는 다음과 같다. 먼저, 각 자리를 받고, 보기 쉬운 10진법으로 만들었다. 만드는 방법은, 각 digit에 일정 가중값을 곱했다. 10진법에서 b진법으로 만들 때는 나누기에서 나오는 나머지를 이용해서 각 자리의 값을 구했다. 그래도 요즘에 파이썬 며칠 했다고, 코딩 치는게 조금 편해졌다. 남들이 놀 때 공부하고, 남들이 공부할 때 공부하는 것이 비결 아닐까? 벌써부터 속단하긴 이르지만, 결국 노력만이 승리하는 길이 아닐까 싶다.

그럴 때 다들 있지 않으신가요 문제가 간단해 보이는데, 그래서 막상 풀려고 하면 마땅히 해답이 떠오르지 않는 경우요.. 생각보다 많으시다고요? 저도요. ㅋ. https://www.acmicpc.net/problem/2089 2089번: -2진수 -2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 110 www.acmicpc.net 바로 이 문제입니다! 간단한 듯이.... 어려운.... ㅋㅋㅋㅋㅋ.... 그럴 수록 정공법을 써야죠. 문제의 '원리'를 파악하기! 제 풀이입니다..

이번 문제는요! 입니다. 이 문제 또한 직관적으로 풀면 안된다. 먼저 five(n)랑 two(n)을 통해 총 몇 번의 2와 5의 배수가 사용되는지를 분석할 수 있었다. two(n): 21->10 -> 5 -> 2 -> 1->0 +10 +5 +2 +1 이런 느낌인 것이다! 간단하지만, 이 사이에 신기한 알고리즘이 있었다.

역사적인 문제죠? 이걸 코딩으로 나타낼 수 있다니 정말 영광입니다. 문제는 잘 설명 되어있으니 설명은 생략하겠습니다. 코드는 다음과 같습니다. 저번에 설명했던 에라토스테네스의 체로 먼저 소수들을 찾아내고, 3부터 넣으면서 가능한 수를 구해봅니다. 근데 왜 "Goldbach's conjecture is wrong." 이거는 코드에 안 들어가나면, 애초에 이게 해결되지 않는 문제라는 점에서 잘못된 예시가 아직 발견되지 않았음을 의미하고, 결국 틀린 예시가 이 경우에는 없다는 것이죠. 이런 알고리즘은 수학적인 지식으로 풀 수 있어서 더욱 흥미로운 듯!

상당히 직관적이고 간단한 문제이다. 하지만 이 문제를 정확하게 풀려면, (math 모듈을 import 하지 않고ㅡㅡ) 유클리드 호제법을 알아야 한다. 유클리드 호제법이란, 'a와 b의 최대공약수'는 'b와 "a를 b로 나눈 나머지"의 최대공약수'와 같음을 나타낸다. (a를 b로 나눈 나머지를 r라 하곤 한다.) a와 b의 최대공약수 = b와 r의 최대공약수 b를 r로 나눈 나머지 r'을 구하고, r을 r'으로 나누고... 계속 반복하면 된다. 그랬을 때 나머지가 0가 될 때 나누는 수가 바로 최대공약수이다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 유클리드 호제법 - 위키백과,..

골드 4 문제에 도전을 해본다! 당연하게도, 이 문제를 곧이곧대로 반복문 두개로 풀면 시간 초과가 날 것이다. 수열의 크기가 100만까지 커질 수 있지 않는가! 그렇기에, stack을 이용해서 풀었다. 여기서 stack을 구현하는 방식은, 간단하게 말해서 오큰수를 찾지 못하면 stack에 넣고, 오큰수를 찾을 수 있는 경우에서는 stack에서 가능한 만큼 지워주는 방식으로 구현한다. 처음에 -1을 모든 칸에 넣고, stack에 값이 있는지와 없는지로 나누고, stack에 값이 있는 경우에는 stack에서 top이 data의 i번째와 만났을 때 stack이 처리 가능한지로 나눠서 푼다. 어렵다 어려워.!

왜 크리스마스에 코딩을 하냐구요? 군대에서 이게 제일 재밌거든요.... (롤토체스 하기 제외) 하하....... 오늘의 문제는? 쇠막대기라는 문제입니다! 예전에는 풀어봤었는데... 확실히 요즘 알고리즘 공부하면서 예전 보다는 실력이 확실히 늘기는 했다. 정말이다. 노력한 만큼 보여준다. 이 문제는 꼭!! 꼭!!!!!!!! 그림을 그려봐야한다. 안 그러면 머리에 쥐가 날수도... 아니면 문제 이해하기도 힘들겁니다. (국어는 어렵습니다.) 제 해답입니다. 첫째로 level이라는 변수는, 몇개의 쇠파이프가 있다를 나타내는 의미를 갖고 있습니다. 예를 들면, level이 4면, 4개의 쇠막대기가 있다는 뜻이죠. 하지만, ( 다음에 바로 )가 나와버리면 레이저를 의미하기에, ( )가 되는 경우에 level을 하나..

예전에 20살 최환 시절, 이 문제를 스웨덴에서 풀었던 기억이 있다. 그때는 기본적인 자료구조인 스택도 모르던 시절이여서, 이 문제가 극한의 난이도로 느껴지곤 했다. 지금의 나는 조금 달라진 것 같다. 그래도 발전하고 있네! 코드는 다음과 같다. 스택을 통해 구현했다. stack이 비어있을 때, (가 아닌 )가 입력이 되면 얘는 NO이기 때문에, stack이 비어있는 경우와 안에 값이 들어 있는 경우로 처음 조건문을 두었다. 그리고 나중에 (와 )의 쌍이 만들어지면 stack에서 pop시켰고, 각각의 string을 다 돌았을 때 stack에 값이 있으면 NO, 깔끔하게 비어있으면 YES를 출력하도록 했다. 많이 방황하고 헤메고 있지만, 그래도 발전하고 있는 나를 보아하니 기분이 좋다. 조금 더 간절해지고..