코딩스토리

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 이전에 KMP알고리즘에 대해 알아 보았었다.그럼에도 문자열 문제는 쉽지 않다. 가장 최근 2020 카카오 코딩 테스트를 보면 문자열 문제가 시작부터 연달아 나옴을 알 수 있다. 그만큼 중요하면서도 어려운 유형이다. 이번에는 접미사를 통해 문자열 알고리즘을 좀 더 확장시켜 보려고 한다. 1. 접미사 배열 문자열을 다룰 때 빼놓을 수 없는 자료구조로 접미사 배열이 있다고 한다. '문자열의 맥가이버 칼' 이라고도 부른다는데 한번 공부해 보도록 하자. 먼저 접미사 배열은 말 그대로 한 문자열의 모든 접미사들을 사전 순으로 배열에 저장해 놓은 것을 말한다. 이때 접미사들을 그대로 저장하면 문자열의 길이..

* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 '문자열'은 간단한 문제여도 쉽지 않은 문제들이 많다. C++의 STL을 사용하며 많은 부분에서 편리함이 생겼지만, 그럼에도 문자열 문제들은 많은 시간이 소요된다. 하지만 문자열 문제는 카카오 코딩테스트 문제 유형에도 자주 나오며 그 외 많은 문제에서 찾아볼 수 있다. 항상 나를 괴롭혀 왔던 '문자열'에 대해 자세히 공부해 보고자 한다. 1. 문자열 검색 문자열을 검색하는 알고리즘에 대해 공부해보자 주어진 긴 '짚더미(Haystack)' 문자열 H가 '바늘(Needle)' 문자열 N을 부분 문자열로 포함하는지를 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 ..

백준 1543번 - 문서 검색 www.acmicpc.net/problem/1543 1543번: 문서 검색 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한� www.acmicpc.net 최근에 KMP알고리즘에 대해 공부 한 뒤라 자신 있게 풀어보려 들어갔다. 문제 n제한과 시간 제한을 보니 KMP 쓰기에도 아깝다고 생각이 들었다. 가볍게 브루트포스로 풀고 넘어가려 했는데... 반전!! 삐빅!! 틀렸습니다. 삐빅!! 런타임 에러. 하... 역시 문제는 풀어도 풀어도 어렵다... 실버 4 문제라고 절대 방심해선 안된다는 걸 깨달았다. 처음 틀렸습니다는 내가 문제를 제대로..

백준 9663번 - N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 백 트래킹 알고리즘 문제이다. 백 트래킹에 대해서 공부하다 보니 백 트래킹의 가장 기본 문제라고 하여서 풀어보았다. 공부하고 풀었는데도 생각보다 어려웠다. 처음에는 2차원 배열로 놓고 모든 지점의 좌표에서 dfs를 돌릴 생각이었는데 생각보다 너무 지저분한 것 같아서 다른 방법을 생각해보다가 구글링을 통해서 알아낸 방법으로 풀었다. 분명 2차원 배열로도 풀 수 있겠지만 ..

백준 2447번 - 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 이 문제는 재귀 알고리즘 문제이다. 단계별로 풀어보기 문제들 중에서 안 풀었던 문제가 있길래 풀려고 보니 별 찍기.. 쉬울 거 같아서 빨리 풀어야겠다 하고 풀었는데 2시간 넘게 고민해도 답이 안 나오네?? 결국 구글링을 통해 알아낸 사실은 2차원 배열을 사용하는 것!! 이 문제의 핵심은 저거였다.. 그것도 모르고 몇 시간을 고민했..