룰루랄라 알고리즘

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 오늘 취업전선에 먼저 뛰어든 여자동기 친구와 이런저런 스몰토크를 하다가 친구가 친 대기업에서 자료구조를 기반으로 한 코테 문제가 많이 나왔다는 소리를 듣고, 작년에 배운 자료구조를 생각해 보다가 트리에 대해 잘 기억이 안 나는 것 같아서 관련 문제를 풀어봤다. 자료구조 강의 시간에 C를 기반으로 배웠었는데 자바로 푸니까 확실히 선녀다. C로 할때는 트리 구성할 때 포인터로 연결하면서 ..

https://www.acmicpc.net/problem/1522 내가 제일 싫어하는 문자열 문제인 줄 알고 풀어봤는데 사실 문자열은 별로 관련 없고 슬라이딩 윈도우 문제였음. 처음에 문제 봤을 때 문자열을 서로 교환해야 되니까 자료구조로는 배열이 적합하다 해서 그냥 배열을 선택했다. 근데 사실 교환하는 로직은 문제를 푸는데 아무 관련 없다. 문자열이 처음과 끝이 연결되길래 원형큐인가 하고 봤는데 그것도 아니었다. 그래서 그냥 배열로 풀었다. 이건 그냥 문자열 길게 늘어뜨려놓고 A의 개수를 세서 처음부터 한 칸씩 움직이면서 B의 최소 개수를 세주기만 하면 된다. (문자열의 길이가 짧아서 가능한 브루트포스 느낌) (문자열 처음이랑 끝이 연결되니까 나머지 연산자로 한번 더 계산해 주자) 처음에 생각해 본 로..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 집에 누워있으면 진짜 안될 것 같은 위기감을 느끼고 집 앞 2분 거리 카페에 나와서 문제를 풀었다. 다이나믹 문제를 풀려고 푼 게 아니라 내가 좋아요 누른 문제집을 거의 다 풀고 2개 남아서 그중 하나를 골랐는데 풀어보니 dp였다. 이제 문제를 보기만 하면 dp가 생각이 난다 사실 문제를 풀려고 카페를 갔던 게 아니라서 펜과 종이가 없어서 그림판으로 풀었다. 작은 수를 놓고 좀만 끄적이다 보면 바로 규칙이 나온다. dp는 늘 규칙찾는 퍼즐 푸는 것 같다 1. [][0]에는 이전까지의 합을 누적해서 저장 2. [][1]에는 마지막 ..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 주말 하루종일 침대에만 있다가 죄책감이 들어 저녁 먹고 간단하게 홈트 후에 쉬운 문제를 풀어보았다. 다이나믹 프로그래밍은 예전에 문제를 많이 풀어봐서 바로 풀이법이 떠올랐다. // 0 1 2 3 4 // 0 0 00 000 // 1 1 11,01 111,001,011 // 2 2 22,02,12 222,002,022,012,112,122 // 3 3 33,03,..

https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 학교 전공 시간에 너무 듣기 싫어서 오랜만에 문제를 풀어봤다. 물론 전공시간 동안 못 풀어서 집에서 마저 풀었다. 체스에 조예가 깊었던 나는 맘에 드는 제목을 보고 덥석 풀어봤지만 시간복잡도의 늪에 빠져 몇 시간을 헤맸다. 3트 끝에 겨우 통과했다. 그럼 내가 처음에 제시했던 아이디어와 그 이후 가지치기로 시간복잡도를 줄인 코드를 살펴보자. 3가지 방법이 생각났다. 1. Pair(x, y) 클래스를 생성 후 Se..

앞서 푼 문제 N과 M (1)에서 출력 결과가 오름차순인 조건만 추가된 문제다. 풀이가 앞선 문제와 너무 비슷하고 간단해서 올리지 말까 고민하다가 그냥 올린다. https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아래처럼 DFS를 조금만 수정해 주면 오름차순 조건이 추가되어 출력된다. DFS 백트래킹에서는 방문처리가 중요하니까 이에 신경 써서 풀자!

백준에서 N과 M 문제를 오랫동안 봐왔는데 이번 기회에 (1)부터 차례대로 풀어봐야겠다. https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M이 1부터 8사이이긴 하지만 브루트포스로 돌리면 시간복잡도가 말도 안 되게 높아질 것 같아서 다른 방법으로 풀어야 하는데 문제에 비해 생각보다 풀이법이 떠오르지 않았다. 블로그에서 예전에 풀었던 문제중에 비슷한 걸로 찾아봤더니 DFS를 활용한 백트래킹 문제였다. 내가 가장 못 푸는 문제 유형이니까 이..

일부러 DP만 푸는 게 아니라 풀어보니 DP였다. https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당 문제는 쉽게 점화식을 떠올릴 수 있는데 중복을 허락하지 않는다는 부분에서 고민이 길어졌다. 10원을 만들기 위해서는 dp[10] = dp[9] + dp[8] + dp[5] 처럼 제안된 동전의 값어치만 더하면 10원이 되는 식으로 점화식을 세울 수 있다. 하지만 이 문제는 중복을 허락하지 않는다. 예를 들어 만약 1과 2로 4를 만들어야할 때, ..

이 문제도 dp를 이용하기에 아주 좋은 문제인 것 같다. https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 전략은 dp테이블을 2차원 배열로 다음과 같이 생성하는 것! dp[자릿수][n으로 끝나는 수] 배열은 0부터 시작하기 떄문에 dp[1][2]는 자릿수가 2개인 숫자 중에 2로 끝나는 수의 개수를 의미한다. 계단 수의 특징은 0과 9로 끝나는 수는 다음 자리수에 1과 8만 올 수 있으므로 해당 케이스는 따로 처리하고, 나머지 숫자들은 자신의 수 보다 +1, -1 한 dp[i][j+1] + dp[i][j-1]로 계산한다. 또한 수의 크기가 크므로 자료형을 l..

반년만에 문제를 풀기 때문에 근본문제인 DFS를 다시 한번 풀어보자 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 너무 오랜만에 풀어서 기억이 안났다. 특히 2차원 배열로 행렬 만들 때 가로 세로가 너무 헷갈린다. 행렬에서 상하좌우로 움직여 구역을 나누는건 DFS로 풀자. 아직도 헷갈리는데 X:가로, Y:세로 일 때 int [X][Y] 이렇게 선언해야 할 듯. matrix = new int [M+1][N+1]로 선언한 것은 사실 M, N으로 해도 되지만 ..