본문 바로가기
반응형

전체 글308

[프로그래머스/C++] 카운트 다운 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 다트를 던져서 최소한의 횟수로 일정 점수를 획득하고, 최소한의 횟수 중에서도 싱글과 불을 가장 많이 던지도록 하는 문제다. 이 문제는 DP로 쉽게 풀 수 있다. A라는 점수를 얻기 위한 최소한의 횟수를 구하려면, 아래와 같이 표현 할 수 있다. [B + 다트 점수] = A 여기서 B는 B라는 점수를 얻기 위한 최소한의 횟수다. 그리고 다트 점수는 내가 한번 던져서 나올 수 있는 점수들을 의미한다. 그러므로 A점수를 얻기 위한 최소 횟수를 구하기 위해서는, 이전의 B점수에 대한 최소 횟수를 알면 되므로 DP로 풀 수 있는 것이다. 처음에는 [A-다트점수]=B를 이용해 A를 구하려고 했지만, 이보다 더 직.. 2024. 1. 31.
[프로그래머스/C++] 스타 수열 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 쉽게 말해 스타 수열이란 짝수 크기의 수열을 순서대로 2개씩 나누었을 때, 2개씩 나눈 집합에 전부 같은 숫자가 하나씩은 있어야 된다. (이때, 2개씩 나누었을 경우 같은 숫자가 2개 들어가 있으면 안된다) 이때 스타 수열의 크기가 가장 길 경우를 찾는 문제이므로 기본적으로 어떤 숫자가 가장 많은지 파악하는게 중요하다. 그래서 숫자의 개수를 센 다음 개수를 기준으로 정렬해서 어떤 숫자가 가장 많은지 파악해 정렬했다. ex)1: 2개, 3: 1개, 1: 1개 여기서 max값을 찾는게 아니라 정렬을 하는 이유는 숫자가 연속적으로 붙어있다면 스타 수열의 크기는 줄어들기 때문이다. ex) [0, 3, 0, 0] -> [.. 2024. 1. 31.
[프로그래머스/C++] 파괴되지 않은 건물 (2022 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 단순히 각 구간에 계산을 전부 해주면 250,000*1,000*1000이 되어 시간을 초과하게 된다. 그래서 구간을 전부 계산하는 것이 아닌, 시작 부분과 끝나는 부분에만 숫자를 더해 누적합으로 풀면 된다. 예를 들어 스킬이 [0,5,5,5,5,0]과 같이 데미지가 들어간다면, 이를 [0,5,0,0,0,-5]와 같이 표시할 수 있는 것이다. 이를 2차원으로도 확장 시킬 수 있는데 아래와 같이 변환 할 수 있다. 오른쪽의 변환된 정보를 x 축 기준으로 누적합을 계산한 다음 y축을 따라 다시 누적합을 계산하면 왼쪽과 같은 형태가 된다. 아래와 같은 순서로 압축 압축한 정보를 이용할 경우는 아래와 같이 압축해제 모든 .. 2024. 1. 29.
[프로그래머스/C++] 징검다리 건너기 (2019 카카오 개발자 겨울 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 문제를 푸는 방법이 몇 개 생각났지만, 그 중에서도 이분탐색으로 몇 명이 건널 수 있는지를 먼저 선택하고 실제로 건널 수 있는지를 체크하는 방법이 빠르다고 생각했다. 생각한 방법들 중 하나를 소개하자면, k개 만큼의 돌들을 탐색하고 그중에 max값을 찾으면 max 값을 저장하고 그 이후의 돌 부터 다시 k개 돌을 탐색해 max값이 얼마인지 찾으면서 탐색하는 방법이다. 대신 이 방법을 쓰게 되면 우선순위 queue가 필요하고, 우선순위 queue를 쓰더라도 edge case가 생길 여지가 있어 이분탐색 방법을 선택했다. 이분 탐색으로 n명이 건널 수 있다고 가정할 경우 1. 만약 n보다 같거나 작은돌이 연속으로 n.. 2024. 1. 29.
[프로그래머스/C++] 도둑질 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 완전 탐색과 같이 풀기에는 힘든 문제다. 만약 완전 탐색으로 풀 경우를 예로 들면 첫 번째 집을 털경우 세번째 집을 털거나 안털거나 경우로 나뉠텐데, 이런식으로 계산하다보면 2^n과 같은 지수형태의 시간 복잡도를 가지게 되기 때문이다. 그래서 문제를 풀기 위해서는 이전에 계산한 값들을 갱신하면서 경우의 수를 줄여 주는게 핵심이다. 1. 만약 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질 할 수 없다. 2. 바로 직전에 붙어있던 집을 도둑질 했을 경우 현재 집은 도둑질하거나 하지 않을 수 있다. 위 두 조건을 생각하면 현재 집까지 도둑질 했을 때 돈의 최댓값은 다음과 같이 나타낼 수 있다. 1. [바로.. 2024. 1. 28.
[프로그래머스/C++] 입국심사 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 문제를 봤을 때, 범위가 말이 안되기 때문에 times의 최소공배수를 구해서 나누어야하나? 생각이 들었다. 그런데 아무리 봐도 times의 범위도 매우 길 뿐더러 나눠도 해결이 안될 것이라고 생각해 다른 방법을 생각해봤다. 그 다음으로는 최소힙을 만들고 거기에 특정 심사가 만료되면 몇분이 되는지를 저장하는 방식을 생각했다. 구현만 하면 가능하겠지만, 1,000,000,000번 힙에 삽입 삭제를 하면 시간초과가 될 게 분명해서 이 방법도 넘겼다. 이렇게 힙을 생각하다보니 특정 사람의 심사가 끝나는 시간을 한명씩 넘겨가면서 구하는 것보다 반대로 특정 시간에 몇명을 심사할 수 있는지를 계산하면 되겠다는 생각이 .. 2024. 1. 26.
[프로그래머스/C++] 1,2,3 떨어트리기 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 생각보다 어려워 보였지만 생각보다 쉬웠던 문제였다. 규칙을 보면 길을 한번 지나가면 다음 길로 바뀌는 부분이 있다. 처음에는 int배열을 만들어 현재 어떤 길이 있는지 탐색하고 다음길을 가리키도록 하려고 했지만, 그냥 정렬을 한 다음 queue로 한번 지나간 길은 pop & push를 하면 길 찾기가 쉽다고 생각해 queue로 구현했다. 그렇게 한번 지나갈 때마다 어떤 leaf에 도달하는지를 구하면, 그 leaf에는 1~3의 값이 들어갈 수 있다. 이후 특정 leaf에 숫자가 들어가는게 정해질 때마다 target과 비교해 도달할 수 있는지를 비교했다. target을 만들 수 있는지 비교하는 방법은 최대.. 2024. 1. 26.
[프로그래머스/C++] n + 1 카드게임 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 카드를 구매해 원하는 숫자를 만들면서, 최대한 라운드를 길게 가기 위해서 언제 카드를 사야 하는지 묻는 문제다. 처음에는 특정 라운드에 나온 카드를 살지 말지 어떻게 판단할까 고민했는데, 카드의 길이를 보니 1000밖에 되지 않았다. 그래서 최대 1000*1000번 비교하면 해결할 수 있기 때문에 단순한 for문의 반복으로 해결했다. 먼저 당연한 말이지만 내가 동전을 사용하지 않고 가지고 있는 카드를 사용하는게 coin의 소모를 최대한 적게 하면서 round를 길게 가는 방법이다. 그래서 동전을 1개만 사용해도 되는 경우와 2개 사용해야 하는 경우로 경우를 나눴다, 단순히 for문으로 해결할 수 있는 .. 2024. 1. 24.
[프로그래머스/C++] 부대복귀 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 문제를 보고 시작 부대를 기준으로 BFS를 각각 실행하는 문제라고 생각했다가, 어떻게 반복 횟수를 줄일 수 있을까 생각하다보니 모든 부대의 destination이 동일한 게 눈에 보였다. 반대로 말하면 destination에서 BFS로 갈 수 있는 모든 부대를 탐색한다면 한번의 BFS로 문제를 해결할 수 있다. 또한 roads에서 [a, b]가 주어지면 [b, a]가 주어지지 않듯이 중복된 정보는 주어지지 않는다고 했다. 그러므로 각 부대에서 방문할 수 있는 다른 부대 정보를 2차원 vector에 push해서 저장하면 반복의 횟수도 줄어들게 된다. ​ [아이디어 정리] roads의 정보를 바탕으로 방문할 .. 2024. 1. 24.
[프로그래머스/C++] 주사위 고르기 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 주사위 숫자를 잘 사용하면 전부 비교하지 않아도 풀리지 않을까? 했는데, 그냥 비교하는게 맞는 풀이였다... A가 주사위를 선택하면 B는 남은 주사위를 갖는다. 이후 A가 선택한 주사위로 만들 수 있는 모든 경우를 구한다. (제한에 따르면 약 2 * 10C5 * 6^5 이므로 가능하다고 판단했다.) 이후 선택된 주사위에서 A와 B에서 나올 수 있는 모든 주사위의 합이 구해지면, 정렬을 한다. 정렬을 한 다음 A와 B를 비교하고 만약 A가 크면 B의 idx를 +1 한다. 만약 B가 A보다 크거나 같으면 이긴 경우의 수에 B의 idx를 더하고 A의 idx를 1 더한다. 예를 들어 아래와 같이 구해졌다면, 7과.. 2024. 1. 23.
[프로그래머스/C++] 산 모양 타일링 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] ​ 이 문제는 이전 삼각형의 개수가 다음 경우의 수에 영향을 미치므로 DP로 풀 수 있다. 그림을 그려보면 더 쉽게 점화식으로 표현 할 수 있다. 먼저 아래의 그림과 같은 도형이 있을 때, 빨간 부분을 기준으로 경우를 나눌 것이다. 빨간 선을 기준으로 경우를 나눈 이유는 아래 그림과 같이 마름모가 옆에 있는 삼각형을 침범하는 경우와 침범하지 않는 경우로 나눌 수 있기 때문이다. 그러면 이 마름모를 기준으로 옆 삼각형을 침범하는 경우와 침범하지 않는 경우를 계산해보자 (여기서 빨간색으로 칠해진 삼각형은 2개로 이루어진 마름모형 타일, 파란색 삼각형은 그냥 한개의 삼각형 타일이다.) 옆 삼각형을 침범하지 않는 경우 .. 2024. 1. 23.
[프로그래머스/C++] 사칙연산 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 DP로 풀까 고민을 하다가, 단순히 뒤에서 부터 최대 또는 최솟값을 유지하면서 계산하면 풀릴 것이란 생각이 들었다. 그래서 뒤에서 min max값 중 하나를 선택하면서 계산하도록 코드를 작성을 했는데, 안타깝게도 예외 케이스가 생겨 다시 DP로 풀기로 마음을 바꿨다. DP로 풀 때 정말 헷갈렸던 것은 부호였다. 나는 2차원 vector를 이용해 a부터 b구간의 min값과 max값을 저장했다. 문제는 min값 일 때 부호가 -면 min값에 -1을 곱해서 사용해야하나? max값에 -1을 곱해야하나? 이런 이상한 의문이 들어벼렸기 때문이다. 다행히 문제를 풀다보니 그냥 앞에 부호가 -일 경우에는 두가지 경우로 .. 2024. 1. 22.
[프로그래머스/C++] 지형 이동 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 어떻게 풀지 고민했다. 처음에는 특정 사다리를 놓을 경우 최소값만 구하려고 했는데, 그렇게 풀면 최소값을 구하는 과정에서 A, B, C 지역이 전부 연결되어야하는데 B, C지역끼리만 연결되는 경우가 생기기 때문이였다. 그래서 BFS로 사다리가 없는 지역들을 구분하고, 구분된 지역에서 다른지역으로 갈 때 사다리를 최소로 놓도록 했다. 문제를 풀다보니 모든 지역을 잇기 위해 사다리를 놓는 비용의 합이 최소가 되어야 했기 때문에 이는 MST 문제와 같은 문제라는 것을 알았다. 그래서 가장 비용이 적게 드는 사다리를 놓은 다음에, 사다리를 놓아서 새롭게 갈 수 있는 지역이 생기면 그 지역에서 사.. 2024. 1. 18.
[프로그래머스/C++] 가장 많이 받은 선물 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 문제 자체는 어려운 문제가 아니다. 단순히 +1로 더해가면서 구분만 하면 되는 문제기 때문이다. 대신 효율적인 코드를 위해 map과 split을 구현하는게 약간 어려울 수 있다. map을 사용해 친구들을 key value값으로 빠르게 2차원 vector에서 찾을 수 있도록 변환했고, split 함수를 구현해 누가 누구에게 선물을 줬는지 빠르게 파악하도록 했다. A가 B에게 선물을 주면 2차원 vector의 [A][B]에+1, [B][A]에 -1, 그리고 선물 지수의 A의 값을 +1, B의 값을 -1 하면 된다. 최종적으로 누가 선물을 가장 많이 받는지 비교를 위해 2차원 vector와 선물지수를 비교하며 계산하면.. 2024. 1. 17.
[프로그래머스/C++] 순위 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 순위가 확실한 인원들의 수를 return 하면 되는 문제다. 문제는 순위가 확실한지 파악하는 방법인데, 이는 반복을 통해 쉽게 파악 할 수 있다. A가 B를 이기면 A를 이긴 사람들은 전부 B를 이긴다. 반대로 A에게 B가 졌다면 B에게 진 사람들을 전부 A에게 진다. 그러므로 A에게 이긴 선수가 있다면, A에게 진 선수들에게도 이긴 선수의 수를 1 더해주면 된다. 반대로 A에게 진 선수가 있다면, A에게 이긴 선수들에게도 진 선수의 수를 1 더해주면 된다. 이렇게 계산하면 단순히 특정선수를 이긴 사람의 수와 진 사람의 수를 파악하는 것 만으로도 쉽게 문제를 풀 수 있다. + 위 제한사항에 보면 선수의.. 2024. 1. 17.
반응형

티스토리툴바