MZ 개발자

이 문제는 정점 쌍이 주어지면 트리의 부모가 누구인지 찾는 문제이다. 문제의 예제 입력이 너무 깔끔하게 되어있어서 쉽게 생각할 수 있지만 현재 노드에서 어떤 인접리스트를 탐색해야 할지 생각이 필요한것 같다. 처음 문제를 보았을때 인접리스트를 바로 떠올리지는 않았다. 유니온-파인드인가..?? 생각을 해봤는데 아닌것 같았고.... 뭔가 다음 노드로 이동할때 마다 이동한 노드의 부모 노드를 표시해줘야 할것 같은데 한참을 생각하다가 인접리스트를 이용한 완전 탐색을 떠올렸다. 문제의 예제를 인접리스트와 그래프로 표현하면 다음과 같다. 이제 그래프 완전 탐색을 하면서 현재의 노드의 부모가 어떤건지 표현해주면 된다. 여기서 주의할 점은 단순 dfs로 문제를 풀때 이미 탐색이 끝난 노드는 재방문 하지 않돌고 visit..

이 문제는 N개의 물건중 몇개를 골라서 그 고른 물건의 무게가 K보다 작거나 같게 하였을때 얻을수 있는 가치의 최댓값을 구하는 문제이다. 처음 문제를 보았을때 물건을 무게순으로 정렬하여 모든 케이스에 대해 전부 탐색을 할까 생각했다. 하지만 이렇게 풀었을때 O(n!)의 시간 복잡도가 나오게 된다. 예를 들어 n이 100이라고 하였을때 1개를 선택해서 그 가치가 최대가 될수 있지만 100개를 전부 선택을 해야 가치가 최대가 될수 도 있다. 따라서 각각의 경우에 최악의 경우 100,99,98...개를 선택해야하는 경우가 발생한다. 이 문제를 해결하기 위해 2차원 배열 dp[i][k]를 생성하고 i는 n개의 물건중 i번째 물건을 선택한경우, k는 무게 제한으로 1부터 k 까지 모든 경우에 dp를 채워나가면 된..

이 문제는 I,O로 구성된 문자열 중 IOI 가 몇개 포함되어 있는지 갯수를 구하는 문제이다. 처음 단순 부르트포스 방식으로 접근했다면 당연히 만점을 받지 못했을 것이다. 서브테스크 1의 경우 N> s; solution(); } 다음은 KMP 알고리즘을 활용한 풀이이다. 자세한 알고리즘 설명은 여기를 확인하면 된다. 알고리즘 - KMP 안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부 devconf.tistory.com #include #include #include using namespace std; int n, m; string s; vector getSkipTabl..

이 문제를 읽어보면 배열을 뒤집고 삭제하는 작업이 여러번 반복되는 문제임을 알수 있다. 일반 백터를 활용하여 풀기를 시도한다면 원소의 제일 첫번째를 삭제하는것 뿐만아니라 값을 뒤집는것 또한 귀찮은 일이다. 이때 이를 손쉽게 할수 있는 덱(dequeue)을 사용하면 간단히 해결 가능하다. 입력 문자열을 파싱하여 R일경우 뒤집힘을 알수 있다. 여기서 덱의 특징을 이용한 간단한 트릭을 사용한다면 다음과 같이 생각해볼 수 있다. 1. R이 나오지 않은 상태에서 D를 만난다면 덱의 front에서 pop을 해준다. 2. R이 나올때마다 pop의 위치를 바꿔준다. 위의 방법을 반복하여 수행한 후 마지막 출력시 현재 상태가 front인지 back 인지 확인 후 알맞게 출력해 주면된다. #include #include ..

이 문제는 기본적인 DFS를 활용한 땅 갯수 구하기와 비슷한 문제이다. 문제에서 정상인이 보이는 색과 적록색약이 보이는 색이 다르다. 따라서 각각 정상인 경우와 적록색약인 경우로 나누어 각각 DFS를 돌리면 된다. #include #include #include #include using namespace std; char rgb[102][102]; char rb[102][102]; bool visited[102][102]; int dx[4] = { 0,1,0,-1 }; int dy[4] = { 1,0,-1,0 }; int n; int rgbCnt = 0, rbCnt = 0; void dfs(int x, int y, char arr[][102],char c) { if(visited[x][y]) { ret..

