[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++ 힙(Heap) - 이중우선순위큐

[Programmers] C++ 힙(Heap) - 이중우선순위큐 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의 원소는 큐가 수행할 연산을 나타냅니다. 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무..

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

[Programmers] C++ 스택/큐 - 주식가격

[Programmers] C++ 스택/큐 - 주식가격 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았..

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