빠르게 성장하는 개발자

연속된 k 값들의 합중에서 가장 큰 값을 출력하는 문제의 대표유형21921번: 블로그https://www.acmicpc.net/problem/21921 풀이하는 유형은 다양할 것이다. 슬라이싱을 사용할 수도 있고 이중 반복문을 돌릴 수도 있겠다. 하지만 이것은 시간 초과가 날것이다!!! 최적화를 위해 새로운 알고리즘을 탐색하던 중에 슬라이딩 윈도우 를 공부하였다. 투포인터 슬라이딩 윈도우부분 배열의 크기가 고정적이라는 특징이 있다. 창문을 미는 것처럼! 한 칸씩 옆으로 움직이면서현재의 value를 저장하는 변수한 칸 오른쪽으로 이동하고, 대신 가장 왼쪽의 값을 value에서 빼는 방식으로 반복문을 배열의 길이만큼만 돌면 된다는 최적화를 이뤄낼 수 있다.# N, X : 블로그를 시작한 일수, 특정 기간 i..

1. 힙(Heap) 이란? 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리짧게 힙(Heap)이라고 줄여서 부르기도 한다. 힙은 항상 완전 이진트리의 형태여야 한다.출처 : 나무위키 1. 완전 이진트리?포화 이진트리 ( 모든 잎의 level 이 동일한 이진트리. 잎이 아닌 노드들은 모두 2개의 자식을 갖는 트리 ) 를 오른쪽 leaf 부터 제거해서 얻어진 트리. 2. 시간 복잡도데이터의 삽입과 삭제에는 O(log(N))O(log(N))O(log(N))의 복잡도가 소요된다고 한다. 3. 우선순위 큐와 힙일반적인 큐(Queue)는 First in-First Out 구조입니다.즉, 어떤 부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조였습니다.하지만 우선순위 큐(Prior..

하나의 리스트에서 이 단어가 몇 번 나왔는지 검색하려면 어떻게 해야할까. 알파벳 순, 반대로 알파벳 역순으로 정렬하려면? tuple에서 첫번째 원소가 아닌, 두번째 원소 혹은 다른 원소로 정렬하려면? dictionary는 중복된 키 값을 허용하지 않았던가? 효율적으로 개수를 세는 방법은? 이런 여러가지 물음표들을 머릿속에 가득 안은 채 문제를 풀었다.일단 시간초과가 여러번 났는데, 빠른 입출력을 해주니 시간이 많이 줄었다. 백준에서 빠른 입출력 받는 방법input()대신 sys를 사용하면 된다. 입력받으면 \n이 포함되기 때문에 rstrip()을 함꼐 사용해야 한다.import sys a = sys.stdin.readline.rstrip()python 에서 dictionary 의 특징dictionary는..

알고리즘 문제 풀이시 기본이 되는 것은 이중 List를 다루는 것이다.입력받는 것부터 기억나지 않아 Python 기본을 다시 시작해보자면3 1 2 3 4 5 6 7 8 93 123 456 789name = list(map(int, input().split()))을 통해서 int형태로 받을 수 있다. string이 이어져있는 경우는 split 없이 받을 수 있다. list에서 index와 for문이 같이 필요한 경우에는 enumerate를 사용하면 된다.⇒ tuple 형태로 변환⇒ start를 사용해서 index를 0 이 아닌 1부터 사용가능하다.nums = ["A", "B", "C"] for i, num in enumerate (nums): # 0 A 1 B 2 C print(i, num, end=" "..

단순한 BFS 문제였다.처음에 생각을 잘못한 부분은 → NxN 에서 가장 큰 마른모는 N일때 발생한다고 생각했는데,N+1 일때 발생한다는 것이 key 였다. (그것때문에 49/50 개 pass 였다. 😿) 실제로 예시의 사진을 보면, 3x3 배열이 쏙 들어가는건 마름모가 k=4 일때임을 알 수 있다!앞으로 이런 디테일에 더 주의해서 문제를 풀어야 겠다.from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS 함수를 입력 def BFS(i, j, k): global house q = deque() q.append((i, j)) cnt = 1 if homes[i][j] == 1: house += 1 while cnt < k: for ..

파도반수열…?개념이 조금 낯설 뿐, 피보나치와 비슷하다는 힌트를 보고 자연스럽게 점화식?을 생각하게 되었다.하지만! 그냥 늘어진 숫자만 보고서 어떤 규칙을 찾는담? 하고 막막한 생각이 들었다.# 직접적인 관계 찾아보기 P(4) = P(1) + P(3) P(5) = P(4) P(6) = P(5) + P(3) P(7) = P(6) + P(2) P(8) = P(7) + P(1)결국직접적인 관계는 아니지만! 간접적인 관계가 있음을 확인할 수 있었다.n > 5에서는, P(n) = P(n-5) + P(n-1) DP와 메모이제이션을 이용해서 구현하기피보나치 수열도 마찬가지로, 이미 구한 값을 또! 재귀로 호출할 필요 없이 메모이제이션을 사용해서,한 번 부른 값을 기억해두면 시간초과를 막을 수 있다.import sys..

이번 주를 DP의 주간으로 명명하고 스터디원들과 DP문제만 뿌셔보기로 했다. DP문제를 풀이하면서 풀이 영상이나 풀이법들을 보면 → 2차원 배열을 사용하는 경우가 많다.그래서 이번 문제를 풀면서 나의 의식의 흐름도 자연스럽게 💡2차원 배열로 접근해봐? 란 생각이 들었다. 이 문제는 얼핏보면 간단한데, 결국 문제의 핵심은연속으로 3개의 계단을 밟으면 안된다!! 이다. 연속으로 계단을 밟아도 된다면, 모든 계단을 밟아서 도달하는 쪽이 가장 점수가 높을 테니까,DP로 문제를 풀면서 점화식을 생각해보면서, 역으로(맨 마지막에서 → 처음으로) 생각해 보는 경우가 많아진다.예를 들어 이 그림에서 마지막 ‘도착’ 까지 가는 경우의 수를 생각해보자.연속으로 3칸을 밟지 못한다고 하였으므로 15까지 오는 경우 → 10을..

1. DP (Dynamic Programming)?큰 문제를 작은 문제로 ‘쪼개어’ 생각하는 것크게 위에서부터 아래로 문제를 쪼개서 내려가는 Top-down 방식과, 아래에서부터 더해 올라가는 Bottom-up방식이 있다.DP의 전형적인 유형이 몇 가지 있고, 평범한 배낭문제도 그 중 하나에 속한다.2. 평범한 배낭문제생각하기가 힘들어서 검색의 힘을 빌렸다. 그런데 검색을 안했으면, 내 머리로는 절대 생각해 내지 못했을 것 같다.DP에서 알고리즘의 벽을 느끼고 있다.완전히 이해하고 작성하는 글이다.문제는 백준 12865 평범한 배낭 글의 예제를 사용하도록 하겠다. 3. 준비과정이차원 배열이 필요하다. 이차원 배열에는 각 상황에 대한 가치의 최대값을 저장한다.예를 들어 배낭에 들어갈 수 있는 총 무게가 7..