MZ 개발자

이 문제는 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을 반복해서 수행해야 한다. 처음에는 시뮬레이션 문제인가 헷갈렸다. 알..

안녕하세요. 오랜만에 문어체로 시작하는데요, 학부동안 배운 알고리즘 또는 배우지 못한 다양한 알고리즘 및 자료구조 이론을 정리해보려고 합니다. 설명 과정에 틀린 부분이나 추가해야할 부분이 있으면 언제든지 답글 달아주시면 감사하겠습니다. 오늘 배워볼 알고리즘은 KMP 알고리즘입니다. 문자 검색을 하는 가장 기본적인 방법은 부르트포스 방법으로 순차적으로 패턴을 비교하는 방법이지만 이 방법으로하면 패턴(M)이 길어지거나 문자(N)가 길어진다면 O(NM)의 시간복잡도를 가지게 됩니다. (여기서는 부르트포스 방법은 설명하지 않겠습니다.) KMP (Knuth Morris Partt Algorithm) 앞서 언급했듯이 부르트포스 방법으로 구현한다면 시간 복잡도는 O(NM)입니다. KMP 알고리즘은 부르트포스 알고리즘..

이 문제는 전형적인 분할 정복과 재귀를 사용하여 풀이하는 문제이다. 분할 할때 '('를 출력하고 정복시 ')'를 출력해주면 된다. 이와 비슷한 문제로 백준 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사분면 :..

이 문제는 포켓몬 도감에 수록되어 있는 N개의 포켓못 정보를 가지고 M개의 질문이 들어왔을때 적절하게 결과를 반환해야 한다. 우선 질문은 두가지로 다음과 같다. 1. 포켓몬 이름을 주어질 때 해당 포켓몬이 도감의 몇번째에 존재하는지 2. 숫자가 주어질때 해당 숫자의 포켓몬 이름은 무엇인지 도감에 수록된 포켓몬의 숫자 N는 100,000 이고 질문 M은 100,000 이므로 부르트포스 방법으로는 시간내에 문제를 해결할 수 없다. 따라서 해싱을 통해 O(1) 만에 탐색해야 한다. 숫자가 주어졌을 때 포켓몬 이름을 구하는 방법은 간단하게 배열의 인덱스를 활용하여 해결 가능하다. 하지만 포켓몬 이름이 주어졌을 경우 조금 생각을 해야한다. 만약 이름을 아스키 코드로 변환하여 그 값을 해시값으로 사용한다면 해시충돌..