Algorithm/greedy

프로그래머스 n+1카드게임 c++ // 그리디, 집합을 분류하라

https://school.programmers.co.kr/learn/courses/30/lessons/258707 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 시행착오1. 완탐 ? -> 경우의수 : 선택안함, 좌측선택, 우측선택, 둘다선택 (4) ^ 1000(n) ->불가2. dp?상태 : [idx][round][mycard] == 1000*1000*1000 == 10억 -> 메모리초과 -> 불가// mycard (내가 갖고있는 카드)부분을 정수 1개의 상태로 표현 불가능 -> 불가!3. 그리디? 부분최적해가 전체최적해가 된다. 2. 의사코드0. 매순..

프로그래머스 최소직사각형 c++ // greedy?

https://school.programmers.co.kr/learn/courses/30/lessons/86491 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문풀과정 분류가 완탐이라길래 가로선택-세로선택 분기로 알고리즘짬 -> 최악 : O(2^1000) -> 불가능 그리디로 풀이를 바꾸었다. 2. 전체코드 #include using namespace std; int n; vector big,small; int solution(vector sizes) { int answer = 0; n=sizes.size(); //큰것들모음 - big //작은것들..

프로그래머스 섬 연결하기 c++ // 크러스칼 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 특이한 부분 재귀함수 //부모노드찾기 int get_parent(int node){ if(parent[node]==node) return node; return parent[node]=get_parent(parent[node]); } 2. 합집합 //같은집합으로 만드는함수 void union_parent(int node1, int node2){ int p1=get_parent(node1); ..