전체 글

DFS와 DP문제는 얼추 기초정도는 땐 것 같아서 다른 알고리즘 유형을 풀어보려고 시도하는데, BFS 유형을 추천받았다.따라서 이미 푸는 방법을 알아버렸기 때문에 답지를 반쯤 본 셈이지만, 아무튼 시작해보기로 했다. 시작점, 끝점, 그리고 버스 노선을 알고 있기 때문에, 이 정보를 기반으로 BFS적으로 접근해보면, 1. 현재 정류소에서 탈 수 있는 버스를 찾는다2. 그 버스들 중 아직 타보지 않은 버스를 고른다3. 그 버스들의 아직 내려보지 않은 정류장 위치를 큐에 넣는다4. 도착점에 도달하거나, 도달할 수 있는 모든 정류장을 다 도달하기 전까지 1-3을 반복한다 가 된다. 어디까지나 BFS가 성립하려면, 1. 현재 위치에서 다음 위치를 고려할 때 이전 위치는 상관 없어야 하며 2. 먼저 큐에 넣은 위치..

몰랐는데 문제들을 보다보니 이 문제가 투 포인터의 기초문제같은 느낌이 강하게 들었다.백준에서 풀 때는 이래저래 조건이 적었는데, 릿코드에서 푸는 이 유형의 문제는 조건들이 덕지덕지 붙어있다.Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that: 0 문제를 읽고 발견해야 하는 조건은 세 가지 있다. 1. 네 수의 합이면서 길이가 4 미만이 들어올 수 있다는 것2. 데이터의 범위가 -10억 ~ 10억이기 때문에 연산과정에서 INT 범위를 초과할 수 있다는 것3. 중복된 답안이 존재하면 안된다는 것 세 번째는 중복 유형이기 떄문에 ..

포스팅은 하지 않았지만 요근래 이래저래 바쁘게 살았다.백준에 얽애이지 않기 위해 여러 사이트의 문제를 풀기 시작했는데, 그 중 하나가 LeetCode였다문제 난이도는 보기에 그렇게 어렵진 않았지만, 다시 좀 녹슨 실력을 다듬을 겸 Medium 문제들을 풀어보고 있다. 여러 고민을 했고, 해결을 했지만, 최적의 풀이 방법이 아님은 깨달았으나 일단 내 시행착오를 기록하고자 올려본다.데이터의 크기는 10^5, n^2가 되면 시간초과가 필연적으로 발생하므로 nlogn 이하의 방식으로 해결해야 한다. 한 막대 기준으로 다른 막대를 선정하는 기준을 고민해보았다.1. 나보다 높은 막대를 좌우에서 찾는다2. 크기 상관 없이 한 방향에서 타겟을 삼을 막대를 찾는다 확신 없이, 정렬을 하면 달라질까해서 일단 정렬을 해 보..

문제 난이도는 골드4로 낮은편이지만 그동안 자주 다루는 알고리즘들만 다루다보니그리디 유형을 좀 경험해봐야겠다고 생각해서 선택한 문제다. 사실 골드4라는 점과 그리디 유형이라고 알고 들어가는 점에서 이미 유리한 이점을 차지하고 있기 때문에아마 더 쉬웠을거라고 생각하고, 차근차근 유형을 좀더 넓혀나가야 할 것이다. 단순하게 합연산이기 때문에, 깊게 고려할 것은 없고 높은 자릿수에 많이 사용되는 알파벳에게 순차적으로9부터 부여해주면 되겠다 싶었다. 파이썬이 익숙하지 않아서 그 과정에서 약간의 시행착오가 있었다. 처음에 어떻게 부여해줄까 고민하다 그냥 그 10^^자릿수만큼 해당 알파벳에 부여해주면 되겠다 싶었고정답을 맞췄다 import collectionsN = int(input())words = []# 알파벳..

USB-DAC로 동작하는 스피커만 사용하다가 오랜만에 헤드폰을 쓸 일이 있어 전면부 단자에 꽂고 사용을 해 봤는데,화이트노이즈가 너무 심해서 몹시 거슬렸다. 게임을 하거나 노래를 들으면 크게 신경쓰이진 않았지만,굳이 화이트노이즈를 감수해야 할 이유를 모르겠어서 해결법을 찾았는데 해결법은 다음과 같았다 1. 컴퓨터를 분해해서 전면부 단자에 간섭이 없이 정상적으로 접지되도록 조심하며 재조립한다2. 그냥 외부 DAC를 사용한다 였는데, 굳이 재조립하기는 부품에 관심이 없어진지도 됐고 나중에 부품 갈때나 신경쓸까 싶어서 2번으로 갔다.그래서 꼬다리덱이라고 부르는 외장 DAC를 어떤걸 사용할까 고민하고 있었는데, 일단 지금 여유도 크게 없고 잘 동작하나 테스트 해 볼겸 저렴한 모델중에서도제일 저렴하고 접근성이 좋..

Android StudioGemini 2.5 Pro를 활용하여 만들어보기 그동안 미루다가 챗봇이 발전했다는 이야기에 한번 실험삼아 엔드 유저 입장이 되어 사용해보기로 결심했다.스튜디오를 다운받으려고 페이지를 살펴보니 이미 Integrated 되어있다고 하는데, 같은 구글 프로젝트이니 그럴만도 싶었다. 자세한 내용 및 진행사항은 추가적으로 진행하고 나서 정리하겠다.

문제를 보고 직관적으로 어떤식으로 풀어야 되는지는 바로 떠올랐지만,구체적으로 어떻게 풀어야할지를 고민했었고, 챗봇의 도움을 통해 구체화하여 풀 수 있었다. 먼저 문제에서 주어지는 철도의 범위가 굉장히 크고, N이 10만인 만큼, 최대 NlogN을 넘어서면 안되는 풀이이며,다르게 말하면 범위를 훑는 방식보단 주어진 N에 의존적인 루프를 활용하면 시간 내에 해결될 수 있을거라 짐작했다. 보자마자 투포인터 계열의 느낌이 많이 났는데, 투포인터를 그대로 활용하기엔 문제가 있었다.해당 사람의 범위에서 벗어난 시점에서 단순 -1을 하기에는 이 사람이 철로의 범위 내에 속했는지 안했는지를 알 수 없음 구현 시도를 하던 시점에서는, 시작점과 끝점을 별개의 배열로 나누어 구현을 해보려고 했지만,범위에서 벗어나기 이전의 ..

이래저래 문제는 많이 풀었었는데, 시간에 쫓기어 글을 적지 못하다이번 문제는 꼭 남겨야겠다 싶어서 오랜만에 글을 적게 됐다. 전형적으로 DP 기초 문제중 하나로 보았던 유형인데,이번엔 기초적인 DP 방식으로 문제를 해결하려 들면 n^2라는 시간제한에 걸리게 된다. 주어지는 배열이 최대 백만이기 때문에, nlogn 안에 문제를 해결해야 한다.log n만에 수를 탐색할 수 있는 방법이라면 아무래도 역시 트리, 대표적으로 세그먼트 트리를 떠올릴 수 있었는데, 배열을 1에서 순차적으로 끝까지 탐색한다면, 일반적인 세그먼트 트리로써는,최대값이나 최솟값 정도는 구할 수 있겠지만 LIS를 구하기에는 적절하지 않다고 판단했다. 그래서 고민하다 결국 포기하고 검색 해 보았는데,Patience Sorting이라는 그리디 ..