본문 바로가기
반응형

C++245

[프로그래머스/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.
[프로그래머스/C++] 도넛과 막대 그래프 (2024 KAKAO WINTER INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 그래프의 모양을 파악하는 문제다. 자세히 보면 막대그래프는 순환하지 않고, 8자 그래프는 나가는 간선이 2개가 있는 특이점을 발견할 수 있다. 이를 활용하면 그래프의 모양이 어떤 모양인지 쉽게 파악할 수 있다. 그래프를 돌면서 만약 간선이 2개인 점이 나오면 그 그래프는 8자 그래프, 나가는 간선이 없으면 막대 그래프, 만약 다시 시작했던 노드로 돌아오면 도넛 그래프다. 생점의 특이사항은 들어오는 간선이 하나도 없다는게 특징이다. 문제는 막대그래프의 끝점에서도 이러한 특징이 나타날 수 있는데, 제한사항에 보면 적어도 두개의 그래프를 생점에서는 생성하므로, 나가는 간선의 길이가 2보다 크거나 같으면서 들.. 2024. 1. 16.
[프로그래머스/C++] 카드 짝 맞추기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 카드 짝을 맞추는 최소 횟수를 구하면 되는 문제다. 그렇기 때문에 이동횟수가 최소가 되는 경우를 구하기 위해서는 BFS로 a에서 목적지까지 가는데 걸리는 입력 횟수가 최소가 되도록 계산하면 된다. 그리고 카드를 뒤집는 순서도 게임에 중요하다 예를 들면 a카드를 뒤집고 b카드를 뒤집는 경우와 b카드를 뒤집고 a카드를 뒤집는 경우가 최소 횟수가 다를 수 있다는 의미다. 그래서 카드의 순서에 대한 모든 경우를 구해 카드를 뒤집는 순서를 구하고, 그 순서에 따라 BFS로 최소 횟수를 구했다. 이후 모든 경우에 대해 입력이 최소가 되는 횟수를 return하면 된다. [아이디어 정리] 카드를 뒤집는 순서에 대한 .. 2024. 1. 16.
[프로그래머스/C++] 표현 가능한 이진트리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 이 문제는 이진트리로 특정 수를 표현이 가능한지 풀면 되는 문제다. 이진트리로 특정 수를 표현하기 위해서는 자식 노드가 1일 때, 부모의 노드가 0이 되면 안되기만 하면 된다. 문제는 특정 자식 노드의 부모노드가 0인지 확인을 하기 위해서 어떤 노드가 부모노드 인지를 잘 알아야한다. DFS로 이진트리가 잘 연결되어 있는지 구해도 되지만 처음에 보자마자 부모노드만 잘 정해준다면 제한 된 범위에서 만들어지는 이진트리의 깊이가 깊지 않아 빠르게 구할 수 있다고 생각했다. 문제는 부모노드를 구하는 방법인데 맨 아래 1층과 그 부모인 2층을 비교하면 왼쪽 자식 노드(1층) = 부모노드 - (2층/2) 오른쪽 자식 노드(1층) .. 2024. 1. 15.
[프로그래머스/C++] [1차] 추석 트래픽 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 정렬을 한 뒤, deque를 써서 문제를 풀었다. 특정 시간에 최대 몇개가 포함되어 있는지 풀면 되는 문제기 때문에 먼저 시작 시간을 기준으로 정렬을 했다. 이후 시작시간을 기준으로 정렬을 했기 때문에 끝나는 시간이 deque의 맨 앞에 저장 된 시작 시간 보다 더 크다면 마찬가지로 같은 시간에 처리가 되고 있다는 뜻이다. 이후 끝나는 시간이 가장 빠른 처리가 맨 앞으로 와야 하므로 deque의 원소와 비교해 처리가 끝나는 시간을 비교하고 올바른 위치에 삽입했다. 위치를 바꿔서 삽입해도 되는 이유는 항상 deqeu의 맨 앞에 끝나는 시간이 가장 빠른 트래픽이 오도록 정렬해 두었기 때문에 가능한 것이다. ​ [아이.. 2024. 1. 14.
[프로그래머스/C++] 올바른 괄호의 갯수 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 처음에는 memoization을 이용해 풀려고 했는데 n의 개수가 적어서 단순 재귀로 풀었다. 열린 괄호를 넣는 경우와 닫는 괄호를 넣는 경우로 나눌 수 있는데, 만약 열린 괄호를 넣게 된다면 사용할 수 있는 열린 괄호의 개수를 1만큼 줄이고 닫힌 괄호의 사용횟수를 1 늘리면 된다. 이후 두 경우의 합을 더하면 현재 열린 괄호와 닫힌 괄호를 사용할 수 있을 때 몇개의 경우의 수가 나오는지 결과를 알 수 있다. ​ [아이디어 정리] 열린 괄호의 개수가 0보다 크면 열린 괄호를 사용하고, 닫힌 괄호의 사용횟수를 1 늘린다. 만약 닫힌 괄호의 개수가 0보다 크면 닫힌 괄호를 사용하고 닫힌 괄호의 사용횟수를 1 줄인다. 위 .. 2024. 1. 13.
[프로그래머스/C++] 쿠키 구입 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [풀이] 쿠키의 길이가 최대 2000이기 때문에 시작점과 끝 점을 고르면 이분탐색으로 절반으로 나눌 수 있는지 쉽게 구할 수 있다고 생각했다. 그리고 계속 반복해서 시작점과 끝점을 더하는 계산이 나오지 않도록 부분합을 이용해 반복 덧셈을 줄였다. 쿠키의 시작점과 끝점이 주어지면 먼저 쿠키의 개수의 총합이 홀수인지 짝수인지 확인한다. 홀수인 경우는 절반으로 나눌 수 없으므로 패스한다. 짝수일 경우는 이분탐색으로 쿠키를 절반으로 나눌 수 있는지 탐색하면 된다. ​ [아이디어 정리] 쿠키의 부분합을 구한다. (반복 덧셈을 줄이기 위해서) 시작점과 끝점을 기준으로 이분탐색을 해 쿠키를 절반으로 나눌 수 있는지 구한다. 쿠키를 절반으로.. 2024. 1. 12.
[프로그래머스/C++] 아이템 줍기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] ​ 이 문제는 겹친 사각형으로는 캐릭터가 이동할 수 없다는게 핵심이다. 그래서 겹친 사각형의 경로를 없애주고, 없앤 다음 만들어진 경로를 BFS로 탐색하면 쉽게 풀리는 문제다. BFS로 탐색하는 것은 쉽지만, 어떤 경로를 이동할 수 있는지를 구하는게 생각보다 어려웠다. 처음에는 사각형의 좌표를 기준으로 겹쳐있는지를 보고 겹친 부분을 조건에 따라 삭제하려고 했다. 하지만 코드가 생각보다 길어질 것 같아서, 잘 생각해보니 겹칠 경우는 조건을 잡을 필요없이 겹친 부분을 0으로 없애면 실제로 가능한 경로만 남게 된다는 사실을 알았다. 그래서 하나의 사각형에서 이동이 가능한 경로를 그리고, 그 사각형의 경로 위에 다른 사.. 2024. 1. 11.
[프로그래머스/C++] 섬 연결하기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 섬과 섬을 연결하는 다리를 건설해 모든 섬을 이을 때, 최소 비용을 구하는 문제다. 이전에 풀었던 최소 신장 트리 문제와 똑같은 문제다. [SWEA/Python] 5249 - 최소 신장 트리 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 노드와 간선의 수가 주어지면 이 그래프로 부터 최소 신장트리를 만들고 최소신장트리를 구성하는 간선의 가중치를 모두 더하는 문제다. HTML 삽입 codingjj.tistory.com HTML 삽입 미리보기할 수 없는 소스 [풀이 요약] 섬위 범위가 100이기 때문에, 프림 알고리즘이나 크루스칼 알고리즘에서 사용하는 유니온, 우선순위 큐 등을 사용하지 않고 반복으로도 쉽게 풀릴 것이라 생각했다. [아이디어 정.. 2024. 1. 9.
[프로그래머스/C++] 단속카메라 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 특정 구간을 지나는 모든 차량이 단속용 카메라를 만다록 하는 문제다. 이전에 풀었던, 요격 시스템이라는 문제와 매우 비슷하다. [프로그래머스/Python] 요격 시스템 HTML 삽입 미리보기할 수 없는 소스 [문제 설명] ​ A나라가 B나라를 침공했다. 요격 시스템이 있지만 비용이 있어서 요격 횟수를 최소로 해야하기 때문에 미사일의 요격을 최소로 하는 횟수를 구 codingjj.tistory.com HTML 삽입 미리보기할 수 없는 소스 이 문제는 greedy 하게 풀 수 있다. 특정 구간을 지나서 무조건 새로 카메라를 달아야 하는 구간이 오면 새로 비교하던 데이터들을 갱신하고, 다시 카메라가 차량들을 단속할 수 있는지 판단하면 된다. 이전에는 시.. 2024. 1. 8.
[프로그래머스/C++] 네트워크 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] ​ 컴퓨터와 컴퓨터가 연결되어 있으면 하나의 네트워크로 본다. 만약 A와 B컴퓨터 B와 C컴퓨터가 연결되어있다면, 하나의 네트워크로 간주한다. 컴퓨터간의 연결이 2차원 vector로 주어지면 컴퓨터들 간의 총 네트워크의 수는 얼마인지 return 하면 되는 문제다. HTML 삽입 미리보기할 수 없는 소스 컴퓨터의 개수가 최대 200개로 크지 않았기 때문에 DFS로 쉽게 풀 수 있다는 생각이 들었다. 그래서 이미 네트워크로 체크했는지 검사하는 isNet이라는 1차원 vector를 이용해 DFS로 문제를 풀었다. 하나의 컴퓨터와 연결된 컴퓨터는 이미 연결된 네트워크인지 체크를 했다고 처리를 하는 것이다. ​ [아이디어 정리] 컴퓨터의 개수만큼 for문을 .. 2024. 1. 7.
반응형

티스토리툴바