프로그래머스 풀이 (90) 썸네일형 리스트형 [프로그래머스LV2] 땅따먹기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12913 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 처음엔 백트래킹으로 구현했는데 시간초과가 났다. 4^10만이기 때문에 말도안되는 시도였다.그래서 DP를 생각했고 백트래킹에 접목했는데 틀렸다. 그리고 좀 더 유심히 문제를 보니 열은 반드시 4로 주어지는 문제였다. 그래서 Bottom-Up 방식 DP를 생각해냈다. 결국 i번 행에서는 i - 1행의 3가지 경우 중 하나만 올 수 있고 그 중 최댓값을 구하면 되기 때문이다. 그래서 다음과 같은 점화식이 생긴다. DP[i][j] = value[i][.. [프로그래머스LV3] 등굣길 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제를 처음 풀었던 2023년 5월에도 bfs로 풀면 되지 않을까 생각했고 무려 2024년 10월에도 같은 생각을 해서 틀렸다는 점에서 반성이 필요하다. 동적계획법을 보고 다익스트라여서 dp라고 한건가 생각했는데 아니었다. 100 * 100 이고 아무리 다익스트라를 사용한다 해도 결국은 2^100*100 이 되어버린다. 그래서 이 문제는 그냥 dp로 중복을 제거하여야한다. dp에 어떤 정보를 담아야할까? 난 처음에 이.. [프로그래머스LV3] 숫자 게임 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr A와 B를 정렬하고 A와 맞으면 둘 다 인덱스 ++ 아니면 B만 ++ 해보는 방식으로 풀면 된다. 문제 유형은 Greedy로 생각된다. #include #include #include using namespace std;int solution(vector A, vector B) { int answer = 0; sort(A.begin(), A.end()); sort(B.begin(), B.end()); for.. [프로그래머스LV3] 단속카메라(C++) https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 벌써 세번째 푸는데 잘 못푼 나 .. 이런 문제를 풀 때는 케이스를 몇 개 생각해볼 수 있다. 검은색 범위가 원래 있었던 것이고 파란색이 들어온 차의 범위라고 하자. 그리고 빨간색 점이 카메라의 위치라고 하자. 위사진의 케이스들은 모두 새로운 카메라가 필요없다. 첫번째, 두번째 케이스는 원래 있었던 카메라의 위치 = 차가 나가는 지점을 바꿀 필요가 없다. 이미 커버하고 있기 때문이다. 그러나 세번째 케이스의 경우는 기.. [프로그래머스LV3] 인사고과(C++) https://school.programmers.co.kr/learn/courses/30/lessons/152995# 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 쉬운듯 하면서도 까다로운 문제였다. N이 10만으로 N^2 하면 TLE 이므로 최적화가 필요한 문제였다.처음엔 근무태도, 동료평가를 각각 sort한 배열을 만들었는데 이렇게하면 안된다. 결국은 O(N^2)의 시간이 필요하게 되기 때문이다. 문제의 골자는 다음과 같다. 1. 이 사람이 인센티브를 받을 수 있는가? -> 모든 사람에게 둘 다 밀리지는 않는가?2. 그래서 원호의 순위는? 그래서 이 문제는 sort를 통해 근무태도, 동료평가 중.. [프로그래머스SQL] 대여 횟수가 많은 자동차들의 월별 대여 횟수 구하기 https://school.programmers.co.kr/learn/courses/30/lessons/151139#qna 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 어려운 문제였다. 그룹바이를 두개의 컬럼으로 걸 수 있는 능력이 있는가 묻는 문제였다. 또한 서브쿼리도 그룹바이를 써야하고 메인쿼리에서도 그룹바이를 써야하는 문제로 신선했다.그런데 메인 쿼리에서 WHERE START_DATE>="2022-08-01" and START\_DATE이것을 제거하면 틀렸습니다가 나오는데 이미 서브쿼리에서 다 정재된 CAR_ID가 오는것인데 왜 한 번 더 하냐면 서브.. [프로그래머스LV3] 순위 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49191#qna 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 위상정렬을 가장 먼저 떠올릴 수 있었지만 2번의 그래프 탐색으로도 끝낼 수 있는 문제이다. 승자 -> 패자 패자 -> 승자 그래프로 두개 만들어 두고 한번씩 탐색한 후 각 노드가 연관된 노드의 개수가 5이면 순위를 정할 수 있다고 판단한다. 이렇게도 풀 수 있지만 위상정렬을 사용해서도 풀 수 있는데 위상정렬은 그래프의 순서를 유지하여 정렬하는 방법이다. 문제에서 준 예제를 그래프로 표현하면.. [프로그래머스 SQL] 헤비 유저가 소유한 장소 https://school.programmers.co.kr/learn/courses/30/lessons/77487 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 하나의 테이블에서 두개 이상의 튜플을 가진 것들을 출력하는 문제이다. 난 그룹화하여 2개 이상을 셀렉트하고 그것을 IN 함수로 처리했다. 다른 풀이도 모두 비슷한 방향으로 풀이한 것 같다. -- 코드를 입력하세요SELECT * FROM PLACES WHERE HOST_ID IN ( SELECT HOST_ID FROM PLACES GROUP BY HOST_ID .. 이전 1 2 3 4 5 ··· 12 다음
