본문 바로가기

Computer Science/Algorithm

 (117)
BOJ 2004: 조합 0의 개수 이번 문제는요! 입니다. 이 문제 또한 직관적으로 풀면 안된다. 먼저 five(n)랑 two(n)을 통해 총 몇 번의 2와 5의 배수가 사용되는지를 분석할 수 있었다. two(n): 21->10 -> 5 -> 2 -> 1->0 +10 +5 +2 +1 이런 느낌인 것이다! 간단하지만, 이 사이에 신기한 알고리즘이 있었다.
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만의 제곱가지 계산은 많이 힘든가보다. (시간 초과 코드) 그래서 바꿔보기로 결정했다. 첫번째와 마지막 체크포인트를 제외하고, (가운데 체크포인트를 지나고 가는 거리)-(가운데 체크포인트를 제외하고 앞 뒤 노드로 향하는 거리) 중에서 제일 큰 애를 빼기로 했다. 결국 성공이다! 저기 있는 저 복잡한 식으로 많은 식을 줄일 수 있었다. 뿌듯!
BOJ 1935: 후위 표기식2 (Stack) 안녕하세요 여러분들! 오늘은 BOJ 1935: 후위표기식 2으로 찾아왔어요. 바로 풀이법으로 들어갈게요! 사실 자료구조 수업 좀 열심히 들은 분이라면 이 문제는 껌일듯요... (물론 나 미포함) 먼저 몇개의 알파벳을 부여받는지를 정하고, 둘째 줄에서 수식이 들어오면 어떻게 알파벳을 부여된 숫자로 바꿀지 고민했었는데, ord라는 함수를 사용해서 풀어봤습니다! ord()는 안의 인수를 아스키코드로 바꿔주는 함수에요! stack으로 풀어봤습니다! (후위 표기법이니깐~ 심지어 괄호도 없어요 꿀입니다) 이번 주도 화이팅!

티스토리툴바