본문 바로가기

algorithm & data structure

 (16)
[BOJ] 2565 전깃줄/Dynamic Programming/이분 탐색/최장 증가 부분 수열(LIS)/C++ 풀이 문제 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 문제에서 제시해준 예제를 통해 풀이를 생각했다. 위 처럼 전깃줄 개수가 처음에 주어지고 그 다음 (시작 전봇대 위치 - 끝 전봇대 위치)들이 주어진다. 시작 위치 기준으로 정렬한다면 다음과 같이 된다. 이 때 문제의 예시의 답에서 알려준 끝 전봇대 위치가 1, 8, 9인 전깃줄을 제외하고 관찰해보면 흥미로운 특징이 보인다. 바로 2, 4, 6, 7, 10은 증가하는 수열이라는 것이다. 시작 전..
[BOJ] 포도주 시식 / Dynamic programming https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net C++ 풀이 코드 #include #include #define MAX_N (10000) using namespace std; int N; int wines[MAX_N + 1]; int dp[MAX_N + 1]; int answer; void solve() { cin >> N; for (int i = 1; i > wines[i]; } if (N == 1) { cout
[프로그래머스] 스킬트리 / 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/12946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr C++ 풀이 #include #include using namespace std; vector gAnswer; void hanoi(int n, int src, int path, int dst) { if(n == 0) return; hanoi(n - 1, src, dst, path); gAnswer.push_back({src, dst}); hanoi(n - 1, path, src, dst); ..
[프로그래머스] N개의 최소공배수 / 정수론 / 유클리드 호제법 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr C++ 풀이 #include #include using namespace std; int getGCD(const int a, const int b) { if(b == 0) { return a; } return getGCD(b, a%b); } int solution(vector arr) { int answer = 1; for(const auto& n : arr) { int gcd = ge..
[프로그래머스] 이중 우선 순위 큐 / 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(..
[프로그래머스] 섬 연결하기 / Minimum Spanning Tree, Kruskal MST, Union-find / C++ 풀이 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 전략 n개의 섬을 최소한의 비용으로 전부 연결해야 한다. 최소 신장 트리(Minimum spanning tree)는 그래프의 정점들을 최소의 비용으로 전부 연결한다. 이 때, n개의 정점에 대해 (n-1)개의 간선을 사용하여 연결한다. Kruskal MST 알고리즘 비용이 가장 적은 간선부터 n개의 정점을 전부 연결 할 때까지 선택해 나간다. 서로 연결된 정점들은 하나의 '그룹'이..
[프로그래머스] 순위 / 플로이드-워셜 알고리즘 / 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로 갈 수 있는 것이다. 그래프에서 '갈 수 있다'는 것은 곧 '이긴다'는 의미가 된다. 플..

티스토리툴바