알고리즘7 [C++]문자열 검색 KMP 알고리즘 (with 백준 1786) "두 문자열 S, target이 주어질 때 문자열 S에서 문자열 target을 찾고 그 시작 위치를 구하라." 이 문제를 다음과 같은 순서로 해결하고자 한다. 단순한 구현 KMP 알고리즘 KMP 알고리즘과 부분 일치 테이블의 구현 백준 1786 1. 단순한 구현 1) 알고리즘 및 구현 문자열 검색하면 가장 처음에 떠올릴 법한 구현으로, 문자열 S의 시작점을 변경해가며 비교하는 방법이 있다. S = "abcabc", target = "ab" 라고 가정해 보자. 다음 과정을 통해 시작점을 구할 수 있다. begin = 0 문자열 S a b c a b c 문자열 target a b 비교 결과 O O begin = 1 문자열 S a b c a b c 문자열 target a b 비교 결과 X 비교하지 않음 beg.. 2022. 11. 26. [cpp]백준 14266번 나는 가르친다 스위핑을 더보기 오늘 시간 낭비한 것에 대한 푸념 풀이는 맞았는데, 실수로 디버깅하려고 작성한 코드를 안 지워서 정답률 및 시간 손해를 봤다... ㅠㅠ 그것도 두 문제나... 구현이 길어지면 단계별로 테스트하기 위해 다음과 같이 로그를 찍어보는 코드를 넣었는데, 제출할 때 이를 인지하지 못 한 게 사건의 발단이었다. 그래서 위와같이 8번의 맞왜틀을 시전했다. 처음 코드에서 44번 라인만 지우니 맞더라... https://www.acmicpc.net/problem/14266 14266번: 나는 가르친다 스위핑을 영선이는 BOJ 캠프의 강사다. 이번에 스위핑에 대한 세미나를 진행하였는데, 그 연습문제를 만들었다. “1사분면 정수 좌표계에 n개의 점이 주어질 때, 원점을 지나는 직선 중 직선위의 점들이 최 www.ac.. 2021. 9. 19. 알고리즘 및 코딩테스트 언어 고민 중이다. 얼마 전 카카오 블라인드 코딩테스트 본 후 C++ 로는 코딩테스트를 풀기 힘들다고 느꼈다. 물론 여전히 백준이나 알고리즘 대회에서는 C++ 이 최고다. 알고리즘 대회나 백준은 시간 제한이 타이트한 경우가 많아서 같은 알고리즘이라도 순수 파이썬으로는 시간초과 나는 경우가 있다. 또한 채점이 완료되는데 기다리는 시간도 길다. 특히 언어별 추가시간이 없는 경우에도 C++ 로 풀 경우 알고리즘만 맞는다면 시간초과를 볼 일이 없다. 1. C++ 의 한계 사실 한계까지는 아니고 C++ 로도 코딩테스트 다 풀 수는 있는데 많이 불편하다. 코딩테스트 특성상 순수 알고리즘 실력보다는 구현, 실제 개발 위주로 문제를 내려고 하는 것 같다. 물론 뒷번호로 가면 알고리즘을 물어보는 문제가 나오기도 한다. 아무튼 문제 유형에 .. 2021. 9. 19. [cpp]백준 1107번 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이 문제를 본 건 엄청 오래됐다. 3년 전에도 봤었고, 그 뒤로도 몇 번 풀이를 생각했으나 못 풀었던 문제다. 요즘엔 알고리즘을 나름 꾸준히 풀고 있어서 무슨 수를 써서든 풀 수 있을 거란 확신이 있었다. 처음엔 1ms 도 아니고 1μs 안에 돌아가는 알고리즘을 생각했지만, 구현이 매우 어렵고 예외처리도 많이 해야 한다. 그 뒤에 아주 간단한 풀이 방법이 생각 났는데, 왜 이걸 이.. 2021. 9. 12. 백준 14734번 Aztec Diamond (cpp) https://www.acmicpc.net/problem/14734 14734번: Aztec Diamond 첫 번째 줄에 문양의 크기 N이 주어진다. N은 1 이상 100 이하이다. 다음 2N줄에는 문양의 행을 나타내는 길이 2N의 문자열이 주어진다. “.”은 공백, “L”과 “R”은 가로 벽돌의 좌우 칸, “U”와 www.acmicpc.net 이 문제는 스페셜 저지이다. 이런 유형의 문제를 풀기 위해서는 순서를 강제해야 해야 한다. 이 문제도 그런지는 모르겠지만. 종만북이 그랬다. 위에 거 회전했다가 아래 거 회전했다가 하면 중복되는 경우도 잡아내기 힘들지 않겠는가? 이 문제 풀이에 대한 착안은, 블록 하나를 두면 그 블록에 의해서 특정 위치에 특정한 모양으로 존재할 수밖에 없는 경우가 있다는 것에서 .. 2021. 7. 28. 백준 1562번 계단수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net DFS + DP 문제이다. DP를 사용하기 위해, 임의의 숫자로 시작하여 숫자를 하나씩 이어나갈 때 지금 몇 번째 숫자까지 붙였는지, 현재 숫자는 무엇인지, 0~9 숫자를 사용했는지 여부를 판단해야 한다. 근데 사실 0~9 까지의 숫자를 사용했는지 모두 확인할 필요가 없다. 0과 9라는 숫자만 사용되었다면 그 사이에 있는 숫자도 모두 사용되었을 수밖에 없다. 따라서 메모이제이션 배열을 cache 라 하면 cache[101][10][2][2] 이런 식으로 만들 수 있고, 101 은 dfs 의 깊이, 10 은 현재 숫자, .. 2021. 7. 21. 백준 17404 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 그냥 RGB거리랑 다른 점은 첫 번째랑 마지막 번째도 이어져 있다고 가정하는 것인데 내가 알고리즘 초보라 푸는데 시간이 너무 오래 걸렸다... 메모리는 굳이 1000개짜리를 사용하지 않아도 풀이가 가능하다. 그냥 RGB 거리를 풀었다고 생각하고 추가된 아이디어는, 메모이제이션으로 사용한 배열 rgb[a][b] 은 첫 번째 집은 a 로 칠하고, 마지막 번째 집은 b 로 .. 2021. 6. 24. 이전 1 다음
