본문 바로가기

Algorithm/PS

 (60)
[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를 만들어야 이를 통해 비교하고 ..
[1일 1알고] 기둥과 보 설치 https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 가장 중요하다고 생각되는 지점은 기둥과 보에 대해서 기준을 어떻게 잡을 지 입니다. 전체 정사각 격자에서 기둥과 보가 array특정 위치 x, y지점에서 어떻게 존재하고 있는지 기준을 명확히 잡아야 이후 풀이에서도 헷갈리는 점이 없습니다. 저는 x, y일 때 (x, y)에서 위로 뻗는 '기둥', (x,y)에서 오른쪽으로 가는 '보' 라고 생각하고 진행했습니다.또한 한 점에서 기둥과 보가 동시에 존재할 수 있기 때문에 해당 상태를 어떻게 표현할지도 정해..
[1일 1알고] 베스트앨범 https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 자료구조를 활용하는 문제입니다. 비효율적으로 풀더라도 정답 자체에 대한 문제는 없겠지만 그래도 효율적으로 풀기 위한 노력을 하는 것이 중요하겠죠 // most streaming 노래를 두 개씩 모아 베스트 앨범 출시// 노래는 고유번호로 구분// 우선 수록 기준// 1. 속한 노래가 많이 재생된 장르 // 2. 장르 내에서 많이 재생된 노래// 3. 장르 내에서 재생 수가 같다면 고유 번호가 낮은 노래 의 조건을 지켜야합니다. 그렇다면 많이 재생된 장르..
[1일 1알고] 도둑질 https://school.programmers.co.kr/learn/courses/30/lessons/42897 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr오늘은 간단한 문제입니다. 가장 일반적인 dp문제를 아주 쪼끔 비틀었는데요 dp[i] = max(dp[i-1], dp[i-2] + val); 로 이루어지는 점화식을 활용합니다. 원형으로 이루어져있기 때문에 끝과 끝이 만나는 지점의 처리방법만 생각하면 됩니다. 간단하게 첫 집을 고르는 경우와 고르지 않는 경우를 나눠 계산한다면 마지막 집을 선택할 수 있는 가능성이 있는것, 없는 것으로 나누어지고 이에 따라 dp를 계산하면 정답이 나오게 됩니다. #inclu..

티스토리툴바