티끌모아 태산

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

1. ⭐⭐배열과 연결 리스트의 차이점을 설명해 보세요.더보기배열과 연결 리스트는 데이터를 저장하는 위한 자료구조로, 데이터 저장 방식에 큰 차이점이 있다. 배열은 연속된 메모리 공간에 데이터를 저장한다. 그래서 특정 인덱스의 데이터에 한 번에 접근할 수 있어서 읽는 속도가 빠르다. 하지만 데이터 삭제 또는 삽입 시 요소들의 인덱스를 수정해야 해서 비교적 시간이 오래걸린다.  반면에, 연결 리스트는 노드를 이용해 메모리 공간에 데이터를 불연속적으로 저장한다. 각 노드는 데이터와 다음 노드의 주소 값을 저장하고 있어서 다른 노드에 접근할 수 있다. 배열과 달리 인덱스가 없으므로 한 번에 특정 데이터에 접근 할 수는 없지만, 데이터의 삽입과 삭제 시 노드가 가리키는 주소 값만 변경하면 되어서 속도가 ..

1. 운영 체제란 무엇인가?더보기운영 체제란 컴퓨터 하드웨어 바로 윗단에 설치되는 소프트웨어로써 컴퓨터 사용자를 위한 역할과 하드웨어를 위한 역할로 나눠볼 수 있다. 사용자에게는 컴퓨터를 더 편리하고 효율적으로 사용할 수 있도록 환경을 제공하며 하드웨어에서는 CPU와 메모리, I/O 장치 등 컴퓨터 시스템 내의 자원을 효율적으로 관리하는 역할을 한다. 2. 시분할 시스템이란 무엇인가?더보기CPU의 작업시간을 여러 프로그램이 조금씩 나눠쓰는 시스템을 의미한다. 3. Multi-Programming-System이란 무엇인가?더보기메모리 공간을 분할 해 여러 프로그램들을 동시에 메모리에 올려 놓고 처리하는 시스템이다. 4. 커널이란 무엇인가?더보기커널이란 운영체제의 핵심 ..

1. OSI 7계층이 무엇이고, 왜 나누는지 설명하시오더보기OSI 7계층은 네트워크 통신이 이뤄지는 과정을 7단계로 나눈 네트워크 표준 모델이다. 이렇게 나누는 이유는 통신이 일어나는 과정을 단계별로 알 수 있고, 특정한 곳에 이상이 생기면 그 단계만 수정할 수 있기..

1. 데이터베이스란?더보기컴퓨터 상에서 즉, 전자적으로 저장되고 사용되는 관련있는 데이터들의 조직화된 집합으로 목적에 맞춰 대용량 데이터를 저장하고 관리할 수 있다.. *쿼리란 데이터베이스에 접근해서 원하는데이터를 추출하거나, 수정, 삭제하는 요청을 의미한다. 2. DBMS(database management systems)란?더보기사용자들이 DB를 정의하고, 만들고, 관리할 수 있도록 기능(추가, 수정, 삭제 등)을 제공하는 소프트웨어 시스템이다. 3. 메타 데이터가 무엇인가? 그리고 데이터 모델링은 무엇인가?더보기데이터를 설명하기 위한, 데이터의 정보를 담고 있는 데이터를 의미한다. 그리고 데이터 모델링은 복잡한 현실 세계의 데이터를 단순화 해서 컴퓨터 세계의 데이터베이스로 변환하는 과정이다.  Q...

설명 연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다. 이환이가 만든 공식은 사용하려면 먼저 다음 4가지 변수의 값을 계산해야 한다. L = 연두의 이름과 팀 이름에서 등장하는 L의 개수 O = 연두의 이름과 팀 이름에서 등장하는 O의 개수 V = 연두의 이름과 팀 이름에서 등장하는 V의 개수 E = 연두의 이름과 팀 이름에서 등장하는 E의 개수 그 다음, 위에서 구한 변수를 다음 식에 입력하면 팀 이름의 우승할 확률을 구할 수 있다. ((L+O) × (L+V) × (L+E) × (O+V) × (O+E) × (V+E)) mod 100 연두의 영어 이름과 팀 이름 후보 N개가 ..

Dynamic Programming(동적계획법)이 문제를 풀기 위해서는 '동적 계획법' 개념에 대해서 알고 있어야한다. DP는 큰 문제를 작은 문제로 나누어 푸는 알고리즘 기법이다. DP는 다음의 조건을 만족할 때 사용 가능하다.큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.따라서 동적 계획법은 작은 문제의 결과를 메모리에 저장해 두었다가, 같은 작은 문제가 나타날 때마다 이를 활용하여 문제를 풀 수 있다. 그렇기 때문에 메모리 공간을 효율적으로 사용하여 시간복잡도를 줄일 수 있다. O(N^2) -> O(f(n))으로 다항식 수준으로 개선! 하지만 문제에 따라 다름. 일반적으로는 작은 문제의 정답을 저장해 두고 이를 활용하는 것이기 때문에 작은 문..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 설명 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다. 예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다..

https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 설명 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈..

핵심 아이디어 데이터 범위가 굉장히 크기 때문에 이진 탐색을 생각해 봐야 한다. 문제에서는 '모든 사람이 심사를 받는데 걸리는 시간의 최솟값'을 요구 했으니 '시간'을 기준으로 범위를 잡자. 심사위원의 처리 시간을 고민해 보면, 먼저 가장 짧게 걸릴 수 있는 시간은 얼마일까? 사람이 한명 들어온다 했을 경우, 1분만에 심사를 하는 심사위원이 있는 것이다. 반대로 가장 길게 걸리는 시간은 ''심사위원 중 심사를 가장 느리게 하는 심사 위원에게 모든 사람이 몰리는' 경우이다. -> 처리를 가장 느리게 하는 심사위원의 속도 * n명의 사람들. 이를 통해, 최소 시간과 최대 시간을 확인했다. 해당 값들을 이용해서 이분 탐색을 진행한다. 최솟값과 최댓값을 절반으로 나누고 해당 값이 동일한지, 작은지, 큰지를 판단..