De plus en plus

더보기 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 아래와 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 또 다른 예로 위와 같은 온도가 주어졌을 때, 모든 연속적인 5일 간의 온도의 합은 아래와 같으며, 이때, 온도의 합이 가장 큰 값은 31이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. 입력 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진..

그리디 알고리즘 문제를 풀기 위해서는, 최적의 해결 방법을 찾아야 한다. 최적의 풀이 방법을 생각해내지 못하고, 완전탐색으로 억지로 풀고자 한다면 시간 초과가 날 수밖에 없다. 최초에 이 문제를 풀면서도, 단순 정렬만을 하고 완전탐색으로 풀었다가 시간초과의 덫을 빠져나올 수 없었다. 하지만 이내 좋은 방법을 찾아내어, 시간 초과 문제를 해결할 수 있었다. import sys input = sys.stdin.readline lst = [] for _ in range(int(input())): lst.append(list(map(int,input().split()))) lst.sort(key=lambda x : (x[0],x[1])) time = [] for i in range(len(lst)): res =..

알고리즘 공부를 공부할때마다 느끼는 것이 있다. 알고리즘 공부는 비단 프로그래밍 실력만을 상승시킬뿐만 아니라, 공부하는 사람의 사고까지도 효율적으로 흘러갈 수 있도록 변화시킨다는 것이다. 구간합이란, 연속으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 것을 의미한다. 배열 [10, 20, 30, 40, 50]이 있다고 하면, 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 보통 구간합 문제가 나오면, 여러 개(M개)의 쿼리를 주고 해결하라는 형식으로 출제된다. 만약, 이 방법을 숫자가 주어질때마다 해당 배열의 수를 뒤져가며 매번 더하게 된다면 시간 복잡도는 O(NM)이 될 것이다. 그런데, 접두사 합(prefix sum)이란 방식을 사용한..

이진 탐색에 대해 공부하였다. 파이썬의 리스트 자료구조에서, for문을 통해 첫번째 인덱스부터 마지막 인덱스까지 순차적으로 탐색을 하였다가는 시간 복잡도 문제를 문제를 벗어날 수 없게 된다. 이러한 문제를 해결하기 위하여, 이진 탐색 아이디어를 활용할 수 있다. 이진 탐색 이진 탐색이란, 리스트를 절반으로 쪼개어 탐색하는 과정이다. 0 1 2 3 4 5 6 7 8 9 라는 리스트가 있다고 할 때에, 찾고자 하는 수가 0~4와 5~9 중 어디에 있는 지를 파악하고, 만약 전자의 범위 내에 있다면 전자의 범위에서, 그 반대라면 후자의 범위 내에서 탐색하는 방법이다. 이러한 이진 탐색을 구현하는 방법은 두 가지 방법이 있는데, 하나는 재귀 함수를 이용하는 방법이고, 다른 하나는 반복문을 사용하는 방법이 있다...

BFS와 DFS에 대하여 공부하고 있다. 그 중 BFS란, 너비 우선 탐색을 의미한다. 가까운 노드들부터 우선적으로 탐색한다는 것이다. 이에 해당 개념을 잡기 위해, 수 차례 의미를 생각하며 코드를 쳐보았지만 아직 부족함을 느꼈다. 이에 BFS 개념을 적용해보고자, 백준 OJ에서 다음과 같은 문제를 찾아 풀어보았다. 문제 ‘쩰리’는 점프하는 것을 좋아하는 젤리다. 단순히 점프하는 것에 지루함을 느낀 ‘쩰리’는 새로운 점프 게임을 해보고 싶어 한다. 새로운 점프 게임의 조건은 다음과 같다.‘쩰리’는 가로와 세로의 칸 수가 같은 정사각형의 구역 내부에서만 움직일 수 있다. ‘쩰리’가 정사각형 구역의 외부로 나가는 경우엔 바닥으로 떨어져 즉시 게임에서 패배하게 된다.‘쩰리’의 출발점은 항상 정사각형의 가장 왼..

DFS와 BFS 코딩테스트를 준비하는 사람이라면, 누구나 반드시 공부해야하는 알고리즘 중 하나라고 한다. 나 또한 공부해야지, 공부해야지, 했지만, 이런 저런 이유를 핑계로 미뤄 두다가 이제야 다시 시작해본다. DFS 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 이용한다. 하지만, 구현 상의 한계가 있어 스택 자료구조를 직접 이용하기 보다는 재귀 함수를 사용하여 구현한다. def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph..

그리디 알고리즘 그리디 알고리즘이란, 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이다. 달리 말해서, 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 정렬, 최단 경로 등의 알고리즘들은 그 사용법을 정확히 알고 있어야만 해결할 수 있다. 이와 달리, 그리디 알고리즘으로 분류되는 다익스트라 알고리즘을 제외하면, 그리디 알고리즘은 그 사용법을 굳이 외우지 않아도 풀 수 있을 가능성이 매우 높다. 그리디 알고리즘은 그 풀이법이 매우 다양하다. 그것은 즉, 그만큼 문제를 풀기 위한 창의력, 다른 말로는 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 아이디어를 요구한다는 의미와 같다. 그만큼 그리디 알고리즘은 다양한 유형의 문제를 풀어보며 그 유형에 익숙해질 필요가 있다. 또한, 정렬 알고리..

BOJ 23253번, 자료구조는 정말 최고야 자료구조 중 스택에 대해 공부하였다. 스택이란, 쉽게말해 선입후출이 적용되는 자료 구조를 말한다. 리스트에 `.append()`를 통해 데이터를 삽입하면, 그 데이터는 리스트의 맨 앞에 추가된다. 반면 `.pop()`을 통해 데이터를 삭제하면, 순서를 지정하는 것이 아니한 경우 리스트의 맨 뒤부터 데이터가 삭제된다. 이러한 스택 구조의 개념을 BOJ 문제 풀이를 통해 응용해보고자 했다. 그리하여 찾은 것이 백준 online judge의 23253번, '자료구조는 정말 최고야'였다. 문제 설명 찬우는 스택을 배운 뒤 자료구조 과목과 사랑에 빠지고 말았다. 자료구조 과목만을 바라보기로 다짐한 찬우는 나머지 과목의 교과서 N권을 방 구석에 M개의 더미로 아무렇게나 ..