알고리즘
1.순열과 조합
알고리즘 문제를 풀면서 생각보다 순열이나 조합을 구현할 일이 많다고 생각되어 정리해보았다.55CD09E1-9E71-48E1-A9D2-6A6FBD14A826.jpegc++에서는 next_permutation 함수와 prev_permutation 함수를 제공하는데,각각 “
2.비트마스킹
ex) 10010 (18) 의 1번째 비트 끄기ex) 10010(18) 의 0번째 비트 바꾸기ex) 10010 (18) 의 최하위 켜져있는 비트? 1번째 비트ex) 10010 (18) 0번째 비트 켜기10010 (18) 3번째 비트 확인어떤 특정 원소를 찾을때 시간
3.[알고리즘] 그리디와 라인스위핑
각 단계마다 지역적 최적해가 궁극적으로 전역최적해가 되는 것.그리디로 문제를 풀려면 2가지를 충족해야한다.최적부분구조를 가지고 있어야 한다. 지금 state에서 최선을 다해 선택하는 해가 결국에는 전역적인 최적해로 이어져야 한다.탐욕적속성이 증명이 되어야 한다. 하지만
4.[알고리즘] 백준15662 톱니바퀴(2)
백준15662 톱니바퀴(2)톱니바퀴가 조건에따라 연결되어 회전한다.제일 처음 회전시키는 톱니바퀴를 기준으로 왼쪽과 오른쪽을 확인하여 회전조건을 만족할 경우 하나의 자료형에 해당 톱니바퀴의 인덱스와 회전방향을 저장하여 한번에 회전시키면 되지않을까??가장 처음 회전하려는
5.[알고리즘] 백준1911 흙길 보수하기
백준1911 흙길 보수하기해결해야 할 것웅덩이의 범위가 겹치는 경우 처리웅덩이의 범위와 널빤지의 길이에 따른 처리위치에 해당하는 배열을 만들어 웅덩이를 저장할까?위치값은 최대 10억이므로 10억짜리 배열을 만들 수 없다!\-> 라인스위핑을 이용하자.웅덩이의 크기가 널빤
6.[알고리즘] 백준2632 피자판매
백준2632 피자판매손님이 주문한 피자를 판매하는 경우의 수는 다음과 같다.A 피자로만 구성B 피자로만 구성A 피자와 B 피자 혼합먼저 위 경우의 수의 최대값을 알아보자.A와B 피자는 최대 1000 조각이다.손님은 최대 2,000,000 피자만큼 주문 할 수 있다.2,
7.[알고리즘] 이분탐색과 LIS(최대증가부분수열)
이분탐색은 어떤 경우의 수를 하기에는 애매하거나, n이 무지막지하게 큰 경우 O(logN) 만에 처리해야겠다는 생각이 들 경우 시도해보는 알고리즘이다.이진탐색정렬된 배열에 특정 원소가 있는지를 확인하는 것을 logN 만에 해결하는 알고리즘정렬된 배열의 가운데를 살펴보고
8.[알고리즘] 백준 1561 놀이공원
백준1561 놀이공원T초가 되었을때 전부 다 태울 수 있는지 확인한 후, 가장 낮은 T초를 구하면 되지 않을까? N이 20억이다. -> 시간복잡도가 크니까 탐색을 한다면 이분 탐색을 떠올려야 함.코드를 순차적으로 살펴보자.check() 코드를 살펴보면 각 놀이기구 마다
9.[알고리즘] 2020 카카오 기출 _ 자물쇠와 열쇠
2020 KAKAO BLIND RECRUIT : 자물쇠와 열쇠열쇠는 회전과 이동이 가능하고, 열쇠로 자물쇠를 열수 있는지를 판단하는 문제이니, 완전 탐색으로 풀 수 있지 않을까?자물쇠의 홈이 열쇠의 돌기보다 많을 경우열쇠를 360도 회전시키며 자물쇠의 패턴과 비교할때,
10.[알고리즘] DP, 다이나믹 프로그래밍
DP,다이나믹 프로그래밍 이란? DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.
11.[알고리즘] 백준 12852 1로 만들기 2
12852 1로 만들기 2X가 3으로 나누어 떨어지는 경우X가 2로 나누어 떨어지는 경우1을 빼는 경우N이라는 자연수에 대하여 위의 3가지의 경우를 모두 탐색하여야 한다.하지만 아래 2가지의 제약조건이 존재한다.N은 최대 10^6 의 자연수이다.연산의 최솟값을 구해야한
12.[알고리즘] 백준 12865 평범한 배낭
12865 평범한 배낭여러가지 경우의 수 중에서 최댓값을 구하면 되는 전형적인 DP 문제이다. 바로 코드를 살펴보자.1\. 해당 물건을 넣기 전 가방의 최대 가치 + 해당 물건의 가치 (물건을 가방에 넣었을때)2\. 해당 물건을 넣었을때와 동일한 무게의 가방의 최대가치
13.[알고리즘] 백준 17387 새로운 게임 2
17387 새로운 게임 2구현 문제니 문제의 조건을 먼저 살펴보자.맵의 크기 NXN, 말의 개수 K말은 1턴에 1번 말부터 K번 말까지 순서대로 한칸 움직인다.이동 방향(오른쪽 :1, 왼쪽: 2, 위쪽: 3, 아래쪽:4)말이 이동할때, 위에 올려져 있는 말이 있으면 함
14.[알고리즘] 백준 1450 냅색문제
1450 냅색문제경우의 수 문제이므로 탐색을 진행해야 한다.1\. 완전 탐색? -> N개의 물건이므로 완전 탐색을 진행하면 경우의 수는 2^30 이므로 불가능하다.2\. DP? -> C의 최댓값이 10^9 이므로 DP배열의 인덱스에 넣을 수 없다.그렇다면 어떻게 해야할
15.[알고리즘] 백준 1480 보석 모으기
1480 보석 모으기업로드중..보석을 무게 상관없이 최대한 많이 담으면 되니까 보석을 무게 순서대로 정렬한 후 계속 담아나가면 되지 않을까?? 예제 입력2) 처럼 1 3 5 2 4 입력이 들어왔을때, {1,4},{3,2} 이런식으로 담아야 하지만 위 방식은 {1,2}
16.[알고리즘] 백준 2156 포도주 시식
2156 포도주 시식먼저 문제의 조건을 살펴보자.1부터 N까지의 번호가 붙어있는 N개의 포도주 잔을 선택해서 마셔야한다.연속으로 놓여있는 3잔을 마실 수 없다.1<=N<=10,000위 조건을 바탕으로 DP를 가장 먼저 생각했고, 아래와 같은 코드를 구상하였다
17.[알고리즘] 백준 9251 LCS
9251 LCS문자열이 최대 1000글자로 이루어져 있으므로, 모든 경우의 수를 생각하려면 2^1000 이므로 DP를 사용하자.그렇다면 DP 배열을 어떻게 만들어야 할까?우선 예제를 바탕으로 살펴보자.위는 C와 "A", "AC", "ACA", ... "ACAYKP" 문
18.[알고리즘] 펜윅트리
펜윅트리는 이진 트리기반의 자료구조이며 세그먼트 트리의 원리를 가지고 있다.아래는 최솟값의 index를 담은 트리이다.이처럼 세그먼트 트리는 1\. 이진트리에2\. 어떤 쿼리에 대한 최적화한 값을 담아놓은 것을 의미한다.이를 이용하여 최솟값을 탐색한다면 쉽게 O(log
19.[알고리즘] 다익스트라
그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다.가중치가 양수인 그래프에서 사용할 수 있다.위와 같이 정점까지의 거리를 갱신하며 탐색한다.문제를 통해 더 자세히 살펴보자.1753 최단경로최소값을 구하는 문제이므로, 초기값을 INF로 설정해
20.[알고리즘] 백준 2618 경찰차
2618 경찰차사건이 최대 1000번 일어날 수 있고, 경찰차는 2대가 있으니 단순히 완전탐색으로 풀려면 2^1000 의 경우의 수를 탐색해야한다.그럼 DP로 접근해보자.제일 처음에 든 생각은 각 경찰차의 좌표를 DP배열에 넣는 것이었다.하지만 도시의 크기는 최대 10
21.[알고리즘] 백준 5419 북서풍
📖문제 5419 북서풍 💡구상 위와 같은 네 섬이 존재한다면, 북서풍을 타고 항해할 수 있는 섬의 쌍의 수를 어떻게 구해야 할까? 🔍코드 🔥배운 점
22.[알고리즘] 백준 1280 나무심기
📖문제 1280 나무심기 💡구상 🔍코드 🔥배운 점
23.[알고리즘] 백준 1486 등산
1468 등산다른 지점으로 이동할 때, 걸리는 시간이 다르다?노드에서 노드로 가는게 가중치가 다르다면 BFS는 사용할 수 없다.BFS는 가중치가 같은 그래프에서 사용할 수 있다.또 산에 갔다가 다시 호텔로 돌아와야 하기 때문에, 단방향인 다익스트라 알고리즘은 사용할 수
24.[알고리즘] 백준 5719 거의 최단 경로
5719 거의 최단 경로거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 이루어진 경로 중 가장 짧은 것을 말한다. 우선 최단경로를 찾고 그 최단경로에 해당하는 간선들을 끊은 후 다시 최단경로를 찾는 방식으로 생각해봤다.처음에는 최단경로를 찾을 때 플로이드 워셜을
25.[알고리즘] 백준 1219 오민식의 고민
https://www.acmicpc.net/problem/1219(1219 오민식의 고민)우선 문제를 잘 살펴보면 그래프 간의 가중치는 "버는 돈" 에서 "교통 비용"을 뺀 값이고, 음수가 될 수 있다. 음수 가중치를 지닌 그래프의 최단 경로??벨만포드 알고리