정적배열 - Array

• 연속된 메모리 공간에 위치한 같은 타입의 요소들의 모음
• 한번 정해진 크기는 변경불가
  • 가득찬 공간에 원소 추가하려면 더 큰 배열 생성 후 기존 배열의 원소를 복사한 후 새 원소 추가
• 숫자 인덱스를 기반으로 랜덤 접근이 가능하고 중복을 허용한다.
• vector와 달리 메서드가 없다.

C++ 선언타입

C스타일

1
2
3
4

int a[10]

// 할당
int b[] = {1,2,3}

• 배열의 크기를 정하여 선언 가능
• 크기를 정하지 않고 선언하면서 중괄호 요소들을 할당할 수 있다.

std스타일

1

array<int, 10> a;

동적배열

• 정적 배열의 특징을 가지면서 가변적인 특징이 더해짐
• 참조: O(1)
• 탐색: O(n)
• 맨끝에서 삽입 / 삭제: O(1)
• 맨 끝 제외 삽입 / 삭제: O(n)

ex) 파이썬의 리스트

C++ 선언방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

vector<타입> 변수명;

vector<int> b;

// 크기 미리 정하거나 해당 크기의 어떤 값으로 초기화 가능
#include <bits/stdc++.h>
using namespace std;
vector<int> v(5, 100);
int main(){
	for (int a : v) cout << a << " ";
	cout << "\n";
	return 0;
}
/*
100 100 100 100 100
*/

댓글 공유

제시된 합을 가진 부분 배열 찾기

정렬되지 않은 양의 정수로 이루어진 배열 A가 있다. 연속된 원소를 더한 값이 제시된 값 S와 같은 부분 배열을 찾아라. (인덱스 기준은 1이다.)

• 입력: arr = [1, 2, 3, 7, 5], s = 12, 출력: [2, 4]
  • 인덱스 2부터 4까지의 합: 2 + 3 + 7 = 12
• 입력: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], s = 15, 출력: [1, 5]

방법

1. 이중 반복문 사용

1
2
3
4
5
6
7

def solution(arr,s):
    for i in range(len(arr)):
        sum = s
        for j in range(i,len(arr)):
            sum -= arr[j]
            if (sum == 0):
                return [i+1,j+1]

2-1. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def solution(arr,s):
    sum = s
    index = 0
    position = 0
    while sum != 0:
        if position == len(arr) - 1:
            return [-1]
        sum -= arr[position]
        if sum < 0:
            index += 1
            position = index
            sum = s
            continue
        position += 1
    return [index+1,position]

• sum에 s를 할당하여 position 위치의 요소를 하나씩 빼면서 sum 값이 0 보다 작은지 체크
• 0 보다 작다면 연속되는 부분합이 아니므로 리셋시켜주고 시작 index도 우측으로 이동시킨다.
• 만약 시작 index가 배열의 끝까지 도달했는데도 sum이 0이 되지 않으면 연속되는 부분합을 만들 수 없다.

2-2. O(n) 시간복잡도로 풀기

1
2
3
4
5
6
7
8
9
10

def solution(arr,s):
    left,sum = 0,0
    for right in range(len(arr)):
        sum += arr[right]
        while (left < right and sum > s):
            sum -= arr[left]
            left += 1
        if sum == s:
            return [left+1,right+1]
    return [-1]

• 배열의 첫번째 요소부터 하나씩 sum에 더해준다.
• sum이 s보다 작거나 같으면 계속 배열의 요소를 더해준다.
• sum > s를 만족하면, sum에 left 위치의 요소를 빼주면서 sum이 s보다 작거나 같으면 중단
• 이 때, sum == s를 만족하면 [left+1, right+1]을 반환한다.
• left == right 일 때, sum == s를 만족하지 않으면 연속되는 부분합이 없다.

댓글 공유

0과 1로 구성된 배열 정렬

0과 1로 이루어진 배열이 있다. 배열 자체를 오름차순으로 정렬하라.

• 입력: [1, 0, 1, 1, 1, 1, 1, 0, 0, 0], 출력: [0, 0, 0, 0, 1, 1, 1, 1, 1, 1]
• 입력: [1, 1], 출력: [1, 1]

방법

1. sort() 사용

1
2
3
4
5

arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    arr.sort()
    return arr

• sort() 메서드는 원본 배열을 오름차순으로 변경한다.

2. sorted() 사용

1
2
3
4
5

arr = [1, 0, 1, 1, 1, 1, 1, 0, 0, 0]

def get_increased_arr(arr):
    answer = sorted(arr)
    return answer

3. count() 사용

1
2
3

def get_increased_arr(arr):
    arr[:] = [0] * arr.count(0) + [1] * arr.count(1)
    return arr

• arr[:]을 사용하여 원본에 영향을 미치지 않고 복사할 수 있다.

4. 포인터 2개 사용

1
2
3
4
5
6
7
8
9
10
11
12
13

def get_increased_arr(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        while arr[left] == 0:
            left += 1
        while arr[right] == 1 and right >= 0:
            right -= 1
        if left < right:
            arr[left], arr[right] = 0, 1
            left, right = left + 1, right + 1
    return arr

댓글 공유

회문(Palindrome) 찾기

주어진 문자열이 회문이면 True, 아니면 False를 반환하라.

• 입력: madam, 출력: True
• 입력: tomato, 출력: False

방법

1. reversed(), join(), 리스트 컴프리헨션 사용

1
2
3
4

def isPelindrome(str):
    reverse_str = "".join(list(reversed([x for x in str])))

    return str == reverse_str

2. 슬라이싱 사용

1
2
3
4
5
6

word = 'racecar'

if word == word[::-1]:
    print(True)
else:
    print(False)

• 슬라이싱은 [startIndex:endIndex:interval]로 사용하는데, startIndex, endIndex 없이 interval만 사용하여 역순을 표현했다.

3. 포인터 2개 사용

1
2
3
4
5
6
7
8

def is_palindrome(word):
    left,right = 0, len(word) - 1

    while left < right:
        if (word[left] != word[right]):
            return False
        left, right = left + 1, right - 1
    return True

댓글 공유