본문 바로가기

CS

 (46)
유니온 파인드 알고리즘 Find 연산 대표노드를 찾는 연산 O(logN)의 시간복잡도를 갖는다 맨 처음에는 자기 자신으로 초기화 되어있다. 재귀적으로 구현할때 반드시 리턴값으로 업데이트 해줘서 경로 압축을 해줘야한다 Union 연산 두 집합을 합치는 연산 합칠때는 각각의 대표노드를 찾아서 한쪽의 대표노트로 값을 바꿔주면 된다(편의상 작은쪽으로) 선택된 노드끼리 연결하는게 아니라 대표노드끼리 연결해야함 활용 용도(발상법) 1. 네트워크 연결성 검사 네트워크 내의 노드들이 서로 연결되어 있는지, 또는 두 노드가 같은 네트워크 내에 있는지를 판별할 때 예를 들어, 컴퓨터 네트워크나 소셜 네트워크에서 두 사용자가 서로 연결되어 있는지 확인할때 2. 최소 신장 트리 알고리즘 최소 신장 트리(Minimum Spanning Tree, MS..
[BOJ 2482] 색상환 난이도가 있는 dp문제다. 언제나 그렇듯이 dp는 테이블로 시작해서 테이블로 끝난다. dp는 테이블만 잘 설계한다면 물리적으로 내부동작이 어떻게 되든지 상관없이 논리적으로 답이 도출된다. 테이블이 설계가 안된다면 수열을 노가다로 찾아야 하는데 실수할 여지도 많고 시간이 얼마나 걸릴지도 알수 없다. 테이블을 잘 설계하면 이전값들의 결과가 현재값에 영향을 끼쳐야하는 형태가 돼야한다.(끊어지지 않고 이어지는 형태) 서론은 여기까지 하고 이제 이문제를 풀어보자. 일단 d[i][j]는 i개 중에서 j개를 선택하는 경우의 수라고 테이블을 설계했을때 딱 두가지 경우만 생각하면 이문제는 풀린다. 1. 첫번째 색을 포함할 것인가? -> 첫번째를 제외한(이미 뽑았음으로) 나머지 n-1개 중에서 k-1개를 마저 뽑는다. 2..
[BOJ 2293] 동전 1 나는 왜 이문제를 못풀었을까? dp문제를 풀때 규칙이 바로 보이지 않으면 손을 놓고 머리속으로만 풀려고 하는 안좋은 습관이 있다. 규칙이 보이지 않으면 손을 부지런히 움직여서 규칙이 보일때까지 시행착오를 겪으면서 발견해야하는데 발견하지 못할것 같다는 두려움과 손을 놀려야 한다는 귀찮음 때문인것 같다. 그렇다고 머릿속으로만 생각하면 난 천재처럼 머리속에 화이트보드가 있는것도 아니니 초 스피드로 사라지는 휘발성 메모리를 가지고 dp 문제를 풀라고하니 가당치가 않았던 것이다. 고등학교 수열과 마찬가지로 dp는 무조건 규칙 찾기이고 그때 당시 '자기 손으로 지저분하게라도 직접 풀어내는것이 베스트'라는 어떤 수학강사의 말이 다시금 떠올랐다. 다시한번 상기하자 dp는 수열이고 수열의 핵심은 규칙찾기고 노다가를 해서..
[BOJ 11055] 가장 큰 증가하는 부분 수열 다이나믹 프로그래밍에서 가장 중요한것은 테이블을 어떻게 정의하는것이다. 항상 문제를 푼다는 마음이 급해서 테이블 정의를 소홀히해서 오히려 문제를 못풀고 헤매는 경우가 많았다. 따라서 DP 문제는 반드시 테이블을 정의하는것이 시작이라는것을 깨달아야 한다. 테이블에 따라서 문제가 간편해 질수도 복잡해 질수도있다. (일단 테이블이 내가 말하는대로 생각한대로 무조건 동작한다고 가정하자.) 테이블만 잘 설계하면 나머지 조건식들은 적절히 구성해서 답을 도출할수 있다. 수학처럼 점화식으로 떨어지기도 하거나 전에 구했던 식에서 한단계씩 확장하는 모습일수도 있다. 이문제에서는 증가하는 수열의 합인데 DP로 풀지 않는다면 증가하는 이라는 조건을 그때그때 조건식으로 추려내기가 쉽지가 않다. 그렇다면 DP를 이용해서 전단계에..
BOJ 복습용 필수문제 큐 + 코테 팁 인덱스가 헷갈리면 머리로 풀어서 번아웃 오지 말고 노트에 적으면서 진행해라 EASY MODE: 개념 복습용 문제 큐 HARD MODE: 심화 코테용 문제 큐 스택 2493 탑 HARD MODE 6198 옥상 정원 꾸미기 HARD MODE 17298 오큰수 HARD MODE 덱 11003 최솟값 찾기 HARD MODE BFS 4179 불! EASY MODE 7569 토마토 EASY MODE 5427 불 EASY MODE 9466 텀 프로젝트 EASY MODE 2206 벽 부수고 이동하기 EASY MODE 2146 다리 만들기 HARD MODE 1600 말이 되고픈 원숭이 HARD MODE 14442 벽 부수고 이동하기 2 HARD MODE 16933 벽 부수고 이동하기 3 HARD MODE 16920 확장..
[BOJ 1799] 비숍 이문제를 일반적인 백트래킹 방식으로 풀면 N이 최대 10일때 최대 2^100 경우의수가 생겨 시간초과가 된다. 그래서 발상의 비약이 필요한 문제고 그 아이디어는 체스판을 분할하는것이다. 체스판을 보면 흑과 백으로 나뉘어지는데 이것이 비숍의 공격방향과 일치한다. 비숍의 입장에서는 흑과 백은 서로 독립적이라 붙어만 있을뿐이지 서로 영향을 미치지 못한다. 따라서 흑과 백으로 나누면 N이 10일때 N이 5인 체스판 두개로 생각할수 있고 시간복잡도는 2^(25) = 33554432로 충분히 시간안에 해결할수 있는 문제가 된다. 비숍의 공격방향은 대각선이라 BFS같이 상하좌우로 움직이는것과는 달리 약간의 수학적 테크닉이 사용된다. / 방향 대각선은 x+y로 나타낼수있다. \ 대각선은 x-y+n-1로 나타낼수 있다...
[BOJ 1600번] 말이 되고픈 원숭이 BFS 문제는 일반적으로 기본문제만 풀수있는 수준과 심화 문제를 풀수있는 수준이 극명하게 갈리는데 이 문제는 바로 그 경계선이 되는 수준의 문제인것 같다. 정답률이 20퍼다. 본인이 번뜩이는 창의성이 부족한 평범한 사람이라면 분명히 이 문제에서 막히게 될것이고 이것은 발상의 비약이 필요한 순간이라고 할수 있다. 물론 내 이야기다. 알고리즘을 풀면서 어떻게 이런 생각을 하는지 감탄을 넘어서 존경하게되는 순간과 희열을 느끼는 순간과 벽을 느끼는 순간이 종종 있는데 이 문제도 그런류의 문제인것 같다. 나 역시 이문제를 좀 고민해보고 답지를 본 입장으로서 새로운 발상에 눈을 뜬 기분이였다. 일단 딱봐도 BFS를 발상하는것은 어렵지 않다. 문제는 원숭이는 말처럼 움직이는 횟수가 최대 K번이기 때문에 일반적인 BF..
[BOJ 2504번] 괄호의 값 이번문제는 스택 괄호쌍의 응용으로 쉽지 않은 문제였다. 다른 사람의 풀이 설명은 알고리즘이 동작하는 것 위주로 설명하는데 나로서는 쉽게 받아들여지지 않았다. 단순히 이 알고리즘 풀이만 외운다면 이 문제야 풀수 있겠지만 응용력은 기를수 없어보였다. 항상 어떤 문제를 풀때 아이디어가 뭐고 어떻게 발상했는지를 모르면 다른문제에 적용을 할수가 없어서 나는 내 언어로 완전히 바꾸고 이해를 해야 하는 타입이였다. 그래야만 한문제를 풀어도 열문제를 푼 효과를 얻을수 있기 때문이다. 모르는 문제를 답지를 보고 풀고 그 아이디어를 제대로 배웠다면 수십가지의 응용들도 해결할 능력을 얻기 때문에 모르는 것 위주로 문제를 풀어야하고 그게 좋은 방향인걸을 스스로 잘 알지만 역시 문제 앞에서 지고 말았다는 생각이 들어 항상 기분..

티스토리툴바