본문 바로가기

Algorithm

 (72)
[1일 1알고] 보석 쇼핑 https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제를 읽자마자 투포인터로 풀어야한다는 느낌이 듭니다. 다만 이런 문제는 구현할 때 실수가 생기기 쉽죠 물론 제가 실수해서 하는 말입니다.아이디어는 간단합니다. 투포인터로 left, right 인덱스를 관리하며 모두 포함한다면 left를, 포함하고 있지 않다면 right를 움직이는 방식으로 계산해나가면 됩니다. #include #include #include #include using namespace std;vector solution(vector g..
[1일 1알고] 단어 퍼즐 https://school.programmers.co.kr/learn/courses/30/lessons/1882 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 글을 읽자마자 깊은 dp의 향기가 느껴집니다.스읍ㅈ strs의 크기도 작고 t의 크기도 작고 단어 조각의 크기도 작기 때문에 어떻게 풀어도 잘못푼것만 아니면 좋게좋게 넘어가줄 것 같네요#include #include #include using namespace std;bool check(string& src, string& comp, int N, int idx, int size){ if (idx + size > N) return fals..
[자료구조] Priority Queue 간단하게 알아보기 (Feat. Heap) PriorityQueue 는 이름에는 queue가 들어가지만, queue와 다르게 pop을 할 때 지정한 규칙(기본적으로는 큰 값)에 따라 값을 추출할 수 있습니다. queue의 경우 FIFO구조를 통해 먼저 들어간 값을 먼저 꺼내지만, PriorityQueue의 경우 내부구조가 Heap으로 이루어져있어 이진트리의 성질을 보입니다. priority_queue는 위와 같은 template 인자를 받습니다. typename: pq에서 사용할 원소의 타입을 설정합니다._Pr: predicate를 설정합니다. 보는 것처럼 기본 설정은 container=vector, _Pr는 less입니다. (less라면 큰 값 부터 pop)priority_queue의 내부 생성자를 확인해보면 _Make_heap()을 호출해 h..
[1일 1알고] 경주로 건설 https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 일반적인 bfs(다익스트라)에 방향 개념이 더해진 문제입니다.N자체가 최대 25이기 때문에 꼭 다익스트라를 써서 단축시킬 필요는 없겠네요 해당 문제에서 가장 중요한 것은 방향입니다.같은 위치이더라도 방향에 따라 이후의 비용이 달라질 수 있기 때문에 이에 대한 계산을 별도로 해야합니다. 예를 들어 r, c의 위치에서 특정 방향의 cost가 가장 작더라도, 이후의 진행상황에 따라 다른 방향이 더 cost가 적은 길이 될 수 있기 때문에 섵부르게 미리 통합할..
[1일 1알고] 부대 복귀 https://school.programmers.co.kr/learn/courses/30/lessons/132266 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 간단한 BFS문제입니다. 그런데 약간 생각을 잘못한 부분이 있었네요 보면 sources들 에서 destination까지 가는 거리를 각각 측정하는 것입니다.처음에는 source마다 bfs를 돌려 dest 까지의 거리를 측정했는데, 통과는 했지만 몇몇 test에서 많은 시간이 소요되었습니다.// 지역은 유일한 번호로 구분// 최단시간 복귀//int bfs(int n, int src, vector>& arr, int dest){ queue> q; ..
[1일 1알고] 110 옮기 https://school.programmers.co.kr/learn/courses/30/lessons/77886 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 오늘도 간단한? 문제입니다. (한번 틀림) 110을 뽑아내고 이를 올바른 위치에 삽입하는 문제입니다. 읽자마자 stack을 사용해야하는 것을 알 수 있습니다. 110자체는 stack방식을 통해 추출하면 될 일이고, 이후 이 110들을 어디에 삽입할지를 결정해야합니다. 사전 순으로 110이 들어가는 위치는 마지막으로 0이 들어간 위치가 됩니다.왜냐하면 1110과 같은 문자열이 남아있을 수 없기 때문입니다.#include #include using name..
[1일 1알고] 스타 수 https://school.programmers.co.kr/learn/courses/30/lessons/70130 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr dp인척하는 그리디 문제입니다. 코드 자체는 완성하면 간단한데 의도를 파악하는게 어렵네요 스타 수열은 길이 2의 집합들이 특정 값을 공통적으로 포함하며 집합 내에서는 서로 다른 숫자를 가지는 경우입니다. a의 부분 수열 중 가장 길이가 긴 스타 수열을 찾아야합니다.{1, 1, 2, 3, 1, 4} 이렇다면 {1, 2}, {3, 1} 혹은 {1, 3}, {1, 4} 등이 답이 될 수 있습니다. 부분수열이 들어가며 a의 길이가 최대 50만 이기때문에 dp로..
[1일 1알고] 카운트 다운 https://school.programmers.co.kr/learn/courses/30/lessons/131129?language=cpp 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 해당 문제는 특정 점수를 최소회수로 도달하는 방법을 찾는 문제입니다. 문제의 결을 보면 코인 혹은 배낭 문제와 비슷한 dp문제라고 생각이 드실겁니다. dp문제가 언제나 그렇듯 점화식을 세우고 dp배열을 어떻게 설정할지가 가장 중요하게 되는데요dp의 index는 점수, dp의 value는 필요한 횟수, 싱글or불의 횟수로 지정하는 것이 타당해 보입니다. 그리고 미리 점수를 계산하기 위한 array를 만들어야 이를 통해 비교하고 ..

티스토리툴바