빠르게 성장하는 개발자

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

하나의 리스트에서 이 단어가 몇 번 나왔는지 검색하려면 어떻게 해야할까. 알파벳 순, 반대로 알파벳 역순으로 정렬하려면? 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=" "..

파도반수열…?개념이 조금 낯설 뿐, 피보나치와 비슷하다는 힌트를 보고 자연스럽게 점화식?을 생각하게 되었다.하지만! 그냥 늘어진 숫자만 보고서 어떤 규칙을 찾는담? 하고 막막한 생각이 들었다.# 직접적인 관계 찾아보기 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을..

최종코드는 맨 아래에 있습니다! 내 코드import sys from collections import deque di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] N = int(sys.stdin.readline().rstrip()) # 행, 열의 개수를 나타내는 n arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # arr에 있는 값중에 최소, 최대 값을 찾아서 brute-force를 진행한다. min_num = min(min(arr)) max_num = max(max(arr)) numbers = [i for i in range(min_num, max_num+1)] max_V = 1 def rain(numbe..

N-Queen 문제는 백트랙킹의 대표적인 문제이다.체스의 Queen은 같은 행, 열, 대각선에 대해서 공격할 수 있다.NxN 체스판에서 서로 공격하지 않는 Queen을 몇 개 둘 수 있나? 가 문제이다. 문제는 간단하지만, 풀이과정은 간단하지 않다.처음에는 SWEA에서도 풀이한 문제이기 때문에, 이틀 전에 교수님께서 짜신 코드를 생각하면서 다음과 같이 제출했다.# n-queen def queen(row, k): global cnt if row == k: cnt += 1 return else: for j in range(N): can_position = True # 열 검사 for l in range(0, row+1): if board[l][j] == 1: can_position = False # 대각선 ..

문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같..

문제N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게..

문제수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다.이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사용하..