baekjoon 1074 Z 1074번 Z 접근 각 단계마다 절반의 height와 절반의 width를 주어진 좌표와 비교하여 상대적 위치를 파악하고 skip할 수 있는 만큼을 skip해버렸다. 그리고 이 방식을 가장 작은 2*2사각형이 나올 때 까지 했다. 코드 #include <iostream> #include <vector&...

baekjoon 14003 가장 긴 증가하는 부분 수열 5 14003번 가장 긴 증가하는 부분 수열 5 접근 dp로 풀려고 했더니 시간을 도저히 맞출 수 없었다. dp로 풀면 O(n^2)에 푸는 것인데 n = 1,000,000이면 3초 무조건 넘는다. 그래서 결국 lis를 O(nlogn)에 푸는 알고리즘을 쓸 수 밖에 없었다. 이 알고리즘은 ans...

baekjoon 13460 구슬 탈출 2 13460번 구슬 탈출 2 접근 queue에 넣어서 하나씩 순서대로 check할 것이다. nextMove함수로 한번에 상하좌우 다 check한다. 구멍으로 빨간색 나오면 출력하고 return true. count 9일때, 그리고 blue 나왔을 땐 다음 count++ 추가 안한다. queue추가도 안한다. ...

baekjoon 1197 최소 스패닝 트리 1197번 최소 스패닝 트리 접근 //clrs그림 넣고 설명 들어갈 거임 전형적인 mst 문제이다. mst알고리즘으로 kruskal 알고리즘을 선택했다. kruskal 알고리즘은 매 선택에서 다른 집합을 잇는 edge중 가장 weight이 작은 edge를 선택한다는 점에서 greedy 알고리즘의 일종이다....

baekjoon 15681 트리와 쿼리 15681번 트리와 쿼리 접근 dfs를 통해 트리를 만든 후 dp for tree를 이용해서 count를 센다. 코드 #include <iostream> #include <vector> using namespace std; int n, r, q; void dfsTree(int x, v...

baekjoon 2467 용액 2467번 용액 접근 처음에는 2개를 고를 수 잇는 경우를 다 따지는 방식을 써봤는데 100,000C2는 1초를 아득히 초과했다. 그 다음에는 수 범위만큼 배열을 만들어 두고 모든 수에 대해 자기에 -1을 곱한수와 가장 가까운 수를 저장해두고 시작하는 방법을 사용했다. 그런데 수 범위가 1,000,000,000까지라 ...

baekjoon 2166 다각형의 면적 2166번 다각형의 면적 접근 매번 절댓값해서 더해야하는 줄 알았는데 그러면 오목다각형을 계산하지 못한다고 한다. 신발끈 공식을 이용하는 것처럼 그냥 음수도 처음엔 절댓값 붙이지 않고 더해줘야 오목다각형의 경우 서로 상쇄되는 효과가 나서 정확한 넓이를 구할 수 있다. 마지막에 절댓값해주면 된다. 코드 //...

baekjoon 9252 LCS 2 9252번 LCS 2 접근 LCS(Longest Common Subsequence)는 유명한 dp문제이다. 나도 예전에 풀어본 적 있을 것이다. 하지만 이 문제는 길이 뿐 만 아니라 그 subsequence를 복원해야 한다는 차이점이 있다. 이는 dp하면서 만든 cache 2차원 배열을 통해 추적해 나가면 된다....

baekjoon 12100 2048 (Easy) 12100번 2048 (Easy) 접근 2048 구현 문제였다. deuque를 이용해서 좀 수월하게 구현했다. 코드 //12100 #include <iostream> #include <vector> #include <deque> #include <queue&...

baekjoon 1700 멀티탭 스케줄링 1700번 멀티탭 스케줄링 접근 //가장 나중에 쓸 전자기기를 뽑는게 왜 최적의 해를 보장할까? //belady’s min algorithm //논문 보셈 코드 //1700 #include <iostream> #include <vector> #include <map> #i...