https://www.acmicpc.net/problem/1593 투 포인터 문제라고 분류 했지만, 정확히는 슬라이딩 윈도우 문제다. 문자열 W의 순서를 바꾸어(순열) 만들 수 있는 문자열이 문자열 S에 몇 개 포함되어 있는지 카운팅하는 문제다. 가장 먼저 떠오른 방법은 W의 길이만큼 슬라이딩 윈도우를 진행하는 것이다.S의 문자열을 W의 길이만큼 잘라서(S') 정렬한 뒤 정렬된 W와 같은지 비교하는 것이다.어림도 없지. 시간 초과다. 작게 나마 시간을 줄여보려 했으나 안된다. 그래서 질문 게시판에서 힌트를 얻었고, 글자 수를 카운트 하는 아이디어를 얻었다.그러나 생각이 짧은 나머지,,, 문자열을 잘라서 각각의 문자 개수를 매번 계산했다.심지어 Counter 함수를 이용했는데 이러면 딕셔너리로 반환이 되기..
분류 전체보기
https://www.acmicpc.net/problem/1389 최단경로 문제다. 그래프가 주어지고 한 점에서 다른 모든 점들까지의 거리가 최소인 점을 찾는 문제다.입력은 연결된 점들의 리스트가 들어온다. 가장 먼저 생각 난 방법은 플로이드 워셜이다.생각은 났는데 공부한 지 좀 지난 개념이라 알고리즘 흐름을 다시 찾아봤다.간단하게 설명하자면, 모든 지점에서 다른 점들까지의 최단 경로를 한 번에 구하는 방법이다.2차원 배열을 이용하고 배열의 각 칸은 i부터 j까지의 최단 거리를 의미한다.3중 반복문(k, i, j)을 통해 min(arr[i][j], arr[i][k] + arr[k][j])를 수행한다.위의 점화식이 의미하는 바는 i부터 j까지 가는 경로 중 k를 거쳐가는 경우의 수를 고려하는 것이다. 플로..
https://www.acmicpc.net/problem/1334 문자열 구현 문제다. 펠린드롬 수라고 해서 1씩 키워서 펠린드롬인지 확인해봐야지 라고 생각했으나 자릿수가 최대 50인 걸 보고 바로 문자열로 틀었다.이전에는 문자열에서 1씩 키워서 확인하는 방법을 사용했던 것 같다. (당연히 시간초과겠지^^) 3년 만에 문제를 다시 보고 바로 든 생각은 중점을 기준으로 비교해나가는 것이었다.해당 수 보다 크면서 가장 작은 펠린드롬 수를 구하기 위해서는 최대한 뒤쪽 수를 높여야 한다. 중점 기준으로 중앙에서부터 왼쪽과 오른쪽 문자를 비교해나간다.왼쪽 문자가 큰 경우 오른쪽 문자만 값을 키우면 되고, 오른쪽 문자가 큰 경우 중점 값을 키우면 된다. 처음에는 문자열 길이가 짝수인 경우와 홀수인 경우를 나눠서 생..
https://www.acmicpc.net/problem/1230 틀렸던 문제 다시 풀기 3일차.골드1을 보고 당황 했지만,,, 하루에 딱 한 시간만 투자한다는 생각으로 도전했다.4일정도 걸린 것 같은데, 문제를 고민하는 데 2일, 인터넷에 다른 코드를 이해하는 데 2일이 걸렸다. 문자열 O를 N으로 만들기 위해 추가해야 하는 최소 '문자열'의 개수를 구하는 문제다.우선, 내 머리만으로 해결하진 못 했다. 처음에는 단순하게 앞에서부터 비교하면서 O에 없는 문자를 카운트 했다.연속 여부를 고려해 문자열 개수를 카운트 했다. (틀린 방법이니 자세히 설명하진 않겠다.) 그리고 2차원 표에 O[:i] 를 이용해 N[:j] 를 만드는 데 필요한 최소 문자열 개수를 구했다.근데 정말 이리보고 저리봐도 규칙을 끌어낼..
https://www.acmicpc.net/problem/1182 틀렸던 문제 재도전 두 번째다.브루트포스, 백트래킹 문제다. 처음 문제를 보고 이걸 효율적으로 어떻게 탐색할까... 고민을 했다.우선 내가 이 문제를 이전에 틀렸었던 이유는 부분수열의 의미를 잘못 파악했기 때문이다.무조건 연속되는 부분 수열일 것이라고 생각했는데, 임의의 숫자를 선택해서 만들어도 부분수열이었다.(부분 수열의 확실한 개념은 원래 항에서 무작위로 데이터를 삭제해도 되지만, 그들의 순서는 유지되어야 한다.) 처음 생각한 건 투 포인터가 떠올랐는데, 부분 수열을 잘못 알고 있었기에 정렬을 하면 안된다고 생각했다.(제대로 알고 있었어도 못 쓰는 방법이다.ㅋㅋㅋ) 그다음은 누적합을 생각했는데 범위가 괜찮으려나 하고 확인해봤더니 수열의..
https://www.acmicpc.net/problem/1022 백준 문제 중 '시도했지만 맞지 못한 문제' 도장 깨기를 해보려고 한다.구현 문제다.중앙부터 시작해 돌아 나오는 소용돌이 중 (r1, c1) 부터 (r2, c2)를 출력하면 되는 문제다. 소용돌이 최대 크기가 10001 x 10001 이라서 그냥 만들어 놓고 범위만 출력하면 안되나? 했는데 어림도 없다.열심히 규칙을 찾기 위해 이리 저리 숫자 놀이를 해본 결과 8이라는 숫자를 이용할 수 있었다.1을 중심으로 8방향으로 점점 커지는 숫자들의 규칙이 (공차가) 8씩 증가했다.위로 가는 걸 기준으로 1 4 15 34 --- 이 숫자들이 간격은 3 11 13 --- 간격의 간격이 모두 8이었다.8방향 모두 같은 규칙이고, 간격의 시작점만 달랐다...
