비트 마스킹 (bit masking) 이란? 이진수와 관련된 개념이다 이진수 110 은 2^2+2^1 으로 십진수 6을 표현한다. 그리고 이진수는 또다른 원론적인 의미로 해석될 수 있는데 바로 true false다. 즉 110 은 단순 십진수 6 뿐 아니라, 첫째, 둘째 놈은 true, 셋째 놈은 false 로 의미 부여를 하고 갈 수 도 있는것. 이번엔 거꾸로 가보자. 눈앞에 10개 버튼이 있는데, 나는 각버튼을 누를 수 도, 누르지 않을 수도 있다. 내가 버튼을 누를 수 있는 경우의 수는? 간단한 수학이다. 누른다, 안누른다 = 2 2^10= 1024 가지 경우의 수가 나온다. 아래 이진수에 부여한 의미를 생각해보자 0000000000 == 십진수 0 >> 전부 버튼을 누르지 않는다 000000000..
lis는 10, 20, 10, 30, 20, 50 이런 길이 5의 수열중 10, 20 ,30 ,50 과 같이 계속해서 증가하는 수열들 중, 가장 긴 수열을 찾는 문제다. 우선 lcs는 푸는 방식이 정말 다양한데, 전부 시간 복잡도가 다르다. dp를 통해서 풀게되면 O(N^2) 이고, lower_bound를 통해서 풀게 되면 O(NlogN) 의 시간 복잡도가 발생한다. lis 문제는 시간초과를 가지고 장난을 많이 치기에 lower_bound 방식만 가지고 문제를 풀어보겠다. 자세한건 아래 문제를 보면서 알아보자..! 1.lis 의 길이는? lis의 길이를 구하는 문제로, 위 의 입력의 경우 10,20,30,50 이기에 4가 정답입니다. 흔히 전깃줄 문제로 응용 됩니다. 자세한 건 아래 문제를 확인 해봅시다..
knapsack은 "제한된 자원" 으로 "최적(최대 or 최소) 의 이득" 을 얻는 문제에서 사용된다. 아래는 대표적인 예시 중 하나다. n개의 보석이있다. 이중 1~ n번째 보석중 k 번째 보석의 무게를 w_k, 가격을 c_k 라고 정의한다. 내가 가방에 최대로 담을 수 있는 무게가 w_max일때, 내가 담을 수 있는 최대 가치는? 대충 이런 느낌이지만, knapsack도 상황에 따라 다양한 방식으로 나눠져 있으므로 지금부터 같이 하나하나 알아보자! 1) fractional knapsack - 보석을 쪼개서 가방에 담을 수 있다. >> 그냥 무게당 가치가 높은것들을 우선적으로 가방에 담으면 끝이다. 예를들어 무게3에 가치 9, 무게 2에 가치 4 무게 1에 가치 1인 보석이있다고하면 1번의 무게 1당 ..
우선 백준 1005번을 보고 오자. https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 이 문제에 대한 올바른 문제해결 방법은 '위상정렬' 이다. 위상정렬은 보통 어떤 작업에 순서가 정해져있을 때, 순서를 결정하기 위해 사용하는 알고리즘입니다. 예를들어 스타크래프트에서 어떤 상위 건물을 지으려면, 하위 건물들을 몇가지 지어야 하는 경우가 있는데, 이처럼 어떤 작업 진행전에 해야하는 '순서' 가 존재할시 위상정렬을 사용한다. 위상정렬을 사용하기..
보통 데이터의 집합은 배열로 저장하는 것이 일반적이지만, vector, queue 등의 데이터 타입이 가지는 차별점으로 인해 다양한 데이터 타입을 사용하는 경우가 많은데, 자주 쓰는 배열과 달리 익숙하지 않아 초기화하는 것에 애를 먹은 경험이 있어 이러한 다양한 데이터 타입을 초기화 하는 방법을 간단하게 정리해보려한다. 1. vector 초기화 내가 보통 사용하는 방법은 vector vec; int main(){ //vec에 값을 넣어준다 vector tmp; vec=tmp; } 위와 같이 완전히 동일한 새로운 벡터를 만들어준 뒤, = 연산자로 초기화해주는 것이다. 보통 초기화 방법을 검색하면 fill 함수( 주어진 벡터내 모든 데이터를 지정값으로 초기화) 를 쓴다는데 이 방식대로면 단순히 '값' 을 초..
경로를 탐색해나가는 것에 더 나아가, 경로를 저장한 후 출력하라는 문제들이 종종 있다. 오늘은 어떤 경우에, 어떤식으로 경로를 저장해나가는지 케이스 별로 알아보자 1. 다익스트라,벨만포드 https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 백준 문제 11779 번을 풀어보며 알아보자. 이 문제는 다익스트라 문제이지만, 벨만포드도 "경로 추적" 은 동일한 메커니즘으로 돌아간다. 혹시 벨만포드로 된 문제를 풀고 싶다면 ..
x,y 좌표에 대한 기본지식으로 인해 헷갈릴 수 있는 부분인데 arr[i][j] 에서 i값은 x좌표, j값은 y좌표 가 아니다! 이차원 배열을 풀 때, 저절로 x,y좌표를 이미지화 하며 구현하는 경우가 있는데, 보통 아래와 같이 이미지화 할 것이다. (x,y) 를 표시 여기서 우리가 이차원 배열을 입력을 아래와 같이 받고 for(int i=0;iarr[i][j]; 출력도 동일하게 아래와 같이 한다고 생각해보자. for(int i=0;i
이 문제가 삼성 코테에 기출 되어서 풀어봤는데, 여러가지 알고리즘이 한 문제에 누적 되어 있어, 풀어보면 좋을 것 같아 자잘한 설명과 함께 코드를 공유하려합니다! 코드에 대한 설명은 주석으로 상세하게 적어놨습니다~ 문제를 처음보면, 딱 "그룹" 이라는 단어가 떠오르면서 자연스럽게 mst(최소 스패닝 트리) 에 관한 문제인 것을 캐치하고 풀어 나갔다. MST에 대해 잘 모른다면, 아래의 글을 참고하자. https://codenme.tistory.com/manage/posts/ Tistory 좀 아는 블로거들의 유용한 이야기 www.tistory.com 문제는 크게 3파트로 나눌 수 있는데 1) 각 섬에 번호를 붙여 저장하기 (섬간의 구분을 위해) 이건 bfs를 통해 구현했다.. 2)섬간의 거리를 구한다. ..
