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

문제링크 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이 분류: 트리순회 + 이진탐색 느낌? 몰라서 풀이를 참고했다 ㅜㅜ 노드 클래스를 만들어서 풀려 하니까 insert, find 등의 함수를 다 구현해야하나 싶었다. 참고 풀이를 설명하자면, 전위 순회로 받았기 때문에 처음 입력값인 50이 루트 노드 이다. 이진 트리이기 때문에 루트보다 큰 값은 오른쪽에 위치하게끔 인덱스를 설정해준다. 그 인덱스를 기준으로 왼쪽 서브트리를 돌..

문제 링크 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 문제 풀이풀이 설명분류: 그래프 이론, 그래프 탐색, 구현 이동 중 벽을 만났을 때 부수고 가야할지 말아야할지, 어떤게 최적인지 현재 좌표에서 어떻게 알 수 있는지를 고민하다가 결국 풀이를 참고했다. 이런 경우엔 그래프 탐색에서 많이 사용하는 방법이라고 한다. (질문 게시판에 너무 좋은 글이 있다.)-> 모든 벽을 한번 부수고 다 탐색하는 완전탐색을 하기엔 시간초과인..

누적합 (1) (A+B) % M : 구간의 합이 mod인 경우 모듈러 연산 사용 -> 나머지 배열 만들기 예시문제 1. 백준: 10986 "나머지 합" (2) (A+B) = T : 구간의 합이 T인 경우 이중포인터 사용(범위 늘리기용) O(N) 예시문제 1. 백준 1806 부분합 2. 백준 2143 두 배열의 합 # 범위가 큰 경우 O(nlogn) 을 위한 "이분탐색" 사용. bisect 그래프이론 (1) BFS + 3차원배열/큐: 이동할 때마다 현재 상태에 따라 조건이 바뀌는 경우 (이동 좌표 & 현재 상태)를 큐에 같이 저장한다. 예시문제 백준: 2206 "벽 부수고 이동하기" 백준: 1600 말이 되고픈 원숭이 백준: 7569 토마토 트리 - 공통은 재귀함수를 사용하는 것 (1) 입력값으로 트리를 ..