이 문제는 A라는 수를 DSLR 규칙을 이용하여 B로 바꾸는데 필요한 최소한의 명령어를 나열하여 출력하는 문제이다. 처음 문제를 보았을때 숫자를 자릿수로 쪼개서 deque으로 저장할까 라는 생각을 하였다. 이 방법을 이용하면 L,R은 쉽게 풀수 있지만 D,S는 자릿수를 다시 계산해야 하는 번거로움이 생긴다. 그냥 숫자로 접근해보자!! DSLR을 숫자로 접근해보면 다음과 같은 식으로 표현할 수 있다. D: (n * 2) % 10000 S: (n - 1) < 0?9999:n - 1 L: (n % 1000) * 10 + (n / 1000) R: (n % 10) * 1000 + (n / 10) 이제 A숫자에서 B로 만들기 위해 우리는 DSLR을 반복해서 수행해야 한다. 처음에는 시뮬레이션 문제인가 헷갈렸다. 알..

이 문제는 전형적인 분할 정복과 재귀를 사용하여 풀이하는 문제이다. 분할 할때 '('를 출력하고 정복시 ')'를 출력해주면 된다. 이와 비슷한 문제로 백준 2630 색종이 만들기가 있다. 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 위의 색종이 만들기 문제의 풀이는 여기를 참고하면 된다. 다음은 이 문제 풀이이다. #include #include #include using namespace std; char map[64][64]; string result = ""; void so..

우선 이 문제는 그래프 문제로 N 개의 정점이 주어지고 M개의 연결이 주어질때 '모든 정점'에서 '모든 정점'으로의 최단경로를 구하는 문제이다. 플로이드 와샬 알고리즘을 알고 있었다면 간단하게 해결할 수 있는 문제이다. 하지만 플로이드 와샬 알고리즘을 몰랐기 때문에 인접리스트를 이용하여 DFS로 문제를 해결하였다. 각 정점에서 다른 정점까지 최단 경로를 구해야 하기 때문에 생각해낸 방법은 리스트에 찾고자 하는 정점이 있을경우 1번에 탐색 가능, 없을경우 리스트에 있는 정점으로 이동하여 다시 탐색하는 방법을 사용하였다. 어찌어찌 이상한 방법으로 문제를 해결하였지만 알고리즘 분류를 확인하고서 플로이드 와샬이라는 것을 알게 되었다. 우선 내가 푼 방법을 공유하고 다시 플로이드 와샬로 문제를 풀어보도록 하겠다...

처음 문제를 봤을때 무식하게 이동하려는 채널의 자릿수를 확인하면서 누를 수있는 버튼중 차이가 가장 작은것을 선택할 생각을 하였다. 하지만 다음 입력 예제를 가지고 생각해 보았을때 처음 생각한 방법으로 답을 구할 수 없는 것을 할게 되었다. 500000 6 0 2 3 6 7 8 위의 입력으로 버튼을 눌러서 500000과 최대한 가깝게 이동할 수 있는 곳은 499999 이다. 하지만 처음 생각한 방법으로 각자리의 차가 가장 작은것을 선택하게 된다면 511111이 된다. 이럴 경우 정답은 7인데 오답 11117이 나오게 된다. 이를 해결 하기 위해 각 자리마다 경우의 수가 붙게 되는데 이를 찾는 것 뿐만 아니라 구현하는 것도 왠지 이 방법으로 문제를 풀었다고 해도 어디선가 반례가 나올것 같았다. 여기서 생각한..

이 문제는 N*N 크기의 종이를 모든 부분이 같은 색으로 칠해져 있을때 까지 N/2*N/2로 계속 나누면서 각각 1을 파란색, 0을 하얀색으로 나타내고 이때 파란색 색종이와 하얀색 색종이의 갯수를 각각 출력하는 문제이다. 풀이 방법은 재귀를 이용한 방법이다. 전체 종이 길이 N에 대해서 재귀를 반복할 때마다 색종이의 한변 길이를 N/2 씩 줄여나가면서 1사분면,2사분면,3사분면,4사분면으로 분할하여 탐색하면 된다. 이렇게 분할 하였을때 가장 중요한 부분은 범위이다. (1,1)을 기준으로 모든 사분면의 범위를 구하는 방법은 다음과 같다. 1사분면 : (1,1) / 2사분면 : (1,1+N/2) / 3사분면 : (1+N/2,1) / 4사분면 : (1+N/2,1+N/2) 이 되고 이를 일반화 하면 1사분면 :..