본문 바로가기
반응형

Algorithm292

[프로그래머스/C++] 보석 쇼핑 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 이 문제는 연속 된 구간을 선택하고 모든 종류의 보석을 전부 구매할 수 있는지를 계산하는 문제다. 구간을 2중 for문으로 탐색할 경우 O(N^2) 이지만, 누적 합과 비슷하게 특정 자리의 보석이 빠지거나 들어올 때, 그 보석의 개수를 고려하면 쉽게 풀 수 있는 문제다. 먼저 모든 종류의 보석의 수를 구한다. 그리고 구간의 시작지점 st와 끝나는 지점 ed를 정한다. 이후 처음 보석부터 모든 종류의 보석이 모일때까지의 구간을 구한다. 이제 모든 종류의 보석이 모였다면 st를 한 칸씩 앞으로 당기면서 보석을 뺀다. 만 보석을 뺐는데 그 보석의 수가 0이라면, 모든 보석을 구매할 수 없는 경우이므로, 구간의 끝인 e.. 2024. 2. 7.
[프로그래머스/C++] 등대 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 주의해야하는 점이 A와 B 등대가 있다면 두 등대 중에 한 등대는 무조건 켜져있어야 한다는 점이다. 위 그림과 같이 등대가 켜져 있어도, A와 B 등대 사이에 불이 켜져있지 않기 때문에 정답이 될 수 없다. A와 B 등대중 하나가 켜져있어야 된다. 이제 문제를 풀때 사이클이 없으므로 하나의 트리로 볼 수 있다. 이를 이용해 1을 트리의 최상단 노드라고 가정하고, leaf 노드를 찾는다. 여기서 leaf 노드를 찾을 경우 leaf 노드의 불을 켜는 것 보다 부모 노드의 불을 켜는게 더 좋다. 왜냐하면 leaf 노드는 연결된 노드가 하나이고, leaf 노드의 부모 노드는 최상단 노드인 1을 제외하면 연결된.. 2024. 2. 7.
[프로그래머스/C++] 베스트앨범 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 stl중 map을 사용하면 쉽게 풀 수 있는 문제다. map을 이용해 장르별로 재생 횟수를 더해 계산을 한다. 그리고 map을 하나 더 만들어 장르별로 index의 위치와 재생횟수를 저장하는 vector를 value로 만든다. 이렇게 두개의 map을 만든 뒤, 장르별 재생 횟수를 저장한 map을 vector로 변환해 정렬한다. 재생 횟수가 많은 순서대로 정렬된 map을 이용해 가장 재생횟수가 많은 장르부터 for문을 돌린다. for문을 돌리면서 장르별로 index와 재생횟수가 저장된 map을 다시 재생횟수 순서로 정렬하면 된다. (이때, 장르별로 index와 재생 횟수를 vector에 넣을때 index.. 2024. 2. 6.
[백준/C++] 6086번 - 최대 유량 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 network Flow문제와 같다. 같은 지점에서 같은 지점으로 연결된 관은 병렬연결이므로 흐를 수 있는 유량에 더해준다. 그리고 양방향으로 흐를 수 있다고 했으므로 이 점도 고려해 흐를 수 있는 유량에 더해주면, Network Flow 문제가 된다. ​ Network Flow 문제를 푸는 방법을 간단하게 소개하면 1. 유량 보존의 법칙 유체가 나오는 부분을 source, 들어오는 부분을 sink라고 하는데, 이 두 부분을 제외하고는 각 정점에서 들어오는 유량과 나가는 유량이 일치해야 한다. 2. 유량의 대칭성 f(u, v) = A 가 u에서 v로 A 만큼 유체가 흐르는 것을 의미한다고 하자. 그러면 .. 2024. 2. 5.
[프로그래머스/C++] 보행자 천국 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제풀이] 이 문제는 아래와 오른쪽으로만 차량이 이동할 수 있다. 그리고 통행이 전부 가능한 구간과 차량의 통행이 금지된 부분, 우회전 및 좌회전을 하지 못하는 구간 3개로 나눠져 있다. 그러므로 내가 원래 아래방향으로 이동하고 있었는지, 오른쪽 방향으로 이동하고 있었는지를 알고 있으면 쉽게 풀 수 있다. 그래서 내가 원래 이동하는 방향이 아래방향인 경우의 수를 기록할 2차원 vector와 오른쪽 방향으로 이동하던 경우를 기록할 2차원 vector를 만들었다. 그리고 for문을 돌려 현재 위치가 모든 차량이 이동가능한 부분이라면, 내 위치에서 아래로 가는 차량과 오른쪽으로 가는 차량의 수를 합쳐 아래와 오른쪽으로 이동하는 차.. 2024. 2. 4.
[프로그래머스/C++] N으로 표현 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 횟수가 8이라 DFS로 쭉 풀어도 되겠다는 생각이 들었다. DFS로 풀 경우 현재 숫자 Num과 NNN, 111과 같은 숫자들을 DFS로 연산하기만 하면 된다. 왜냐하면 N으로 특수하게 만들 수 있는 숫자들로 계산을 다 해주었기 때문에, 연산하는 과정에 다 포함이 되기 때문이다. 문제를 풀고 나서 다른 사람의 풀이를 보니 DP를 이용해 푼 풀이들이 보였다. T번 써서 만든 숫자들 = [T-n번 써서 만든 숫자들] (사칙연산) [n번 써서 만든 숫자들] 과 같은 형태로 풀었는데, 이렇게 보니 좀 더 풀이가 깔끔해 보였다. 문제가 크게 어렵진 않았는데, 연산을 코드로 작성하는게 그냥 좀 오래.. 2024. 2. 2.
[프로그래머스/C++] 재밌는 레이싱 경기장 설계하기 (2023 현대모비스 알고리즘 경진대회 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음에 이 문제를 봤을 때, 적당히 잘 자른다음 옆으로 밀면서 비교하면 되지 않을까?라고 생각했다. 그런데 옆으로 밀면서 비교해도 특수한 경우가 있어서, 단순 비교로는 풀 수 없을 것이라 생각하고 다른 사람의 힌트를 참고 했다. 알고보니 풀이는 비슷한데 숫자의 개수가 홀수인 경우와 짝수인 경우를 구분해서 생각해야했다. 나는 계속 홀수개의 숫자에서 고민을 하다보니 어려웠던 것이다... [문제 풀이] 먼저 숫자가 짝수개일 때는 정렬을 한 다음 절반을 나눠서 비교하면 된다. [짝수일 경우] 아래 그림과 같이 한 다음 숫자의 배치를 b1, a1, b2, a2 순서로 배치한다. 여기서 a1을 먼저 배치하지 않고 b1을 배치하는 이유는 .. 2024. 2. 2.
[프로그래머스/C++] 가장 긴 팰린드롬 (feat. Manacher's Algorithm) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보자마자 O(n^2)으로 해결 되겠다고 생각이 들었다. 문자열의 사이즈가 작았기 때문이다. 하지만 더 효율적인 알고리즘이 뭐가 있을까 찾아보다가 Manacher's Algorithm을 알게 됐다. Manacher's Algorithm을 처음 봤을 때, 설명이 많이 복잡하다는 생각이 들었다. [참고] https://www.crocus.co.kr/1075 https://m.blog.naver.com/jqkt15/222108415284 즉 Manacher's Algorithm을 요약하면 이전에 Palindrome인지 체크한 것을 이용한 것이다. for문으로 앞에서 부터 문자열이 Palindrome인지 체크하.. 2024. 2. 1.
[프로그래머스/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.
반응형

티스토리툴바