정신차려 하프물범 정신차려 하프물범

문제 링크 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 풀이 설명 분류: 문자열 replace 를 썼더니 시간초과 replace 의 빅오: O(문자열의 길이 * (교체할 문자열의 길이 + 교체되는 문자열의 길이/교체할 문자열의 길이)) 그러므로 replace > slice > del 순서로 시간이 적게 걸린다는 것을 생각하자. 안될 경우 slice/del 로 바꿔보기 slice - O(L[a:b]) => O(b-a) de..

문제 링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 풀이 설명 분류: 구현, 완전탐색 우선 한 좌표를 시작점이라고 생각하고 5가지 블록 * 4(회전) * 2(대칭) * 모든 좌표(500*500) = 1천만 -> 2초이므로 완탐 가능 5가지 블럭 모양에 대해 회전, 대칭을 다 그려본다. 그러면 네모 모양과 막대 모양, ㅜ 모양, 복잡한 꺾인 모양은 8가지로 안만들어도 돌려도 같은 모양인 경우가 나올 것이다. 이를 제외하면 총 19가지..

문제 링크 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 풀이 풀이 재귀함수를 이용해서, 지우려는 노드를 실제로 dict 형태를 가진 Tree에서 삭제시키는 것. 삭제 진행 자식 길이가 0이면 해당 노드 삭제 돌아와서 본인 삭제 삭제 과정 후에 자식이 0인 것을 센다. import sys input = sys.stdin.readline sys.setrecursionlimit(100000) N = int(input()) Tree = ..

문제 링크https://www.acmicpc.net/problem/7569 7569번: 토마토첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,www.acmicpc.net 문제 풀이풀이 설명분류: 그래프이론1 익은 것, 0 안익은것, -1 없음1 부터 BFS 전파 (1의 위치를 담은 큐)큐가 끝날때까지 반복, 큐가 끝났을 때, 0이 1개라도 있으면 -1  (원래 토마토 자리를 알아놓자)안익은 토마토가 익는 0 -> 1로 변하는 것이 모든 0의 수와 같은 count면 전부 익었다고 할 수 있다.코드# - 익은 토마토의 자리 위치, 토마토 ..

문제 링크https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로www.acmicpc.net 문제 풀이풀이 설명분류: 그래프 이론, 그래프 탐색, 구현 이동 중 벽을 만났을 때 부수고 가야할지 말아야할지, 어떤게 최적인지 현재 좌표에서 어떻게 알 수 있는지를 고민하다가 결국 풀이를 참고했다. 이런 경우엔 그래프 탐색에서 많이 사용하는 방법이라고 한다. (질문 게시판에 너무 좋은 글이 있다.)-> 모든 벽을 한번 부수고 다 탐색하는 완전탐색을 하기엔 시간초과인..

문제 링크 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 풀이 풀이 설명 분류: 누적합 모듈러 합의 개념을 알아야 함. (A + B) % M = ((A % M) + (B % M)) % M 덧셈 뿐 아니라 뺄셈, 곱셈 다 해당됨 구간의 합은 누적합 배열에서의 차와 같다. ex. i~j 까지의 부분합 = sum[j] - sum[i-1] 그러므로, 구간의 합 % M = 0 -> (sum[j] - su..

1. 문제 링크 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 2. 풀이 분류: 누적합, 투포인터 (10 ≤ N < 10만 )과 S (0 < S ≤ 1억) 이므로 O(n)으로 풀어야지, 이중 반복문으론 아무리 break를 걸어도 시간초과 남. while 문 1개로 돌리기.. 누적합 배열 만들어서도 해봤는데 왜 시간초과 나거나 틀렸다고 하는지 모르겠움🤦‍♀️(아직 풀이중) import sys input = sys.stdin.rea..

1. 문제 링크 https://www.acmicpc.net/problem/1182 2. 풀이 n, s = map(int, input().split()) array = list(map(int, input().split())) cnt = 0 def dfs(idx, sub_sum): global cnt if idx >= n: return sub_sum += array[idx] if sub_sum == s: cnt += 1 dfs(idx + 1, sub_sum) dfs(idx + 1, sub_sum - array[idx]) return dfs(0, 0) print(cnt) 3. 후기 백트래킹 문제 유형은 index의 값을 어떻게 넘기는지에 따라 조합, 순열 등 결과에 영향을 많이 받습니다. 대체로 문제에서 시키..