본문 바로가기

C++

 (10)
[프로그래머스] 스킬트리 / 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++ 풀이 / 자료구조 풀이 전략 priority_queue 두 개를 활용해서 풀 수도 있을 것 같지만 포인터 복습할 겸 그냥 전부 구현했다. C++ 코드 #include #include using namespace std; typedef struct node node_t; struct node { int val; node_t* lChild; node_t* rChild; }; vector vals; void insert(node_t** p, int n); void midfixInsertVal(node_t* p); void removeMax(node_t** pp); void removeMin(node_t** pp); vector solution(vector operations) { vector answer; vals.clear(..
[프로그래머스] 순위 / 플로이드-워셜 알고리즘 / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 문제에 따르면 실력이 더 좋은 선수가 항상 이긴다고 한다. 예를 들어, A가 B를 이기고 B가 C를 이긴다면, A는 항상 C를 이긴다. 이를 그래프로 표현한다면 A에서 B로 가는 경로가 있다면 A에서 C로 가는 경로가 있다고 표현할 수 있다. 다시 말해 B를 중간 경로로 하여 A에서 C로 갈 수 있는 것이다. 그래프에서 '갈 수 있다'는 것은 곧 '이긴다'는 의미가 된다. 플..
[백준] 1753 최단경로 / 다익스트라 알고리즘 / C++ 풀이 문제 링크 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 전략 '시작점에서 다른 모든 정점으로의 최단 경로'를 구하라고 한다. 다익스트라 알고리즘을 사용하면 특정 시작 노드에서 다른 모든 노드로의 최단 경로를 구할 수 있다. 따라서 다익스트라 알고리즘으로 접근한다. C++ 풀이 /* https://www.acmicpc.net/problem/1753 */ #include #include #include..
[프로그래머스] 네트워크 / 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)회의 반복문이 돌기 때문에 효율성 테스트를 통과할 수 없다. 따라서 더 효율적인 방법을 생각해야 한다. 문제에서 '한 코어에서 작업이 끝나면 작업이..
[백준] 2468 안전 영역 / BFS, 깊이 우선 탐색 문제 링크 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이 전략 가능한 모든 수위에 대해 물에 잠기는 지점과 안전한 지점을 표시한다. 서로 연결된 안전한 지점을 BFS를 통해 찾는다. BFS가 호출된 수가 안전 영역의 개수이다. 코드 #include #include #include using namespace std; int board[101][101]; int land[101][101]; //-1 : 침수, 1 : 안전지역 int N; int ..

티스토리툴바