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

누적합은, 보통 이중 반복문(배열 문제)으로 시간 초과가 될때 구간합을 O(1)로 줄여주는 경우가 많아서, 종종 쓰인다. 누적합 사용 유형구간 합 구하기: 배열에서 여러 번 특정 범위의 합을 구하는 경우, 배열의 누적합을 미리 계산해 두면 각 구간의 합을 빠르게 구할 수 있습니다.예시: 주어진 배열에서 여러 번 "i번째 원소부터 j번째 원소까지의 합"을 구하는 문제.최소/최대 구간 합: 배열에서 특정 길이의 구간 중 가장 큰 합 또는 가장 작은 합을 구하는 문제에서, 누적합을 활용하면 구간 합을 효율적으로 계산할 수 있습니다.예시: "배열의 부분 배열 중 합이 가장 큰 구간을 찾아라"와 같은 문제.차이 배열: 누적합을 활용하여 배열에서 구간별로 값을 추가하거나 뺄 때, 전체 배열을 매번 갱신하지 않고도 ..

Dequestruct Deque { private var array: [T?] private var head: Int private var tail: Int private var capacity: Int init(capacity: Int) { self.capacity = max(1, capacity) self.array = Array(repeating: nil, count: self.capacity) self.head = 0 self.tail = 0 } var isEmpty: Bool { return head == tail } var isFull: Bool { ..

1. 문제 링크https://level.goorm.io/exam/49101/%ED%99%98%EA%B2%BD%EA%B3%BC-%EC%A5%90-%ED%81%AC%EA%B8%B0%EC%9D%98-%EC%83%81%EA%B4%80%EA%B4%80%EA%B3%84/quiz/1 구름LEVEL난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다.level.goorm.io 문제 풀이집단에 있는 쥐 크기를 기준으로 [x - 2, x + 2] 범위의 숫자들만 대표값이 될 수 있다.그러므로 대표값이 될 수 있는 숫자들을 a_size, b_size로 모두 넣어 탐색한다.(10 ** 5) * 5(범위값) 이므로 시간 복잡도에도 걸리지 않음.코드from collections import Counter, deq..

TreeMap (SortedDict)TreeMap은 균형잡힌 이진트리 구조로 데이터를 관리해주는 자료구조 이다.- 각 노드는 (key, value) 쌍 형태로 들어가고, key를 기준으로 노드의 위치를 결정한다- 따라서 삽입, 삭제, 탐색 등 모든 함수의 시간복잡도가 전부 O(logN)이다.- TreeMap 자료구조는 built-in function이 없다- sortedcontainers 라는 외부 라이브러리가 필요from sortedcontainers import SortedDict차이점1. 선언sd = SortedDict()2. keys(), items()와 같이 저장된 데이터를 순회할 때, 자동으로 key 기준으로 오름차순 순회 된다.대체로 "오름차순" dictionary 출력이 필요한 문제에 쓰이..

문제 링크https://www.acmicpc.net/problem/11729할때마다 까먹는 하노이탑.. 제대로 이해를 못한거같아 밑에 블로그를 보면서 정리해봤다. [참고] https://mgyo.tistory.com/185문제점N -1개의 원반으로 두번째 막대로 옮겨야한다는 것은 알았음재귀로 이 문제를 어떻게 풀어낼지에 대해 막힘 풀이재귀란? 같은 형태의 보다 작은 입력을 지닌 자기 자신을 호출하는 것, 재귀적인 호출을 사용하는 함수를 “재귀함수”라고 한다.그렇다면 이 문제는 재귀의 여지가 있는가?hanoi(N): N개의 원판을 ~~~해서 다른 곳으로 옮기기hanoi(N-1): N-1개의 원반을 ~~~해서 다른 곳으로 옮기기이런 식으로 활용 가능하지 않을까?그럼 hanoi(N) 함수를 반복적으로 사용할 ..

1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/12987 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 설명xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.각 사원은 딱 한 번씩 경기를 합니다.각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리..

1.문제https://softeer.ai/app/assessment/index.html?xid=132454&xsrfToken=i9dyxMu8sCXqxYFy3CT6AkZMoUoaYcXW&testType=practice2.풀이완전탐색으로 풀기엔 n, m 풀이 힌트에선 multi-source bfs 라고 하던데, 쉽게 말해 모든 칸에서 직접 다 움직이는게 아니고,하나의 유령 좌표를 알아놓고, 그 유령이 움직이는(상하좌우) 좌표를 미리 다 표시해두는 것이다.일반적으로 4개의 방향을 갈때마다 그 위치를 q.append 해주는 방식 + visited를 합쳐놓은 거라고 보면 된다.[코드 풀이]벽, 탈출구만 써있는 board 배열을 만들고, 나머지(남우, 유령)는 다 좌표로 저장한다먼저 유령 좌표를 모두 받아놓고 ->..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17680 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음엔 아래와 같이 직접 cacheSize를 측정했는데,, deque([], maxlen=3) 처럼 정의하면 append 했을때 maxlen 사이즈를 넘어가면 알아서 왼쪽 원소를 pop한 후 append 한다. from collections import deque def solution(cacheSize, cities): answer = 0 n = len(cities) q = deque..