본문 바로가기

Algorithm

 (6)
[프로그래머스] 스킬트리 / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 코드 #include #include using namespace std; bool isMatchedFromFront(string skill, string order) { for(int i = 0; i < order.length(); ++i) { if(skill[i] != order[i]) { return false; } } return true; } int solution(string..
[프로그래머스] 배달 / 다익스트라 알고리즘 / C++ 코드 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 1번 마을에서 다른 마을까지의 최단 거리가 K 이하인 경우 '배달 가능한 마을'이다. 다익스트라로 출발 노드와 모든 노드간의 최단 거리를 찾고 거리가 K 이하인 도시의 수를 반환하면 된다. C++ 풀이 #include #include #include #define INF (9999999) using namespace std; typedef pair weight_node; in..
[프로그래머스] 네트워크 / DFS, BFS 그래프 탐색 / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 주어진 벡터 computers는 인접 행렬로 두 컴퓨터 간의 연결 상태를 표현한다. 각 컴퓨터를 노드로 하여 방문하지 않은 노드에 대해 그래프 탐색을 수행한다. 서로 연결된 노드를 탐색해가며 방문했음을 표시한다. 한 번의 그래프 탐색 호출 시 서로 연결된 모든 노드를 탐색하게 되므로 하나의 네트워크를 찾게 된다. 따라서 그래프 탐색을 호출한 횟수가 네트워크의 수 이다. C++..
[프로그래머스] 단속카메라 / 탐욕법, Greedy / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 주어진 구간에 대한 배열 routes를 정렬하고 앞에서부터 구간이 겹치게 단속 카메라를 설치할 수 있는 구간을 찾는다. 주어진 예시 [[-20, -15], [-14, -5], [-18, -13], [-5, -3]] 로 생각해보자. 위를 정렬하면 [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]이고, 정렬된 routes를 앞에서부터 살펴보면서 구..
[프로그래머스] 선입 선출 스케줄링 / 이분탐색, binary search / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12920 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 각 코어가 작업을 받을 수 있는 시각인지 확인하며 n개를 처리할 때까지 반복문을 돌리면 시간 초과가 난다. 일의 개수는 최대 50,000이고 코어의 수는 최대 10,000 개다. 최악의 경우 5억( = 50,000 * 10,000)회의 반복문이 돌기 때문에 효율성 테스트를 통과할 수 없다. 따라서 더 효율적인 방법을 생각해야 한다. 문제에서 '한 코어에서 작업이 끝나면 작업이..
[프로그래머스] 등굣길 / DP, Dynamic Programming 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42898 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 접근 물에 잠기지 않은 어떠한 지역에 대해 그 곳에 오는 방법은 바로 위쪽 지역에서 오는 방법(1)과 바로 왼쪽 지역에서 오는 방법(2)이 있다. 따라서 현재 지역으로 오는 방법의 수는 (1)과 (2)의 합으로 나타낼 수 있다. 시작 지역(집)에 오는 방법을 1로 초기화 하고 다른 지역들에 도착하는 방법의 수를 갱신해나가면 된다. 코드 #include #include #define..

티스토리툴바