무니화니

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

안녕하세요 여러분들! 오늘은 BOJ 1935: 후위표기식 2으로 찾아왔어요. 바로 풀이법으로 들어갈게요! 사실 자료구조 수업 좀 열심히 들은 분이라면 이 문제는 껌일듯요... (물론 나 미포함) 먼저 몇개의 알파벳을 부여받는지를 정하고, 둘째 줄에서 수식이 들어오면 어떻게 알파벳을 부여된 숫자로 바꿀지 고민했었는데, ord라는 함수를 사용해서 풀어봤습니다! ord()는 안의 인수를 아스키코드로 바꿔주는 함수에요! stack으로 풀어봤습니다! (후위 표기법이니깐~ 심지어 괄호도 없어요 꿀입니다) 이번 주도 화이팅!

내 코인은 달나라에 가지 못했지만, 내 코드는 별로 보내려고 한다. https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 문제는 다음과 같다. 우선 알파 센투아리는 예전에 내가 와이책에서 읽었던 바로는 지구랑 제일 가까운 별이라고 한다. 이 문제를 풀려면 풀 수 있는 방법 자체는 많아서 어떤 방법으로 풀지 며칠간 고민을 해보았다. 하지만 결국 제일 먼저 떠올랐던 flag변수를 이용해서 풀기로 했다. 우선 ..

킼 프로미스나인 보면서 이 글 올려본다. 원래 송하영이 짱이였는데, 지금은 백지헌 스페셜 보고있다. 하여튼, 이번 문제는 저번에도 풀었던 DFS와 BFS에 대한 내용으로 풀었다. (문제 이름부터 뻔함) 이번 문제는 sort를 사용해서 '방문할 수 있는 노드가 여러가지인 경우 정점 노드가 낮은 순으로' 두었다. DFS는 Depth First Search의 약자로, 말 그대로 재귀를 통해 계속 깊게 탐색을 실시한다. BFS는 Breadth First Search의 약자이고, queue를 통해 방금 전에 방문했던 노드에 대해서 다시 search를 시작하는 식으로 재귀를 이용한다. 각자 장점과 단점이 있다. (dfs가 코드가 간단하긴 하니깐...) 아직까지는 코드를 보면서 써야하는게 참 불편하지만, 많이 하다보..

시즌 말 골드 승급이 제일 어려운 것 처럼, 실버 1 짜리 BOJ 2667번 단지번호붙이기 문제를 풀었다. https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 와.... 물론 요즘 알고리즘 공부 한다고 했더니, 역시 DFS로 풀어야겠다라는 생각은 났다. (나중에 찾아보니 BFS로도 가능하다고 한다. 사실 여기서는 탐색만 하면 상관이 없으니 둘다 가능할 듯 하다.) 그러나 무슨 알고리즘을 사용해야 하는지는 알고 있었지만, 손은 결국 얼어서 코드로 살려..

롤이랑 롤체에서만 골드 찍지 말고, 백준에서도 골드 찍는게 목표인 무니화니. 실버5 난이도의 단어 나누기에 도전하는데... 문제를 보자마자 부르트포스가 생각이 난다. 그러나 쓰기에는 시간초과가 두렵다. 시간 제한 2초를 보고 바로 실행하기로 마음먹는다. 3개의 반복문으로 각각의 범위를 나눠서, 가능한 모든 수를 더하고 그 중 제일 사전순으로 우선인 친구를 찾는다. 성공!

from. 백준 4948번: 베르트랑 공준 (solved) 2021/12/10 이 문제는 우선적으로 '소수 찾기' 알고리즘을 써야 한다. 소수 찾기 하면 에라토스테네스의 체를 사용해야 하지 않겠는가. 마음 편하게 이런식으로 돌려봤었다. 하지만 어라라 시간 초과가 떴다. 비슷하게는 풀리는데, 비효율적인 것 같다. 조금 찾아본 결과 내 생각에는 에라토스테네스의 체에서 알고리즘을 조금 바꿔야 할 것 같다. 우선 더 고민해본다. ----------------------- 2021/12/11 결국 다른 식으로 풀어봤다. 우선적으로, n의 value를 수 제한이었던 123456의 2배로 늘렸다. 2n까지 계산해야 하니깐! 그리고 처음에 primes라는 list를 만들어서 n부터 2n까지의 숫자가 존재하는지를 따지는..