백준 1707. 이분 그래프 처음 문제를 봤을땐 좀 이해하기 힘들었는데, 예제를 통해 그림을 그려보면 감이 좀 잡힌다. 예제분석CASE 1.1,2,3번 정점이 있고, (1,2)와 (2,3) 간선이 이어져있는 형태이다.분석해보면, [1,2]와 [3]으로 집합을 분리했을때 각 집합에 속한 정점끼리는 서로 인접하지 않는다는 것을 알 수 있다.즉, 이분그래프인것이다.  CASE 2. 1,3번 정점이 서로 연결되어있지는 않지만, 그둘을 하나의 집합으로 묶었다고 해서 이분그래프가 되진 못한다. 나머지 집합이 서로 인접하기 때문이다(간선을 갖기 때문)  이분그래프그렇다면 위 내용을 바탕으로, 이분그래프를 정의해보자면 다음과 같다. 이런식으로 정점을 두 진영으로 나누었을때, 서로 다른 진영끼리는 연결될 수 있으나 같은..

올해 하반기 신입공채를 준비하면서, 코딩테스트를 굉장히 많이 봤던것같다.대기업, 중견기업, 은행권, IT회사 등 가리지 않고 응시하게 되었는데, 특히 대기업과 은행권 쪽에서는 SQL이 꼭 필수적으로 출제되었다. 보통은 한문제에서 최대 두문제까지 나왔고, 난이도는 천차만별이였다... 분명 옛날에는 코테수준의 SQL은 어렵지 않다고, 특히 은행권은 어렵지 않다는 의견이 지배적이었던거 같은데^^;; 최근 코테 경향을 보면 그렇지만도 않은것같다. 쉬운건 정말 쉽지만, 어려운건 정말 어렵다는 느낌...왜 그렇게 생각했냐면, 지엽적(?)인 함수를 써야되는 문제들이 다수 출제되었다. 나는 프로그래머스 SQL 고득점 Kit를 통해 대비했는데, 취준 초반 시절엔 '음.. 어려워봤자 Join문이나 서브쿼리 정도 아닐까?'..

이분탐색 문제를 풀다보면, 만족하는 특정 값만 있는 문제 뿐만아니라 만족하는 값중 가장 작은것, 또는 만족하는 값의 다음 수를 찾는 문제들이 나온다.이때 사용하는것이 바로 경계값찾기 - Upper Bound와 Lower Bound!! Lower Bound?Lower Bound는 하한값을 나타냄.즉, 찾으려는 값 이상의 값이 처음으로 나타내는 위치2를 찾는중이면, 111222333 이부분! Upper Bound?Upper Bound는 상한값을 나타냄즉 찾으려는 값을 초과한 값이 처음으로 나타나는 위치2를 찾는중이면, 111222333 이부분! 그렇다면 찾으려는 값이 없을때의 결과는?5를 찾을때 1224446779가 주어진다면Lower Bound = 1224446779 ⇒ index=6Upper Bound ..

냅색배낭에 넣을 최댓값이 정해지고 해당 한도 내에서 물건을 넣어 가치의 합이 최대가 되도록 고르는 조합 최적화 문제.두가지로 분류될 수 있다.짐을 쪼갤 수 있는 경우(Fraction Knapsack Problem) ⇒ 그리디를 통해 풀이함짐을 쪼갤 수 없는 경우(0/1 Knapsack Problem) ⇒ DP를 통해 풀이함평범한 배낭백준 12865번 문제 무게W와 가치V 배열이 있을때, 각 W[i]무게를 가진 물건의 가치는 V[i]이다. 예제에 의하면 (Wi, Vi) = (6,13), (4,8), (3,6), (5,12)이다. 최대 수용 무게는 K=7이다.DP[i] = i무게일때 최대 수용 가능한 물품의 가치인것으로 설정하고 규칙을 찾아보자.(6,13), (4,8), (3,6), (5,12)을 각각 A,..