프로그래머 스 레벨 4 난이도 - peulogeulaemeo seu lebel 4 nan-ido

Question

안녕하세요! 이틀간 푹 쉬다가 돌아온 쏘코입니다.

목차 Show

0. 문제 설명
0.0. 제한사항
0.1. 입출력 예
1. 풀이 과정
2. 소스 코드
이동식 저장소
프로그래머스 - 코딩 테스트 연습 사이트 본문
프로그래머스 - 코딩 테스트 연습 사이트
스킬 체크
코딩테스트 연습
코딩테스트 고득점 Kit
모든 문제

DP가 총 4문제인데, 가장 낮은 난이도가 레벨3이라는게 참 오묘합니다.

DP는 정말 구현보다 내가 맞는 알고리즘을 생각해냈는지가 굉장히 중요한 것 같아요.

이번 문제도 굉장히 재미있는 문제였습니다.

출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43105

코딩테스트 연습 - 정수 삼각형

[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30

programmers.co.kr

0. 문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

0.0. 제한사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

0.1. 입출력 예

triangle	result
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]	30

1. 풀이 과정

정말 간단합니다. dp문제라는 것을 염두에 두고 푼다면 금방 찾아내실 수 있을 것이고, 그게 아니더라도 조금만 생각하면 쉽게 떠올릴 수 있습니다.

저는 두 가지 방식을 생각했습니다. 처음에는 DFS방식으로 모든 경로를 탐색해서 최대값을 구하는 방식을 생각했습니다. 그런데 이 문제가 DP섹션에 있었다는 것을 생각해볼 때 이것은 바람직한 풀이법이 아니라고 생각했습니다.

그래서 다음에 떠올린 방법은 bottom-up방식입니다. 경로는 아래 2개의 수 중 더 큰 쪽으로 진행될 것이기 때문에, 아래서부터 붙어있는 2개를 비교해서 더 큰 것을 위쪽에 더해주는 방식입니다.

이미 존재하는 triangle vector를 이용해서 아래서부터 위로 올라가면서 확인합니다. 아래부터 돌기 때문에 삼각형의 단계를 나타내는 i는 거꾸로 진행되고, 단계 안에서 수의 순서를 나타내는 j는 그대로 앞에서부터 확인해도 무방합니다.

또한 triangle를 파라미터값으로 받을 때 call by value 방식으로 받아왔으므로 원본이 훼손되지 않습니다. 따라서 이미 존재하는 triangle에 더해주면서 올라가도 됩니다.

이런 식으로 끝까지 올라가서 triangle[0][0]까지 다 더해지면, triangle[0][0]을 answer에 넣어서 출력하면 끝입니다.

2. 소스 코드

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<vector<int>> triangle) {
    int answer = 0;
    // 아랫쪽 열에 있는 친구들 중에 붙어있는 것들끼리 비교해서 큰 친구를 위와 더해준 후 sum에 넣는다. 이걸 반복!
    for (int i = triangle.size()-1; i > 0 ; --i){
        for(int j = 0; j < i; ++j){
            triangle[i-1][j] += (max(triangle[i][j],triangle[i][j+1]));
        }
    }
    answer = triangle[0][0];
    return answer;
}

3. 후기

내가 생각하고 있는 것이 맞나..라는 의구심이 조금 드는 문제였습니다. level3이라고 해서 약간 쫄아있었던 것 같네요. level보다 어려운 문제가 있으면 level보다 쉬운 문제도 있을텐데라고 생각만 했었는데 이 문제는 그럭저럭 level3에서는 굉장히 쉬운 문제 축에 속하지 않을까 생각합니다.

top-down 방식으로 풀면 재귀함수를 사용하면 될 것 같습니다. DP문제에서 보통 top-down방식은 재귀, buttom-up방식은 반복문을 사용합니다. 이런 꿀팁만 알아놓으면 풀이시간이 훨씬 단축될 수 있으리라고 생각합니다 :)

개인적으로 생각하는 solved.ac와 프로그래머스 난이도의 상관관계

듸발자 김며듬 ・ 2020. 3. 21. 3:21

본인 뇌피셜임. 이 글 쓴 이유는 프로그래머스 레벨 2-3 과 solved.ac 실버-골드는 개인별로 느끼는 난이도가 매우 달라서라고 생각함. 실버가 골드보다 어려울 때도 있어서 당혹스러울때가 있었음.

프로그래머스 레벨 1 == solved.ac 브론즈

프로그래머스 레벨 2 == solved.ac 실버

프로그래머스 레벨 3 == solved.ac 골드

프로그래머스 레벨 4 == solved.ac 플레

(근데 solved.ac 플레보단 프로그래머스 4가 조금 더 쉬운거 같기도 하면서도... 가끔 프로그래머스 2인데 플레보다 어려운거도 보이고.... 브론즈 제외하면 개인마다 체감난아도가 다름)

그 위론 신의 영역이라.. ㅋㅋ 어째튼 대략적으로 저 틀이라고 생각하고 제발 컴공 신입생/전과/편입 희망하면 주력 언어 하나 잡아서 브론즈라도 좀 낮게 잡더라도 “스스로의 힘으로” 풀고 오는게 좋다고 생각.

이동식 저장소

프로그래머스 - 코딩 테스트 연습 사이트 본문

공부

프로그래머스 - 코딩 테스트 연습 사이트

해스끼 2020. 5. 3. 19:30

인터넷을 돌아다니다가 좋은 사이트를 하나 찾았다.

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

코딩 테스트 대비 + 인턴 등 채용 프로그램을 제공하는 사이트이다. 심지어 채용 정보도 있다!

다만 나는 당장 취업할 생각은 없는 관계로, 코딩 테스트 관련 서비스를 살펴보았다.

참고로 Github 계정을 이용하여 로그인할 수도 있다. 네이버, 카카오로 로그인하는 건 많이 봤어도 깃허브는 처음 봤다. 개발자끼리는 이렇게 하는 것이 서로 편할 듯.

스킬 체크

내 코딩 실력을 대략적으로 테스트해 볼 수 있는 페이지다. 레벨 1부터 5까지 준비되어 있다. 제한 시간 안에 주어지는 문제를 해결해야 하는데, 정답을 직접 출력하는 게 아니라 반환하기만 하면 된다. 즉, 어떤 문제를 풀어서 정답을 돌려주는 함수를 작성하면 된다(정확히는 주어지는 함수 템플릿을 완성하면 된다). 전역 변수와 함수는 자유롭게 사용할 수 있다. 말이 조금 어려운데, 해 보면 알 거다.

직접 풀어본 결과, 레벨 1은 solved.ac 기준으로 브론즈~실버 하위권 정도, 레벨 2는 실버 상위~골드 정도 되는 것 같다. 레벨 2는 두 번째 문제에서 시간 제한에 한번 걸려서 실패했다. ㅠㅠ 두 번째 도전에선 빠르게 성공했다.

레벨2

문제는 재도전할 때마다 달라지며, 한 번 합격한 단계에는 재도전할 수 없는 듯 하다.

이름 그대로 실력 체크에 적절하다. 시간의 압박을 느껴 보고 싶다면 도전해 보길.