본문 바로가기

■ 알고리즘 문제 풀이/프로그래머스

 (10)
[프로그래머스] 주식가격 ▶문제설명코딩테스트 연습 > 스택/큐 > 주식가격https://programmers.co.kr/learn/courses/30/lessons/42584 ▶ 설계prices의 길이가 2 이상 100,000이하이고,prices에 저장된 각 가격은 1 이상 10,000이하의 자연수이다. 2중 for문으로 일일이 확인하도록 구현하는 방법이 가장 먼저 떠올랐다.이렇게 나이브한 알고리즘으로 문제를 해결한다고 하면100,000개의 가격 각각에 대해 1초에 가격이 1부터 1씩 증가한다고 했을 때 최대 10,000번을 확인하게 된다.1부터 10,000까지 1씩 증가시키고 그 다음 또 1부터 10,000까지 1씩 증가시키는 것을 반복했다고 한다면따라서, 최악의 경우에 대략적으로 100,000 * 10,000 = 1,000,..
[프로그래머스] 네트워크 ▶문제설명코딩테스트 연습 > DFS/BFS > 네트워크 https://programmers.co.kr/learn/courses/30/lessons/43162 ▶ 설계DFS로 해결이 가능한 문제이다. 2차원 벡터 매개변수인 computers는 인접행렬로 정점들 사이의 간선 여부를 나타낸다. 문제에서 연결 요소를 네트워크라고 표현했을 뿐, 그래프의 연결 요소의 개수를 세서 리턴하는 문제라고 생각하면 된다. 네트워크가 몇 개인지를 구하는 함수의 시그니처를 정의해보자. 123void findNetworkNum(int n, int nowComputer, const vector& computers, vector& visited){ }Colored by Color Scriptercs 매개변수명 의미 n 컴퓨터의 개수..
[프로그래머스] 카펫 ▶문제설명코딩테스트 연습 > 완전탐색 > 카펫https://programmers.co.kr/learn/courses/30/lessons/42842 ▶ 설계brown와 red의 값에 따라서 카펫의 가로, 세로 크기를 리턴해야 하는 함수이다.단순히 가능한 가로, 세로의 길이를 2중 for문으로 완전탐색하면 풀릴 것으로 보인다. ▶ 구현우선 2중 for문으로 가능한 가로, 세로 길이를 모두 탐색하도록 하자. 123456789vector solution(int brown, int red) { vector answer; for(int w=1; w
[프로그래머스] 단어 변환 ▶문제설명코딩테스트 연습 > DFS/BFS > 단어 변환 https://programmers.co.kr/learn/courses/30/lessons/43163 ▶ 설계DFS 탐색으로 문제를 해결해보자. 한 번에 한 개의 알파벳만 바꾸어서 word에 있는 단어 중 하나로 변환할 수 있는지 모든 경우를 탐색해보면 되는 문제이다. 복잡한 것 없이 문제에서 요구하는데로 재귀 함수만 잘 구현하면 간단히 해결될 것으로 보인다. ▶ 구현 우선 재귀함수의 매개변수와 리턴타입을 정해보자. 12345int findWord(string nowWord, const string& targetWord, const vector& words, int cnt){ int answer = 987654321; return answer;}C..
[프로그래머스] 소수 찾기 ▶문제설명코딩테스트 연습 > 완전탐색 > 소수 찾기 https://programmers.co.kr/learn/courses/30/lessons/42839 ▶ 설계number의 길이를 n이라고 하자. n개의 숫자들 중에 1 ~ k 개를 뽑아서 순열을 생성한 뒤 정수로 변환하고 해당 정수가 중복되지 않도록하여 소수인지 아닌지 판별해서 개수를 반환하는 함수를 구현해야 한다. 조합의 경우에는 순서를 고려하지 않고 k개를 뽑아내므로 조합만으로는 풀 수 없다. (간단히 예를 들면 1, 3, 2 를 뽑아낼 뿐이지 132, 123, 213, 231, 312, 321와 같이 순열을 뽑아내는 방법이 아니기 때문이다.) n개의 숫자들 중 k개를 뽑아서 순열을 만들기 위해서 재귀함수를 구현하면 될 것으로 보인다. 123456..
[프로그래머스] 다리를 지나는 트럭 ▶문제설명코딩테스트 연습 > 스택/큐 > 다리를 지나는 트럭 https://programmers.co.kr/learn/courses/30/lessons/42583 ▶ 설계트럭을 구조체로 관리하자. 그리고 다리 위에 있는 트럭들을 queue 자료구조로 관리하자. 여러 대의 트럭이 한 시간에 동시에 다리 위로 올라가는 경우는 없으니 도착할 시간이 중복되는 경우는 없다. 시간을 1초씩 증가시키면서 모든 트럭들이 다리를 지날 때까지 반복하면 될 것으로 보인다. commingTrucksQ의 front에 있는 트럭이 도착할 시간이 되었을 때 하나씩 pop해주자. 그러기 위해서 구조체에 도착 시간을 나타내는 arrivedTime이 필요하다. 또한, 다리 위에 올라와있는 트럭이 빠져나갈 때 그 트럭의 무게를 알아야 현..
[프로그래머스] 여행경로 ▶문제설명코딩테스트 연습 > 깊이/너비 우선 탐색 > 여행경로 https://programmers.co.kr/learn/courses/30/lessons/43164 ▶ 설계재귀 함수를 잘 구현하면 해결할 수 있을 것 같다. 재귀 함수의 종료 조건은 모든 티켓을 다 사용했을 경우이다. 전역변수 N에 티켓의 개수를 저장하자. 12345678bool findPath(vector& answer, vector tickets, string city, int cnt) { if(N==cnt) return true; return false; }Colored by Color Scriptercs 문제에서 경로가 여러개인 경우 사전순으로 빠른 경로를 출력하라고 했으므로 sort(tickets.begin(), tickets.e..
[프로그래머스] 기능개발 ▶문제설명코딩테스트 연습 > 스택/큐 > 기능개발 https://programmers.co.kr/learn/courses/30/lessons/42586 ▶ 설계0%로 시작하고 하루에 1%를 채울 수 있는 작업이 있다면 100일이 필요하다. 그러므로 100번 반복하는 루프문 안에서 구현을 이어나가면 되겠다. 완료된 작업이 있는지 확인하기 위한 구간을 begin과 end로 나타낸다. [begin, end) 매일 begin에서부터 연속되어 있는 진행률 100% 이상의 작업들을 확인하고 answer에 추가한 뒤, begin을 업데이트 해주자. ▶ 구현 하루가 지날 때마다 입력으로 주어진 모든 작업들을 주어진 속도에 맞추어 진행률을 업데이트했다. 그리고 begin에 위치한 작업이 100% 이상이 된 경우에 beg..

티스토리툴바