본문 바로가기

전체 글236

[프로그래머스] 구명보트 (C++) 그리디 (Greedy)최대 두명이 탈 수 있으며, limit 만큼의 무게를 감당할 수 있는 구명보트가 있고, N명의 사람들의 무게를 담은 배열이 하나 주어진다. 이때 최소 필요한 구명보트 수 구하기 접근방법힌트를 얻어서 투포인터로 풀었다. 우선 배열을 오름차순으로 정렬하고,왼쪽 포인터 s, 오른쪽 포인터 e 를 배열 양 끝을 가리키도록 한 다음두 포인터가 교차될 때 까지 반복하는 반목문을 들어간다.이 반복문에서는1) 두 포인터가 가리키고 있는 값을 더했을 때 limit 이하이면, 둘다 보트에 탈 수 있으므로 두 포인터 모두 안쪽으로 옮긴다.2) 그러나 더한 값이 limit을 초과하면, 무게가 더 많이 나가는 사람만 탈 수 있다는 의미이므로 오른쪽 포인터 (e) 만 한칸 앞으로 옮긴다. (구명보트 limi.. 2024. 11. 6.
[프로그래머스] 모음사전 (C++) 완전탐색A, E, I, O, U 으로만 이루어진 단어 사전이 있다. 이 사전에 수록된 단어의 최대 길이는 5일때,특정 단어가 주어지면, 이 단어의 순서를 반환하는 문제 "A", "AA", "AAA", "AAAA", "AAAAA", "AAAAE", "AAAAI", "AAAAO", "AAAAU" 접근방법어차피 한번에 단어 한개만 주어져서 저장해두고 쓰는 것도 불필요해서, 그냥 매번 순서를 셌다..(이게맞나 암튼 완전탐색임)DFS처럼 순서대로 단어를 체크했고, 이 문제에서는 의외로(?) 관건이 언제 재귀함수를 종료할 것인가 였다.1. cnt 증가 (단어 순서)2. 찾아야할 단어의 순서인지 확인 -> 맞으면 answer = cnt 담고 함수 종료3. 단어의 길이가 5이면 함수 종료 (이래야 단어의 길이가 6인 .. 2024. 11. 5.
[프로그래머스] 주식가격 (C++) 스택/큐 (근데 이제 안쓴..) 카테고리는 그랬는데 스택이랑 큐를 쓰지 않고, 이중 for문에 중간에 나오는 것만 잘 해줘도 통과됐다..스택으로 푼 케이스를 봤는데, 로직이 어려워서 아직 100%이해하진 못하고 나왔음.. 문제는 N일에 거친 주가가 주어지고, 첫날 부터 차례로 해당 날짜의 주식가격이 떨어지기까지 얼마나 걸리는지 기간을 구하는 문제, 그래서 반환하는 값이 N일의 주가 유지기간을 담은 배열이 된다. 접근방법 스택으로 푸는 방법이 아니라 단순히 해당 날의 주식가격과 다음 날들의 주식가격을 비교하면서카운트를 증가시킨다. 이때 다음 날 중 어느 하나가 본인(해당 날의 주식가격)보다 더 떨어질 경우 반복문에서 나온다.나오면 당시 카운드를 정답 배열에 추가한다. *바로 떨어졌어도 1초?동안은 유지했다.. 2024. 11. 4.
[프로그래머스] 전력망을 둘로 나누기 (C++) 완전탐색 N개의 송전탑이 하나의 트리를 구성하며 연결되어 있는데, 간선 하나를 잘라서 두개의 트리로 분리할 때이 두개의 트리의 송전탑 개수 차가 최소가 되는 그 최소값을 반환하는 문제 두 송전탑을 잇는 간선이 이렇게 wires 라는 배열로 주어짐 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]간선은 한개씩만 주어지지만 양방향 간선임접근방법 완전탐색인 만큼..모든 간선을 잘라보면서 두 그래프의 노드 수 차이를 구해보면 된다.우선 인접행렬을 만들어서 사용했고,하나의 간선 (1,3) 을 자르면, 1로 시작해서 갈 수 있는 노드들을 모두 센다 큐를 하나 만들어서 bfs처럼 풀었음근데, 노드를 방문할 때 3이면 방문하지 않음 => 3으로부터 뻣어갈 수 있는 노드들은 방문하.. 2024. 11. 4.
[프로그래머스] 폰켓몬 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/1845 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krHash 해시폰켓몬 - [3,3,3,2,2,4] 이렇게 n개의 포켓몬?에 대해 포켓몬종 번호가 주어짐, 이중 n/2(n은 늘 짝수)개를 뽑는데, 가능한 다양한 종을 뽑을 때, 최대로 뽑을 수 있는 종의 수를 구하는 문제  접근방법- 포켓몬종 : 수 - 형식의 map을 만든다.- 그러면 최소 1개는 있는 종들로 map이 만들어짐 (즉, 없는 종은 아예 맵에 데이터가 만들어지지 않음) = map의 크기가 최대로 뽑을 수 있는 종의 수- 이 존재하는 최.. 2024. 10. 31.
[프로그래머스] 순위 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그래프 Graph경기결과(a승 b패)가 주어지면, 정확한 순위를 알 수 있는 선수의 수를 반환하는 문제 접근방법첨에 진짜 막막했는데, 선수들의 경기를 간선으로 그래프를 이어보면 본인의 부모노드갯수(본인보다 점수가 높은) + 자식노드갯수(본인보다 점수가 낮은) 값이 총 선수의 수 n - 1(본인) 과 같으면 본인의 순위가 분명한 경우인 것을 고려해서 풀 수 있는 문제다. 인접행렬 두개를 만들어서, 하나는 각 노드의 부모노드를 저장하는 2차원 배열,.. 2024. 10. 31.
[프로그래머스] 더 맵게 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krHeap 힙 (우선순위 큐)n개의 음식의 스코빌지수가 배열로 주어지고, 이 음식들의 최소 스코빌 지수가 K이상이 되도록 음식을 섞을 수 있다고 할 때, 최소 몇번 섞어야 하는지 반환하는 문제. (모든 음식을 섞어도 스코빌지수가 K를 넘지 않는다면 -1을 반환)음식을 섞는 다는 것은, 섞인 음식의 스코빌 지수 = 최저스코빌지수 음식의 스코빌 지수 + 두번째로 스코빌지수가 최저인 음식의 스코빌 지수*2 이다.  접근방법 갱신되는 음식들의 스코빌지수를.. 2024. 10. 31.
[프로그래머스] 가장 먼 노드 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그래프 Graph  이런식의 그래프가 주어집니다. 간선에 붙은 가중치는 없구요. 양방향 간선이고, [점1, 점2] 을 요소로 갖는 배열이 하나 주어짐. 노드는 n개, 노드 번호는 1~n. 이때, 1로 부터 최단 경로가 가장 먼 노드는 몇개인가.즉, 1을 제외한 모든 노드에 대해 1부터 해당 노드까지 도달하는 최단 경로를 구하고, 그 중 가장 먼 거리에 있는 노드는 몇개인지 묻는 문제.즉, (ㅇㄴ) 최단 경로 중에 최댓값을 뽑고, 이 최댓값이랑 거.. 2024. 10. 31.
[프로그래머스] 정수 삼각형 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krDP 동적계획법 이런 정수 삼각형이 2차원 벡터 배열로 주어지고, 대각선 왼쪽 한칸 혹은 오른쪽 한칸으로만 이동하면서 내려갈 수 있다고 할 때, 거치는 수들의 합이 최대값을 반환하는 문제.         접근방법2차원 배열을 똑같은걸 하나 복사해두고, 이걸 각 위치까지 오는데 거친 수들의 합의 최댓값을 저장해두는 용도로 사용한다. (accTri) = 최대누적트리라고 하겠다.그리고 맨위에서 부터 맨 마지막 바로 전 줄까지 보면서, 내가 갈 수 있는.. 2024. 10. 30.
[프로그래머스] 섬 연결하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/42861?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr그리디N개의 섬과 그 섬을 잇는 다리 건설 정보가 2차원 배열로 주어진다.costs배열은 (출발점, 도착점, 비용)을 원소로 갖는 배열임이때, 모든 섬이 서로 연결되도록 다리를 설치하는 데 드는 최소비용을 반환하는 문제 접근방법처음에는 DFS로 풀어보려고 했다가 안돼서 그리디 문제 답게 그리디하게 풀었다 (?)목적은 1) 새로운 섬을, 2) 적은 비용으로 가는 것.그래서 이미 방문한 섬으로부터 갈 수 있는 섬들 중, 가장 .. 2024. 10. 29.
[프로그래머스] 피로도 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=swift 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr완전탐색 (DFS)N개의 던전을 탐색하는 문제인데, k만큼의 체력을 갖고 있을 때, 각 던전에 들어갈 때 필요한 체력과, 각 던전을 들어갔을 때 실제로 사용되는 체력이 주어지고, 최대한 많은 던전을 탐색할 수 있는 경우를 구하는 문제탐색 순서가 달라질 수 있다는 게 문제다 접근방법dfs 재귀 방식으로 풀었는데, 종료조건을 어떻게 두어야 할지 고민했다. 그래서 처음에는 모든 던전을 실제로 들어갔거나, 더이상 들어갈 수 있.. 2024. 10. 28.
[백준 1916] 최소비용 구하기 (C++) https://www.acmicpc.net/problem/1916다익스트라도시를 연결하는 단방향 버스 (출발점, 도착점, 비용)이 주어지고임의의 출발점과 도착점이 주어졌을 때, 이 둘을 잇는 최소 비용을 출력하는 문제 접근방법 음수인 비용이 없어서 다익스트라로 풀어도 된다. (벨만포드로 안풀어도 됨)이거 풀다가 내가 다익스트라를 제대로 이해하고 있는게 맞나 의심했음..다시 공부해야 할 것 같다..다익스트라 기본 개념은 임의의 출발점 하나에 대해 모든 노드에 대한 최소 거리를 저장하고 있는 1차원 배열이 하나 있고,방문한 노드를 하나씩 추가해 가면서 이 배열을 갱신하는 방식이다. 이 문제를 풀 때는,- 인접행렬 (각 노드에 대해 연결된 버스 노선을 담고 있는 2차원 배열. ex. 1번: {(2번도시, 비용.. 2024. 10. 23.