비트 마스킹 (bit masking) 이란? 이진수와 관련된 개념이다 이진수 110 은 2^2+2^1 으로 십진수 6을 표현한다. 그리고 이진수는 또다른 원론적인 의미로 해석될 수 있는데 바로 true false다. 즉 110 은 단순 십진수 6 뿐 아니라, 첫째, 둘째 놈은 true, 셋째 놈은 false 로 의미 부여를 하고 갈 수 도 있는것. 이번엔 거꾸로 가보자. 눈앞에 10개 버튼이 있는데, 나는 각버튼을 누를 수 도, 누르지 않을 수도 있다. 내가 버튼을 누를 수 있는 경우의 수는? 간단한 수학이다. 누른다, 안누른다 = 2 2^10= 1024 가지 경우의 수가 나온다. 아래 이진수에 부여한 의미를 생각해보자 0000000000 == 십진수 0 >> 전부 버튼을 누르지 않는다 000000000..
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)섬간의 거리를 구한다. ..
많은 문제들이 최소 비용, 최단거리 등에 집착한다. 하지만 막상 수많은 최단거리, 최소 비용에 대한 문제들을 보면 어떤 알고리즘을 써서 풀어야하지...? 하는 생각이 들고 생각나는대로 문제를 풀면 시간초과 혹은 오답이 나오면 멘붕이 오곤한다.. 이번 글에선 "최단 거리" 에 대해서와, 언제, 어떤걸 써야하는지에 대해 간략하게 정리해 보겠다. 디테일한 설명전 간단한 요약을 먼저 하자면 bfs: 간선에 가중치가 없다(단위길이) , 즉 비용이 아닌 거치는 횟수가 요구될 때. 다익스트라: 특정 시작점 모든 지점 간의 최단거리 플로이드와샬: 모든 시작점 모든 지점 간의 최단거리 벨만포드: 최단거리에서 음수 간선, 등으로 인하여 계속해서 최단거리를 줄여나가는지 "감지" 해야하는 경우 정도로 요약할 수있다. 1)가중..
