Computer Science 136

BOJ 1463: 1로 만들기

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

BOJ 11576: Base Conversion

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

BOJ 2089: -2진수

그럴 때 다들 있지 않으신가요 문제가 간단해 보이는데, 그래서 막상 풀려고 하면 마땅히 해답이 떠오르지 않는 경우요.. 생각보다 많으시다고요? 저도요. ㅋ. 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 바로 이 문제입니다! 간단한 듯이.... 어려운.... ㅋㅋㅋㅋㅋ.... 그럴 수록 정공법을 써야죠. 문제의 '원리'를 파악하기! 제 풀이입니다..

BOJ 6588: 골드바흐의 추측

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

BOJ 2609: 최대공약수와 최대공배수

상당히 직관적이고 간단한 문제이다. 하지만 이 문제를 정확하게 풀려면, (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 유클리드 호제법 - 위키백과,..

BOJ 17298: 오큰수

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

BOJ 10799: 쇠막대기

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

BOJ 9012 괄호

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

BOJ 10655: 마라톤 1

오늘도 즐거운 백준 시간~! 오늘의 문제는 바로바로 마라톤 1! 입니다! 먼저 이 문제를 보고 풀고자 하는 아이디어는 O(n^2) 복잡도로 for 문을 두개 돌렸다. 그러나 시간 초과... 역시 10만개의 체크포인트가 나오기에 10만의 제곱가지 계산은 많이 힘든가보다. (시간 초과 코드) 그래서 바꿔보기로 결정했다. 첫번째와 마지막 체크포인트를 제외하고, (가운데 체크포인트를 지나고 가는 거리)-(가운데 체크포인트를 제외하고 앞 뒤 노드로 향하는 거리) 중에서 제일 큰 애를 빼기로 했다. 결국 성공이다! 저기 있는 저 복잡한 식으로 많은 식을 줄일 수 있었다. 뿌듯!