PS

n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 1, 1, 1, 1, 1로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.\-1+1+1+1+1 = 3\+1-1+1+1+1 = 3\

정렬과 함께, Max-heap, Min-heap의 개념을 제대로 활용할 수 있는 문제기 때문에 풀이와 함께 priority queue, heap의 개념까지 함께 정리하고자 한다. 우선 문제의 경우,

dfs, bfs 카테고리의 골드 4문제이며, 일반적인 bfs방식으로 접근 후 해결이 안된다는 것을 확인하고, 백트래킹과 dfs를 활용한 방식의 풀이로 접근해야 했기에 사고 과정을 정리해보고자 한다. 가장 먼저 접근했던 방식은 일반적인 bfs의 문제풀이였다.주어진 세로와

이틀전부터 본격적으로 dfs와 bfs를 접하기 시작했고, bfs 뿐만 아니라 bruteforce까지 함께 고려한 문제기 때문에 포스팅을 남기고자 한다. (+ 혼자서 10분 딱 고민하고 골드문제 한번에 푼게 처음이라 바로 포스팅하는건 비밀)먼저, 문제의 세부 사항들을 살

끊어진 기타줄의 개수 N, 기타줄 브랜드 M개일때, 기타줄을 N개 사기 위해 필요한 돈의 최솟값을 찾는 문제이다. 처음에는 6개 묶음짜리에서 가장 저렴한 묶음과, 낱개 중에서 제일 저렴한 제품만을 사용하면 되고, 처음에는 사고의 흐름대로 굉장히 무식하게 일일히 경우들을

이전에 DFS문제를 풀며 백트래킹의 개념을 처음 접했던 기억이 있다. 나중에 한번 날잡고 제대로 공부해야지하고 미루고 미루다가 이번 포스팅을 통해 제대로 정리해보고자 한다.기본적으로 백트래킹은 '가능한 모든 방법을 탐색한다'는데 기본 아이디어가 있다. 기본적으로 DFS

장장 3시간을 붙들어 메고 있었던 문제다... 처음문제를 접하자마자 DFS를 사용해야겠구나 라고 생각하고, 열심히 코드를 작성했다. input이 문자열의 이중배열 리스트로 주어졌기 때문에 탐색속도를 고려하여 전체 set을 딕셔너리 형태로 수정한 뒤, key, value

지난번에 정리한 백트레킹에 이어 한번 날잡고 제대로 공부해야겠다고 마음먹은 분할정복이다. 간혹가다가 분할정복 문제를 접하게 되면 그 매커니즘이 직관적으로는 이해되지만 100% 내것이다!라고 말하기엔 애매한 부분들이 좀 많은 것 같아, 제대로 개념 정리 후, 관련 문제들

최단 경로라는 문제의 조건과 주어지는 간선들의 비용이 모두 양수이므로, 문제를 잠깐만 살펴보더라도, 다익스트라 문제임을 알 수 있었다. 다익스트라 알고리즘을 손에 익을 만큼 써보면서 연습하고 있기에 이 문제를 풀면서 다시한번 더 다익스트라 알고리즘을 정리해보고자 한다.