본문 바로가기

알고리즘

[Union Find] 1. Union FInd 정의 - 서로소 집합(disjoint Set) & 병합 찾기(MergeFind Set) - 여러 서로소 집합을 가지고 있는 자료구조(서로소 집합이란, 교집합이 없으면서 모든 원소가 각자의 집합을 가지고 있는 집합) 2. 구현 1) 자료구조 -집합 자료구조: Tree, root 노드가 집합의 ID라 생각 -노드 자료구조: 배열, parent[i]는 원소 i의 부모 노드를 저장한다. 2) 함수 Union 함수: 주어진 원소들을 집합으로 합침 Find 함수: 특정 원소가 어느 집합에 있는지 찾음 3) 초기화 -parent[i] = i; //원소의 부모는 자기자신 4) 구현 //x의 root노드와 y의 root노드를 비교한 후, 둘이 같지 않다면 y의 root = x로 지정 void U.. 더보기
[11000]강의실 배정 3. 유의 할 것 - 입력값이 20만개 이므로 logN형 자료구조를 사용해야 한다. - 나는 시간을 줄이기 위해서 주로 map,set을 사용했는데 set의 경우 균형 이진 트리이므로 검색은 빠르지만 삽입 & 삭제가 느리다. (삽입,삭제는 log(N)) - 우선순위 큐는 Heap을 사용하므로 set보다 더 빠르다. 삽입 삭제도 logN 이므로 따라서 우선순위 큐를 자주 쓰도록 하자. 4. 코드 더보기 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N,s,e; vector v; cin >> N; for(int i=0;i> s >> e; .. 더보기
[Lev.2] 수식 최대화(C++) 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 � programmers.co.kr 2. 접근 방법 1) 우선 "숫자"와 "연산자"를 나누어 준다. 2) 연산자 별 우선순위 경우의 수를 next_permutation으로 만들어서 각 경우의 수 별로 연산을 수행한다. 3) 우선순위에 해당하는 연산자를 발견하면, 연산자 기준 양 옆의 숫자를 연산하여 연산 결과를 다시 list에 넣는다. -> 중간에 삽입/삭제가 자주 있으므로 lis.. 더보기
[Lev.3] 경주로 건설 1. 문제 https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 2. 접근 방법 1. dfs 혹은 bfs로 풀 수 있다. 나는 재귀 연습을 .. 더보기
[16235]나무 재테크(C++/구현) 1. 문제 https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 2. 접근 방법 1. 특별한 알고리즘을 써야 한다기 보단 구현 문제이다. 구현일 수록 사용할 자료구조 선택, index 의미에 유의하자! 2. 문제의 조건 & 제약 사항을 파악하자 (다음은 문제를 읽으면서 생각한 흐름) 1) 한 칸에 "여러 개"의 나무가 있을 수 있다. => "container형 이차원 배열 사용해야 겠다." 2) 양분을 먹을 때, 나이가 어린 나무부터.. 더보기
[백준] DP > 1. DP의 정의 & 속성 동적 계획법: 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 두 가지 속성을 만족해야 DP로 풀 수 있다 -optimal substructure: 문제의 정답을 다른 문제의 정답에서 구할 수 있음 ex) 피보나치 -overlapping subproblem: 겹치는 부분 문제 ( 작은 문제로 N-1과 N-2번째 수를 구하는 것) ex)서울->부산 가는 가장 빠른 길: 서울->대전-> 대구->부산 이면, 대전->부산을 가는 가장 빠른 길은 대전->대구->부산이다. 2. 문제 스킬 1) 각 문제는 한 번만 풀어야 한다. 2) 같은 문제는 구할 때마다 정답이 같다. 정답을 어딘가에 메모해두자(memorization) 3) 문제에서 구하려고 하는 답을 문장으로 나타낸다. 4) 문장에 .. 더보기
[Lev.3] 자물쇠와 열쇠(C++) 1. 문제 2. 접근 방법 1. 문제 조건 보면서 범위 줄여가기 1) 모든 홈이 다 차야 한다 => 홈이 발생한 구역을 구한다. 만약 열쇠 사이즈가 홈 구역보다 작으면 false return(경우의 수가 아예 안만들어 진다.) 2) 자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안된다 => 홈이 아닌 부분은 무조건 돌기이다 => 자물쇠의 홈 구역 밖으로 열쇠의 돌기가 있는 경우는 열 수 없음 3) 자물소의 홈 모양 전체와 열쇠의 돌기 모양 일부가 일치해야 한다. -> 나는 처음에 이렇게 접근했었는데, 이렇게 좁은 범위나 예외 케이스부터 생각하지 말고 큰 관점에서 먼저 생각하는 연습을 하자. 2. 가장 간단한 방법부터 생각하기 1) 모든 경우에 대해서 열쇠를 돌려가면서 맞춰본다 -> 완탐 -> 범위를 보니 가능한.. 더보기
N으로 표현(DP) / C++ 1. 문제 2. 접근 방법 1) 문제 조건, 제한 범위 찾기 - N은 최대 8번 사용 가능하다 => 연산을 수행할 수는 N~NNNNNNNN까지 가능 - 괄호 사용 가능 2) DFS로 풀기 2-1) 종료 조건 : 원하는 수를 찾았을 때, cnt가 8을 넘어갔을 때 2-2) 재귀 함수 호출 : 0부터 시작, 현재 수에 N부터 NNNNNN까지 사칙 연산을 각각 수행하면서 재귀함수를 호출한다. => 현재 수 (+ / - / * / 나눗셈) N,NN,NNN,...,NNNNNN 2-3) 효율적으로 짜는 법 : - 현재 수가 0인 경우엔 곱셈 나눗셈 수행 안함 - 2-2)에서 현재 수에 연산할 N의 범위는 최대 NNNNNN이다. (for문은 N부터 NNNNNN까지 6번 수행) NNNNNNN과 NNNNNNNN이 안되는.. 더보기

티스토리툴바