소근소근

백준 Z https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net [시간 초과 코드] int N, r, c; int cnt; void count(int sx, int sy, int ex, int ey) { //cout > c; int len = 1; for (int i = 0; i < N; i++) { len *= 2; } count(0, 0, len - 1, len - 1); } 처음에는 단순히 재귀를 돌며 0부터 구하려는 위치까지 숫자를 다..

백준 쇠막대기 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net () 는 레이저, ( 와 ) 는 막대기의 끝을 의미하므로, )가 (을 만나면 스택에서 pop하는 느낌으로 풀어야겠다고 생각은 했다 스택을 이용하면 쉽게 풀 수 있을 것 같은데 처음에 너무 어렵게 생각해서 코드를 이렇게 엄청 복잡하게 짰다.. [시간초과 나는 코드] string s; cin >> s; st.push(s[0]); int total = 0; for (int i = 1; i < s.l..

백준 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 현재 큐에 문서들이 주어졌을 때, 앞에서부터 문서를 출력한다. 단, 나머지 문서들 중에 front보다 중요도가 더 큰 문서가 있다면, 출력하지 않고 큐의 뒤로 보낸다. 일단 큐에 문서들을 차례로 집어넣고, 앞에서부터 확인을 해야한다. 나머지 문서들과 중요도를 어떻게 비교할까 하다가 우선순위 큐를 함께 사용했다. 우선순위 큐에 주어진 문서를 다 넣으면, 중요도가 큰 문서가 앞으로 오도록..

백준 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 기본적인 dfs 만 구현할 줄 안다면 풀 수 있는 문제이다. 1년씩 지나면서 빙산이 녹을 때, 처음으로 덩어리가 두개 이상이 되는 최초의 시간을 출력한다. 상하좌우 4방향 중에서 비어있는 경우(0인 경우)의 개수만큼 빼준다. 여기서 주의해야 할 점은, 현재 상태를 기준으로 보고 빼줘야 한다. (동시에 녹는다고 본다) 표시한 부분에서 2-2 = 0 이 되어도, 4부분을 볼 때는 왼쪽은 0..

백준 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 어떤 칸에서 출발하여 계속 대나무가 더 많은 쪽으로만 이동할 때, 최대로 움직일 수 있는 칸의 개수를 구하는 문제이다. 처음에 단순 DFS인줄 알고 이중 for문을 돌며 모든 칸에 대해 dfs를 돌려 최대 칸의 개수를 구했더니 시간초과가 났다. 이 문제는 재귀로 dp를 구현해서 풀면 되는 문제였다. 풀이 해법은 https://yabmoons.tistory.com/15..

분리 집합이란 교집합이 존재하지 않는 두개 이상의 집합을 뜻한다. 구분해야 하는 데이터 집합들을 다루는 알고리즘에서 사용할 수 있다. 분리집합에서는 자식 노드가 부모 노드를 가리키게 되어 있다. 보통 특정 집합의 대표 노드(루트)를 자식 노드들이 가리키고 있는 형태이다. 분리집합 연산에는 두 가지가 있다. 1. Union(x,y) 합집합 연산이다. 두개의 집합을 합치기 위해서 각 두 집합의 대표(루트)노드를 찾고, A의 대표노드의 부모를 B의 대표 노드로 설정한다. void Union(int x, int y) { int px = Find(x); int py = Find(y); if (px != py) { parent[px] = py; set_size[py] += set_size[px]; } } 합치려고 ..

백준 13711 LCS4 https://www.acmicpc.net/problem/13711 13711번: LCS 4 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, [1, 2, 3]과 [1, 3, 2]의 LCS는 [1, 2] 또는 [1, 3] www.acmicpc.net https://steptoprogrammer.tistory.com/60 [백준 BOJ 17218 glod5 - 비밀번호 만들기] Longest Common String (LCS) C++ 백준 17218 https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기..

백준 17218 https://www.acmicpc.net/problem/17218 17218번: 비밀번호 만들기 첫째 줄과 둘째 줄에 수형이가 눈을 감고 만든 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 길이는 최대 40자이다. 빈 문자열은 주어지지 않는다. 가장 긴 부분 문자열 www.acmicpc.net 이렇게 두개의 문자열에서 가장 긴 공통 수열을 찾고, 그 수열을 출력해야 하는 문제이다. 2차원 배열을 이용한 dp로 해결할 수 있다. #include #include #include #include #include #include #include #include using namespace std; int alpha[41][41]; char str1[41]; char str..