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

문제 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 (2번~ n번) 모든 전구는 i번째를 눌렀을때 i-1번째의 전구 상태를 마지막으로 결정한다. i번째가 누를지 말지에 따라 i-1번째의 전구 상태가 정해지고 뒤로 가면 i-1번째 전구는 바뀌지 않는다. 그러므로 i번째의 전구를 누를지말지는 i-1번째의 상태와 목표 전구의 상태를 비교하며 결정한다. (1번 전구 설정하기) 그럼 초기값인 0번째의 전구를 누를지 말..

문제 https://www.codetree.ai/missions/2/problems/beautiful-number?&utm_source=clipboard&utm_medium=text 풀이 - 백트래킹의 기본은 종료조건. 종료조건으로는 (배열의) 길이인 경우가 많다. - 백트래킹을 잘 못해서 해설을 봤음 ㅠ 연습 좀 해야될거같다 종료 조건은 아는데 아름다운 수를 재귀로 어떻게 판단할지 모르겠음 - 연속하는 수의 시작 위치를 찾아내는 방법이다. - 위치(i) + 그 위치의 연속하는 숫자(arr[i]) 를 하면 숫자 만큼 연속해야되기때문에 다음 연속하는 수의 시작위치를 의미한다! n = int(input()) def is_beautiful(arr): # 연속하는 해당 숫자의 시작 위치를 찾기 i = 0 whi..

문제 링크 https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 풀이 처음엔 단순히 N(상자 개수)개의 누적합 테이블(dp)을 만들어, start, end, mid를 통해서 dp[mid]의 도토리 개수에 따라 mid를 파악하려 했다. [시간 초과 난 코드] import sys input = sys.stdin.readline N, K, D = map(int, inpu..

문제링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 풀이 - combinations로만 풀기엔 시간초과가 나는게 뻔해서 고민했다. 완전 탐색 문제인데 어떻게 다 돌지? - 질문게시판에 플로이드 워셜로 하면 금방 다그래서 봤더니 진짜 금방이다:) - 모든 지점 -> 모든 지점은 플로이드워셜, 최단 경로 알고리즘으로만 생각했는데 완전 탐색도 포함이니까 잊지말자! from itertools import combin..

리스트의 주요 연산 시간 복잡도 입력 순서가 유지, 내부적으로는 동적 배열로 구현되어 있다. 연산 시간복잡도 설명 len(a) O(1) 전체 요소의 개수를 리턴한다. a[i] O(1) 인덱스 i의 요소를 가져온다. a[i:j] O(k) i부터 j까지 슬라이스의 길이만큼 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다. elem in a O(n) elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다. a.count(elem) O(n) elem 요소의 개수를 리턴한다. a.index(elem) O(n) elem 요소의 인덱스를 리턴한다. a.append(elem) O(1) 리스트 마지막에 elem 요소를 추가한다. a.pop() O(1) 리스..

문제https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치www.acmicpc.net 풀이시뮬레이션, 구현방향성 조건때문에 헷갈려서 시간이 너무 오래걸렸다 ㅜㅜㅜㅜ 시뮬레이션은 ㄹㅇ 독해가 중요한듯,,모여진 파이어볼의 방향이 모두 짝이거나 홀이면 -> [0, 2, 4, 6], 그렇지 않고 섞여있는 방향이면 -> [1, 3, 5, 7] 이다.import mathfrom copy import deepcopy# move# 일단 방향대로 속력만큼 움..

문제 https://www.acmicpc.net/problem/21315 21315번: 카드 섞기 마술사 영재는 카드 더미를 이용한 마술을 개발하였다. 카드들에는 1부터 N까지의 숫자가 적혀있으며 초기 상태에는 1이 맨 위에 있으며 N개의 카드가 번호 순서대로 쌓여있다. 영재는 마술을 www.acmicpc.net 문제 풀이 - 분류: 완전탐색, 시뮬레이션 N, K의 크기가 크지 않아서 완전탐색 가능 ( 3중 for문을 돌려도 100 * 2 * 10 = 2000번 정도??.. 2^k 중복조합을 이용해서 모든 k의 경우의 수를 구해주었다. from itertools import product max..

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