본문 바로가기

알고리즘 문제풀이246

[프로그래머스] 폰켓몬 (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.
[프로그래머스] 다리를 지나는 트럭 (Swift) https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr스택/큐 (Queue)N대가 올라갈 수 있는 다리가 있고, 이 다리는 W만큼의 무게만 견딜 수 있음.이때, 대기하고 있는 M개의 트럭의 무게가 순서대로 담긴 배열이 주어진다.1초에 한칸씩 이동할 수 있다는 설정이 있는듯(ex. 트럭이 1개여도 다리 길이가 100이면 101초가 걸림)이때 모든 트럭이 다 다리를 건더는 데 몇초가 걸리는지 반환하는 문제(모든 트럭 한 대의 무게는 W 이하이다 = 못올라가는.. 2024. 10. 22.
728x90

티스토리툴바