https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 다익스트라 문제인데 아니 이걸 왜이렇게 오래 뇌절을 쳤는지 모르겠다 엉엉엉 시작점 S에서 이동하는 서커스 예술가가 갈 목적지 후보 중에서 G-H간 도로를 건너 이동해야 하는 경로를 구하는 문제. 즉, 목적지 후보를 K라 할때, S-K 로 이동하는 최단경로가 S-G-H-K 이거나 S-H-G-K 이면 가능한 경우에 해당하고, S-K로 이동하는 최단경로의 길이가 S-G-H-K 이거나 S-H-G-K..
https://www.acmicpc.net/problem/16900 16900번: 이름 정하기 첫째 줄에 S와 K가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 500,000보다 작거나 같다. K는 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net fail 배열이 가지고 있는 값이 접두사와 접미사가 같아지는 최대 길이임을 이용하는 문제. 문자열 두개를 최대한 많이 겹쳐내면 전체 문자열의 길이가 가장 짧아지게 되기 때문에 가장 적극적으로 겹쳐내기 위해서 실패함수 값이 담긴 배열을 구해준다 가장 적극적으로 겹쳤을 때 전체 문자열의 길이는 (전혀 겹치지 않았을때의 최대 길이) - (겹쳐진 부분만큼의 길이) 이고 겹치지 않았을때의 최대 길이는 S.length() * K 로 ..
파이썬 스터디용으로 풀었던 문제. 파이썬어려워요 흑흑 https://www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 처음에는 입력값을 그대로 스택에 넣고 괄호쌍을 만날때 되돌아가는 방식으로 정답을 구했는데, 반례로 123(12)123(12) 와 같이 괄호쌍 두개가 떨어져있는 경우에는 제대로 계산을 못한다. val = input() st = [] ans = 0 for i in val : if i != ')' : st.append(i) else : whil..
언제나와같이 돌아온 KMP 아주 티어 올리는 맛이 달달한 태그다 https://www.acmicpc.net/problem/1893 1893번: 시저 암호 암호학에서, 시저 암호(또는 시프트 암호, 시저 코드, 시저 시프트)는 가장 간단하면서 많이 알려진 암호화 기술 중 하나이다. "시저 암호"라는 이름은 비밀 통신을 위해 이 방법을 개발한 율리 www.acmicpc.net 지문이 이해하기 그리 쉽지 않은 편인데 간단히 요약해보자면 알파벳 순서 표 A를 보고 원문 W를 X칸 이동시키면서 변환한 뒤에, 암호화된 문자열 S에서 변환된 W가 한번만 등장한다면 이때 가능한 모든 X를 찾는 문제이다. 문제를 나눠서 생각해보자. 1. 순서표 A를 보고 W를 한칸씩 이동시키기. 알파벳과 숫자를 매칭시켜 주는 unord..
https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 두 공장을 잇는 가중치의 최솟값이 최대가 되게 하는 문제. 이렇게말하니까 되게 어려워보인다;; 문제의 핵심은 중량제한이 낮은 다리는 굳이 건널 이유가 없다는 발상. 중량제한이 높은 다리들만 이용해서 두 공장을 연결할 수 있다면 정답에 쉽게 도달할 수 있을것이다. "두 공장을 연결할 수 있다면" >> 유니온파인드를 이용해서 두 공장이 연결됬..
상당히 까다로웠던 문제 좀 푸는데 오래걸렸다 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 구하고자 하는 걸리는 날을 T라고 할때, 매일매일 vis배열을 초기화하면서 호수를 탐색하면 시간초과나 메모리초과를 받게 된다. 첫째날에 대부분을 미리 탐색해 놓고, 두번째 날부터는 얼음과 물의 경계선에 해당하는 부분에서만 탐색을 진행해주면 연산량이 극적으로 감소하면서 시간초과 / 메모리초과 둘다 잡히는듯. 큐 두개를 활용해서..