문제https://www.acmicpc.net/problem/9935 사용 알고리즘문자열, Stack 풀이고려사항1. 시간 제한이 까다로운 문제2. 폭발 이전 문자열과 이후 문자열이 합쳐져서 생긴 새로운 문자열 폭발 여부 후기1. 이 문제의 keypoint는 시간관리이다.조건 중 '문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.'와 시간은 2초로 추가시간이 주어지지 않았다.N이 큰 상황에서 최악의 경우 폭발하고 매번 문자열을 순회해야 할 경우 시간 복잡도는 O(N2)이다.따라서 시간 초과가 예상되었다.2. 때문에 무조건 입력받은 문자를 한번만 순회하는 방식을 채택했다.순서대로 스택에 넣으며 현재 문자가 target으로하는 문자의 마지막 문자와 같은 경우에만 확인하는 방법이다.po..

문제https://www.acmicpc.net/problem/1806  사용 알고리즘투 포인터, 누적 합 풀이고려사항1. 시간 제한이 까다로운 문제 후기1. Brute Force가능한 부분 수열 모두를 탐색하는 방식으로 접근했다.시간 복잡도는 O(N2)이다.이때, N의 범위가 10 ≤ N N이 매우 클 때 시간 초과가 발생할 수 있는 코드이다.## 시간 초과 코드 - Brute Force ##import sysinput = sys.stdin.readlinedef find(num_list): for l in range(1, len(num_list) + 1): for i in range(len(num_list) - l): if sum(num_list[i : i + l])..

문제https://www.acmicpc.net/problem/5636 사용 알고리즘Brute Force, 에라토스테네스의 체 풀이고려사항1. 가장 큰 소수인지2. 2  후기두 방법을 사용하여 prime 함수를 정의하였다. 1. Brute Force2부터 주어진 수까지 나누어 중간에 나머지가 0이 될 수 있는지 여부를 확인하였다. 2. 예전 소수 리스트 기록문제 한 번에 1,000개까지 여러 테스트케이스가 존재할 수 있다.때문에 예전 소수들을 저장하는 방식을 구현하였다.prime_lst라는 리스트를 만들고 소수 여부를 확인하여' 0은 아직 확인하지 않은 숫자, 1은 소수, 2는 소수가 아닌 수 '로 분류하여 관리하였다.시간이 줄어들 줄 알았지만, 오히려 메모리가 약간 늘어나고 시간은 줄어들지 않았다.테스트..

문제https://www.acmicpc.net/problem/17144 사용 알고리즘구현, 시뮬레이션 풀이고려사항1. 먼지 확산 - 확산하는 곳이 공기청정기인지, 범위를 넘어가는 곳이 아닌지2. 공기 청정 - 방향전환, 먼지 이동 시 갱신 된 값과 이전 값 구분 후기1. 이 문제에서 어려운 점은 공기 청정 값 갱신이였다.아래 코드는 새로운 배열을 생성한 후 값을 옮기는 방식을 채택했다.하지만 공기 청정하는 라인의 값은 갱신되지만, 그 외의 원래 가지고 있어야하는 값이 0으로 나와 사용할 수 없었다.이러한 방식을 사용하려면 새로운 배열을 0이 아닌 원래 배열에서 deepcopy하여 사용해야 한다.# 잘못된 공기청정 로직def refresh(room): after_room = [[0] * C for _..

문제https://www.acmicpc.net/problem/9465 사용 알고리즘DP 풀이고려사항이전 열(다른 행)의 스티커 가중치가 현재 가질 수 있는 스티커 가중치의 최대인지 후기이 문제의 keypoint는 행이 2개로 고정되어 있으며 점수는 음수가 아닌 것이다.점수가 음수가 아닌 이상 이전 2칸 이상을 고려하지 않아도 된다.처음에는 현재 열이 j이면 0 ~ j-2까지의 리스트 전체에서 max값과 이전 열의 다른 행을 비교했다.하지만 이건 불필요한 작업이였고 다른 행의 이전 2개만 비교하면 된다.그 이전은 이후에 가중치가 음수가 아니기 때문에 하나라도 더 선택하는 것이 큰 값이 되기 때문이다. 코드import sysinput = sys.stdin.readlineT = int(input())for t..

문제https://www.acmicpc.net/problem/2638 사용 알고리즘BFS 풀이고려사항1. 치즈와 맞닿은 공기가 외부 공기인지2. 외부공기와 2면 이상 닿아있는지 후기1. 이 문제의 keypoint는 초점을 치즈가 아닌 외부공기로 두어야한다는 것이다.처음 치즈에 초점을 두고 푸니 맞닿은 공기가 외부인지 내부인지 확인하는 것이 어려웠다.처음에 행을 기준으로 처음과 마지막 치즈 사이에 있는 공기를 내부라고 체크하려 했으나아래 그림과 같이 에서는 가능하지만 과 같은 상황에서 문제가 발생하였다.2. 또한, bfs 알고리즘을 활용하여 코드를 작성 할 때 visited를 사용하여 이미 온 곳을 관리하는데visited에 방문한 적이 있다고 무조건 가지 않는 것이 아닌 점 역시 고려해야 한다.처음에는 방..