본문 바로가기

Algorithm

 (72)
[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..
[1일 1알고] 택배 배달과 수거하기 택배 배달과 수거하기https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 택배를 배달해야합니다.아이디어만 떠올리면 쉽게 해결할 수 있는 문제입니다. cap제한에 따라 택배를 배달할 수 있는데 결국 한번 왕복할 때 cap개의 박스를 배달하고 cap개의 빈박스를 수거할 수 있습니다. 그렇다면 한번 왕복할 때 배달하는 집 혹은 수거하는 집들 중 제일 멀리있는 집의 거리를 더해가면 답이 나온다는 것을 알 수 있습니다.#include #include using namespace std;long long solut..
[1일 1알고] 카드 짝 맞추기 해당 문제는 빡센 구현 문제입니다. 간단해보이지만 여러가지 기술이 합쳐진 컴비네이션 문제입니다. 기본적으로 뒤집어야할 카드의 위치는 모두 공개되어있습니다. 최소 이동값을 구해야하는데 이를 위해 카드를 어떤 순서로 뒤집어야할지 정해야합니다. 최대 카드는 6개까지이고, 카드의 한쪽을 고르면 반드시 다음 선택은 같은 번호의 짝 카드이기 때문에 최대 경우의 수는 12 * 10 * 8 ... * 2일 것입니다. 따라서 모든 경우를 따져도 시간초과가 발생할 문제는 아닙니다.각 경우를 탐색하기 위해서는 조합을 만드는 것 처럼 dfs를 사용해야할 것입니다. 또한 카드를 고를 때 같은 번호라도 어떤 것을 먼저고르는지에 따라 경우가 달라지기 때문에 이는 별도로 백트래킹으로 관리해야할 것입니다.카드에서 카드 간 이동하는 거..
[1일 1알고] 주차 요금 계산 https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr카카오에서 출제한 lv2문제치고는 굉장히 간단한 문제입니다.다만 구현할거리가 적진 않았네요 기본적으로 주어진 문자열을 파싱하고 이를 통해서 자료구조에 저장해가며 해결하는 방식입니다. 단순 구현문제이기에 사람마다 해결방식이 다를 수 있습니다.저는 차가 들어간 시간만을 기록하는 map과 결과를 기록하는 map을 사용했습니다. 문제의 시간이 빡빡하지는 않을 거라 마지막에 정렬하는게 귀찮기 때문에 ordered_map을 그대로 사용했습니다. 파싱은 문자열의 형식..
[1일 1알고] 택배 상자 꺼내기 https://school.programmers.co.kr/learn/courses/30/lessons/389478 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 배열을 사용하면 굉장히 쉽게 풀 수 있지만 이런 문제는 또 수학적으로 풀고 싶은 마음이 생기죠 // 1~n 번호의 택배 상자// snake형식으로 쌓음 좌하단부터 시작// 특정 숫자를 찾을 때 몇 열인지 확인int solution(int n, int w, int num) { int answer = 0; int q = (num-1) / w + 1; int r = (num-1) % w + 1; int offset; if (q ..
[1일 1알고] [PCCP 기출문제] 4번 / 수식 복원하기 그동안 문제는 계속 풀었는데 포스팅을 못했었네요오늘은 약간 복잡한 문제었던김에 적어보려고 합니다. 2~9진법 중 하나를 사용하는 체계일 때 expresion 의 X를 채워넣어야합니다. 예를 들어 expressions가 ["14 + 3 = 17", "13 - 6 = X", "51 - 5 = 44"] 라면 51-5=44를 통해 8진법임을 알 수 있습니다.다만 ["1 + 1 = 2", "1 + 3 = 4", "1 + 5 = X", "1 + 2 = X"]라면 1+2가 3인 것은 1+3이 4임을 통해 알 수 있지만, 1+5에 대해서는 6, 7, 8, 9 진법인지 알 수 없습니다. 따라서 1+5=?가됩니다.따라서 해야할 것은 2~9진법까지 그냥 하나하나 해가면서 정합한지 확인하는 것입니다. 다만 expression..

티스토리툴바