노래부르다

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제분석 N개의 배열 중, 어떤 숫자를 n이라 할 때, 다른 수 '두' 개의 합으로 나타낼 수 있는 '좋은' 수의 개수를 찾는 문제이다. 문제를 보면 두 수의 합이 n과 같은 경우의 수만 찾으면 된다고 생각하지만... 중요한 포인트는 2개이다. 1. 배열의 원소는 중복될 수 있다. 그리고 수의 위치가 다르면 값이 같아도 다른 수이다. 2. '두' 개의 합으로 목표의 숫자를 만들어야 한다. 1. 배열의 원소 중복 예를 들어서, [1 2 3 3 3 4 5]의 배열이 있다고 가정하자. 첫번째 3..

1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 분석 N개의 갑옷 재료 중, 두개의 조합으로 M을 만드는 문제이다. 투 포인터를 사용하여, 원소 두 개의 조합이 목표로 하는 숫자가 되는가를 확인하면 되는 문제이다. 문제 풀이를 총 2가지를 가져왔다. 투포인터를 이용한 풀이와 그렇지 않은 풀이이다. 투 포인터에 대해 알고싶다면 아래 링크로 공부해보자. [Algorithm] 투 포인터(two pointer) 완.전.정.복 투 포인터(two pointer)란? - 투 포인터란, 배열에..

2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 분석 N이라는 숫자를 '연속'된 자연수의 합으로 표현하고, 이 조합의 개수를 구하는 문제이다. 주목해야 할 점은 3가지라고 생각한다. 1, 연속된 자연수. 2. 메모리의 크기.(32MB) 3. N의 크기 1. 연속된 자연수 - 자연수가 1개 혹은 여러 개가 되어도 연속된 자연수라면 조합에 포함이 된다. 즉, N이라는 숫자의 연속된 자연수는 최소 1개 이상이 될 것이다. 이 외의 연속된 자연수를 찾기 위해서는, 구간 합의 개념을 이용하면..

구간 합이란?연속된 숫자들의 배열에서, 원하는 구간까지의 합을 알고자 할 때 이용하는 알고리즘.ex) 1 ~ 10이 배열에 저장되어있다고 할 때, 합 배열은 1 3 6 10 ..과 같은 방식합 배열에서의 1 = 1 / 3 = 1+2 / 6 = 1+2+3 / 10 = 1+2+3+4 if) 난 3 ~ 6의 합에 대해 알고 싶은데 어떻게 해야하나요?answer) 1 ~ 6의 합에서 1 ~ 2의 합을 뺀다면, 원하는 답을 얻울 수 있어요! 공식합 배열 S의 정의S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합) 합 배열 S를 만드는 공식S[i] = S[i-1] + A[i] (더하고자 하는 A[i]를, 이전까지의 합S[i-1]의 합) 구간 합을 ..

배열- 인덱스를 사용하여 원소에 바로 접근 가능하다- 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 삭제하려면 주변 인덱스 값을 옮겨야 한다.- 배열의 크기는 선언할떄 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 있다.- 구조가 간단하다. (코테 사용) 리스트- 인덱스가 없어서 값에 접근하려면, head 포인터부터 순서대로 접근. 값에 접근 속도가 느리다.- 포인터로 연결되어 있기에, 데이터 삽입이나 삭제하는 연산속다가 빠르다.- 선언할 때, 크기 지정이 필요 없다. 크기가 유동적인 데이터를 다룰 때 적절하다.- 포인터를 저장할 공간이 필요해 구조가 복잡하다.