본문 바로가기

전체 글238

[프로그래머스] 등굣길 (C++) 탐욕알고리즘 (Greedy)n*m 그리드에서 1,1부터 n,m까지 가는 최단 경로의 경우의 수를 1000000007 로 나눈 나머지를 반환하는 문제가는 경로에 침수된 지점이 k 개 주어진다 (좌표로 주어짐) 접근방법n*m만큼의 2차원 배열 map을 만들고, 0으로 초기화한 후, 침수된 지점은 -1로 표시한다.1,1부터 n,m까지 순회하면서 각 자리에 이 지점까지 오는 경우의 수를 저장한다.즉, r,c 지점은 한칸 왼쪽 자리까지 오는 경우 + 한칸 위쪽 자리까지 오는 경우, 이 두 경우의 수를 합한 경우다.1,1자리에 처음에 1을 넣고 차례로 순회하고나면 n,m에는 학교까지 오는 데 최단거리의 경우의 수가 담긴다.(최단거리인지 체크하지 않는 이유는, n과 m이 1보다 크거나 같고, 오른쪽과 아래쪽으로 밖에.. 2024. 11. 8.
[프로그래머스] 단속카메라 (C++) 탐욕알고리즘 (Greedy)N개의 차량의 진입지점과 진출지점이 주어지면 모든 차량을 단속할 수 있는 단속카메라의 최소 설치 개수를 반환하는 문제 접근방법진출지점을 기준으로 먼저 나가는 차가 앞에 오도록 차들을 정렬한 후에,첫번째 차 부터 이 차가 나가는 지점에 단속카메라를 설치한다고 할 때, 차례로 차를 순회하며 현재 단속카메라가 단속할 수 있는 차량인지 확인한다.= 반복문에서 가리키고 있는 차의 진입지점이 현재 단속카메라의 위치와 같거나 그 전에 위치하면,해당차는 이미 단속할 수 있으므로 넘어가고,만약, 이 차의 진입지점이 현재 단속카메라의 위치보다 이후에 위치한다면, 해당 카메라로는 단속할 수 없으므로 다시 이 차의 진출지점에 단속카메라를 설치하고, 단속카메라의 총 개수를 1 추가한다. 이렇게 반복문.. 2024. 11. 7.
[프로그래머스] 구명보트 (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.

티스토리툴바