[Programmers] C++ 탐욕법(Greedy) - 구명보트

[Programmers] C++ 탐욕법(Greedy) - 구명보트 문제 설명 보트 한 번에 최대 2명이라고 제한되어있어서 난이도가 높지 않은 문제였던 것 같다. 먼저 주어진 `vector people`을 낮은 몸무게부터 오름차순으로 정렬해주었다. 다른 사람들의 풀이를 보니, 투포인터 방식으로 풀면 조금 더 깔끔하지 않았을까 싶은데 나는 조금 복잡하게(?) deque 방식으로 풀었다. 가장 낮은 몸무게, 가장 높은 몸무게 하나씩 좌우로 빼기 위해서 이 자료구조를 사용하기로 선택했다. 가장 낮은 몸무게(min)를 기준으로 삼아서, 만약 max와의 합이 `limit`을 넘지 않는다면 둘을 각각 deque에서 빼고, `answer++` 해주었다. 만약 `limit`을 넘게 된다면, min을 다시 deque에 p..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 19.
• textsms

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 여행경로 문제 설명 가능한 경로가 2개 이상일 경우, 알파벳 순서가 앞서는 경로를 return 해야하기 때문에 tickets배열을 우선 정렬한다. 정렬한 tickets배열을 DFS로 돌고, tickets를 다 돌았을 경우가 답이 된다. 만약 tickets를 다 돌기도 전에 DFS가 끝나게 되면 백트래킹으로 마지막을 하나씩 가지치기 하면서 답을 구한다. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 18.
• textsms

[Programmers] C++ 동적계획법(DP) - 등굣길

[Programmers] C++ 동적계획법(DP) - 등굣길 문제 설명 문제 자체는 사실 어렵지 않다. 물웅덩이는 계산에 포함되지 않도록 미리 visited 처리 해놓고, 오른쪽, 아래쪽으로만 움직일 수 있기 때문에 DP(i,j) 에서 DP(i-1, j) + DP(i, j-1) 값을 할당해주면 된다. 격자 크기 m, n 도 각각 100 이하 값이고 물에 잠긴 지역(puddles)도 0개 이상 10개 이하이기 때문에 값 자체가 다 작아서 별 생각 안하고 풀 수 있다. 제한사항 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다. m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다. 물에 잠긴 지역은 0개 이상 10개 이하입니다. 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다. 풀이 (..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 16.
• textsms

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 아이템 줍기

[Programmers] C++ 깊이/너비 우선 탐색(DFS/BFS) - 아이템 줍기 문제 설명 겹쳐진 다각형 도형의 테두리를 따라서 시작점 ~ 도착점 까지의 최소 거리를 구하는 문제이다. 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없다. 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없다. 지형이 2개 이상으로 분리된 경우도 없습니다. 한 직사각형이 다른 직사각형 안에 완전히 포함되는 경우 또한 없다. 풀이과정 아무리 머리를 굴려도 마땅한 방법이 생각나지 않았다. 한 문제를 가지고 1시간 가량 고민을 했는데 명쾌한 아이디어가 떠오르지 않아서 구글링을 통해 블로그에 정리를 잘 해주신 분들의 풀이 도움을 받았다. | 핵심 아이디어는 모든 변수값에 2배를 ..

• format_list_bulleted Algorithm/C,C++
• · 2024. 4. 14.
• textsms

[Programmers] C++ 2024 Kakao Winter Internship - 가장 많이 받은 선물

[Programmers] C++ 2024 Kakao Winter Internship - 가장 많이 받은 선물 문제 설명 선물을 직접 전하기 힘들 때 카카오톡 선물하기 기능을 이용해 축하 선물을 보낼 수 있습니다. 당신의 친구들이 이번 달까지 선물을 주고받은 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하려고 합니다. 두 사람이 선물을 주고받은 기록이 있다면, 이번 달까지 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물을 하나 받습니다. 예를 들어 `A`가 `B`에게 선물을 5번 줬고, `B`가 `A`에게 선물을 3번 줬다면 다음 달엔 `A`가 `B`에게 선물을 하나 받습니다. 두 사람이 선물을 주고받은 기록이 하나도 없거나 주고받은 수가 같다면, 선물 지수가 더 큰 사람이 선물 지수..

• format_list_bulleted Algorithm/C,C++
• · 2024. 3. 13.
• textsms

[Programmers] C++ 이분탐색 - 입국심사

[Programmers] C++ 이분탐색 - 입국심사 문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 ..

• format_list_bulleted Algorithm/C,C++
• · 2024. 2. 6.
• textsms