개발자 아지트

5-1. 배열 개념

배열은 인덱스와 값을 1대 1 대응하여 관리하는 자료구조이다. 

배열은 인덱스를 통해 어떤 위치에 있는 값이든 한 번에 접근할 수 있다. 

이런 방식을 임의 접근(random access)라고 한다. 

파이썬에서 배열 선언하는 방법

arr = [0, 0, 0]
arr = [0] * 3

리스트 생성자를 사용하는 방법

arr = list(range(3)) #[0, 1, 2]

리스트 컴프리헨션을 활용하는 방법

arr = [0 for _ in range(3)] # [0, 0, 0]

파이썬에서는 배열을 지원하는 문법은 따로 없고, 대신 리스트라는 문법을 지원한다. 

(사실 엄밀히 말하자면 배열과 리스트는 다른 개념임)

파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현됐다. 

파이썬의 리스트는 다른 언어의 배열 기능을 그대로 사용하면서 배열의 크기는 가변적으로 사용할 수 있다. 

배열과 차원

배열은 2차원, 3차원, ..., 다차원 배열 까지 사용할 수 있다. 

그러나 컴퓨터의 메모리 구조는 1차원이다. 

이는 2차원, 3차원, ..., 다차원 배열도 실제로는 1차원 공간에 저장된다는 뜻이다. 

배열은 몇 차원이든 상관없이 메모리에는 연속적으로 할당된다. 

1차원 배열

배열의 각 데이터는 메모리의 낮은 주소에서 높은 주소 방향으로 연속적으로 할당된다. 

2차원 배열

2차원 배열은 1차원 배열을 확장한 것이다. 

2차원 배열 활용 예시 

# 2차원 배열을 리스트로 표현
arr = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]

# arr[2][3]에 저장된 값 출력
print(arr[2][3]) # 12

# arr[2][3]에 저장된 값을 15로 변경
print[2][3] = 15

리스트 컴프리헨션을 통한 2차원 배열 활용 예시 

# 크기가 3 * 4인 리스트를 선언하는 예시 
arr = [[i]*4 for i in range(3)] # [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

arr = [[1, 2, 3], [4, 5, 6]]

위의 배열에서  첫번째 행과 두번째 행의 메모리 주소는 연속된다. (1행의 인덱스 2 다음 바로 2행의 인덱스0의 주소가 이어진다. )

5-2. 배열의 효율성

배열 연산의 시간복잡도를 통해 배열의 효율성은 아래와 같다. 

배열 연산의 시간 복잡도

아까 배열은 인덱스를 통해 임의 접근 방법을 사용한다고 했다. 따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

만약 배열에 데이터를 추가하거나 삭제해야 한다면? 추가후에 기존에 있던 것들을 처리할 필요가 있는지,  혹은 대상을 삭제하고 기존에 있는 것들을 처리할 필요가 있는지 확인이 필요하다. 

1. 맨 뒤에 삽입할 경우

• 임의 접근을 통해 맨뒷 자리를 찾을 수 있다. 
• 맨 뒤에 값을 추가한 후에 기존의 값들을 이동할 필요가 없다. 
• 즉, 시간 복잡도는 O(1)이다. 

2. 맨 앞에 삽입할 경우

• 임의 접근을 통해 맨 앞 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 현재 갖고 있는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

3. 중간에 삽입할 경우

• 임의 접근을 통해 중간에 삽입할 자리를 찾을 수 있다. 
• 기존 데이터 들을 뒤로 한칸씩 밀어야 데이터의 소실 없이 맨 앞에 값을 삽입할 수 있다. (== 뒤로 밀어야 야 하는 데이터의 개수가 N개라면,  O(N))
• 즉, 시간 복잡도는 O(N)이다. 

위의 경우 들을 봤을때, 배열로 데이터를 저장하기 전에는 항상 이런 비용을 생각하는 것이 바람직하다. 

이렇듯 배열을 선택할 때 고려할 점은 다음과 같다. 

배열을 선택할 때 고려할 점

1. 할당할 수 있는 메모리 크기를 확인해야 한다. (파이썬에서는 리스트를 사용하므로, 배열 크기에 대한 고민은 할 필요가 없다. 공부를 위해 읽어두기)

• 운영체제마다 배열을 할당할 수 있는 메모리의 값은 다르지만, 보통 정수형 1차원 배열은 1천 만개, 2차원 배열은 3천*3천 크기를 최대로 생각한다. 따라서 이 이상의 값의 데이터를 관리하고자 하면 런타임에서 배열 할당에 실패할 수 있다. 

2. 중간에 데이터 삽입이 많은지 확인해야 한다. 

• 배열은 선형 자료구조이기 때문에, 중간이나 맨 처음의 위치에 데이터를 자주 삽입하면 시간복잡도가 높아져, 시간초과가 발생할 수 있다. 

5-3. 코딩테스트에서 자주 활용하는 리스트 기법

리스트에 데이터를 추가하는방법 

1. append()

# 리스트의 맨 끝에 데이터 추가
tmp_list = [1, 2, 3]
tmp_list.append(4) # [1, 2, 3, 4]

2. + 연산자

tmp_list = [1, 2, 3]
tmp_list = tmp_list + [4, 5] # [1, 2, 3, 4, 5]

3. insert()

# 특정 위치에 데이터를 삽입할 수 있다. 
tmp_list = [1, 2, 3]
tmp_list.insert(2, 9) #[1, 2, 9, 3]

리스트에서 데이터를 삭제하는 방법

1. pop() 

# 특정 위치에 데이터를 삭제할 수 있다. 
# 삭제한 데이터의 값을 반환한다. 
tmp_list = [1, 2, 3]
pop = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2]

2. remove()

# 특정 데이터를 찾아 삭제할 수 있다. 
# 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제한다. 
tmp_list = [1, 2, 3]
tmp_list.remove(2) # [1, 3]

리스트 컴프리헨션으로 데이터에 특정 연산 적용하기

리스트 컴프리헨션은 기존 리스트를 기반으로 새 리스트를 만들거나, 반복문이나 조건문을 통해 복잡한 리스트를 생성하는 등 다양한 상황에서 사용할 수 있는 문법이다. 

리스트에 제곱 연산 적용 예시 

tmp_list = [1, 2, 3]
squares = [num**2 for num in tmp_list] #[1, 4, 9]
# tmp_list의 값은 여전히 [1, 2, 3] 이다.

리스트 컴프리헨션은 연산이 끝난 리스트를 반환할 뿐, 연산 대상 리스트를 바꾸지 않는다. 

유용하게 쓰이는 리스트 연관 메서드 

alphabet = ["a", "b", "c", "a"]

# 리스트의 전체 데이터 개수 반환 함수 len()
len(alphabet) # 4

# 특정 데이터가 처음 등장할 적의 인덱스를 반환하는 index()메서드, 만약 값이 없는경우 -1 반환
alphabet.index("a") # 0

# 사용자가 정한 기준에 따라 데이터를 정렬하는 sort()메서드
# 함수안에 인수가 없을 경우, 오름차순으로 데이터 정렬
alphabet.sort() # ["a", "a", "b", "c"]
# 역순 
alphabet.sort(reverse=True) # ["c", "b", "a", "a"]

# 특정 데이터 개수를 반환하는 count() 메서드
alphabet.count("a") # 2

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

https://www.acmicpc.net/problem/1926

문제 해결 방법

그림 정보가 적힌 좌표를 순회한다. 대신 방문여부를 알 수 있는 visited 배열이 필요하다. 

좌표를 순회할때 1을 만나고, 방문한 적이 없으면 bfs함수를 실행한다. 

이때, deque를 활용해 큐를 만들고 큐에 bfs함수를 실행할 당시의 좌표값을 넣어준다. 

bfs함수에서는 큐에서 값을 꺼내어 방문처리를 해주고, 자신의 자리에서 그림이 이어져 있다는 판단 기준인 위, 아래, 양옆을 조회 한다. 

이때, 새로 조회하는 위치가 그림 정보가 적힌 좌표의 범위를 벗어나서도 안되고, 이미 방문 한 적이 있어도 안된다. 또한 0이여도 안된다. 

값이 0이 아니고 방문한 적이 없으면 현재자리의 값에서+1을 해준다.  큐에 해당 좌표와 얼마나 끊기지 않고 값을 조회하고있는지에 대한 값 현재 자리의 값+1을 넣어준다. 

순회를 하면서 더이상 큐에 값을 이어 넣을 수 없으면(그림이 끊기면), 얼마나 끊기지 않고 값을 조회했는지에 대한 값을 임의의 리스트에 넣어준다. 

그림 정보 순회가 모두 끝나면 임의의 리스트의 원소의 개수와 원소의 최대값을 출력한다. 

코드 구현

정답 코드 

import sys
input=sys.stdin.readline
n, m = map(int, input().split())
from collections import deque

if n==0 and m==0:
    print(0)
    print(0)
    exit(0)

dy=[1, -1, 0, 0]
dx=[0, 0, 1, -1]

tmp=[]
for i in range(n):
    tmp2=list(map(int, input().split()))
    tmp.append(tmp2)

# 그냥 카운트만 하는애 cnt
# 방문 확인용 visited
cnt = 0
visited = [([False] * m) for _ in range(n)]
bigN = 0
def bfs(cnt, dequeA, visited):
    bigN=1
    while dequeA:
        yy, xx, _ = dequeA.popleft()
        visited[yy][xx] = True
        for i in range(4): 
            nx=xx+dx[i]
            ny=yy+dy[i]

            if ny<0 or nx<0 or ny>=n or nx>=m:
                continue
            if visited[ny][nx]==True or tmp[ny][nx]==0:
                continue
            if tmp[ny][nx]>=1 and visited[ny][nx]==False:
                tmp[ny][nx] = bigN+1
                bigN=bigN+1
                visited[ny][nx]=True
                dequeA.append([ny,nx, bigN])
    return cnt, bigN

tmp3=[]
check = 0
dequeA = deque()
for i in range(n):
    for j in range(m):
        if tmp[i][j] == 1 and visited[i][j] == False:
            dequeA.append([i,j, 1])
            cnt+=1
            cnt, bigN = bfs(cnt, dequeA, visited)
            tmp3.append(bigN)
            check =1

print(cnt)

if n == 0 and m ==0 or check ==0:
    print(0)
else:
    print(max(tmp3))

시간/공간 복잡도

따로 생각하지 않았다. 

최적화 및 개선

• 따로 하지않음

어려웠던 점

• BFS 문제를 효율적으로 푸는 방법이 가물가물해서 문제 풀기 어려웠다. 

알게된 것

함수 객체 할당과 함수 호출 구문을 구분하지 못해서 생긴 일 

여러줄을 받을 때 속도 감소를 위해 input()함수 말고 sys 에서 제공하는 readline()함수를 사용하려는 상황이다. 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline()

tmp=[]
for i in range(n):
    
    # tmp2=list(input.split())
    tmp2=input.split()
    print('tmp2', tmp2)
    tmp.append(tmp2)

print(tmp)

문제가 있는 코드: 이코드에서는 2번째줄 3번째줄만 입력을 받는게 된다. 

• 괄호를 붙이지 않은 경우 (input = sys.stdin.readline):
  • 이 경우 sys.stdin.readline 함수 객체를 input이라는 변수에 직접 할당하는 것이다. 이 상태에서는 input은 함수 객체 자체를 참조하게 된다.
• 괄호를 붙인 경우 (input()):
  • 괄호를 붙이면 함수가 실제로 호출된다. 함수 호출은 해당 함수가 수행하는 작업을 실행하고, 그 결과를 반환한다. 

import sys

n, m = map(int, input().split())

input=sys.stdin.readline

tmp=[]
for i in range(n):
    
    tmp2=input().split()
    tmp.append(tmp2)

print(tmp)

문제 인지후 바꾼 코드 

파이썬에서는 기본적으로 제공하는 데이터 타입들이 있다.

집을 사면 딸려오는 가구(사실 그 딸려오는 가구 값도 포함되는건 맞지만)처럼 파이썬에서는 기본 데이터 타입과,

컬렉션 데이터 타입을 제공한다. 

04-1 빌트인 데이터 타입

기본 데이터 타입

기본 데이터 타입에는 정수형, 부동소수형, 문자열 타입이 있다.

정수형

: 양, 음의 정수와 0을 포함한다.

사칙연산 뿐만 아니라 그 외의 연산도 가능하다. 

예를들어, **을 통한 지수 연산, //을 통한 나눗셈에서 몫만 반환하는 연산 등

아래는 정수형 데이터 정의 및 활용 방법이다. 

# 정수형 변수 선언

a = 4
b = 3

# 정수형 산술 연산

print(a + b) # 더하기 1
print(a - b) # 빼기 12
print(a * b) # 곱하기 45
print(a / b) # 나누기(소수점 포함) 1.3...
print(a // b) # 나누기(소수점 제외) 1
print(a % b) # 모듈러 연산(나머지 값 출력) 1
print(-a) # 부호 바꿈 -4
print(abs(-a)) # 절대값 4
print(a**b) # a의 b승 64

# 정수형 비교 연산

print(a == b) # 같은 값인지 비교 False
print(a != b) # 같은 값이 아닌지 비교 True
print(a > b)  # 왼쪽값이 더 큰지 비교 True
print(a < b)  # 오른쪽 값이 더 큰지 비교 False
print(a >= b) # 왼쪽값이 더 크거나 같은지 비교 True
print(a <= b) # 오른쪽값이 더 크거나 같은지 비교 False

# 정수형 비트 연산

a = 13
b = 4

print(a & b) # AND 4
print(a | b) # OR 13
print(a ^ b) # XOR 9
print(~a) # NOT -14
print(a << 2) # 왼쪽 시프트 (a에 2^2를 곱한 것과 동일) 52
print(a >> 1) # 오른쪽 시프트 (a에 2^1로 나눈 것과 동일) 6 

#정수형 논리 연산

print(a and b) # 논리 연산 AND 4
print(a or b) # 논리 연산 OR 13
print(not a) # 논리 연산 NOT / False

*~a가 14인 이유

a는 2진수로 표현하면 0000 1101 이다. ~(not)을 하면 0000 1101이 반전돼서 1111 0010이 된다. 

맨 왼쪽의 값이 0이면 양수, 1이면 음수를 나타내는 것이다. 

1111 0010은 음수의 값이고, 컴퓨터에서 음수는 2의 보수로 표현된다. 

2의 보수를 읽기 위해서는 값을 한번 반전해주고 => 0000 1101 

그대로 1을 더해준다. => 0000 1110 이는 10진수로 14이다.

하지만 이 값은 음수이므로 -14로 표현할 수 있는 것이다. 

*논리 연산 AND 연산자

파이썬에서 논리 연산 AND는 두 피연산자가 모두 참이면 마지막 값을 반환한다. 

만약 첫 번째 피연산자가 거짓이거나 NULL이면, 첫 번째 피연산자를 반환한다. 

부동소수형

부동소수형에서는 사칙 연산, 정수형 나누기, 모듈러, 제곱 연산, 논리 연산을 할 수 있다. 

부동소수형에서 눈여겨 봐야할 곳은 10 % 3.2의 값이 0.4가 나와야 하지만 파이썬에서는 

0.39999999999999947이 나온다. 

그 이유는 파이썬에서는 부동소수형 데이터를 이진법으로 표현하기 때문에 발생하는 거고, 표현 과정에서 오차가 발생한다.

이를 엡실론이라고 한다. 

따라서 부동소수형 데이터를 활용한 문제에서는 오차 허용 범위의 언급을 확인하고, 주의 해야한다. 

04-2 컬렉션 데이터 타입

컬렉션 데이터 타입은 여러 값을 담는 데이터 타입을 말한다. 그 유형으로 리스트, 튜플, 딕셔너리, 셋, 문자열 등이 있다.

또한 컬렉션 데이터 타입은 두가지로 나눌 수 있는데, 이는 데이터의 수정 가능 여부에 따라 변경할 수 있는 객체(mutable object)와 변경할 수 없는 객체(immutable object)로 나눌 수 있다. 

변경할 수 있는 객체(mutable object)

: 객체 생성 후 객체를 수정할 수 있다. 리스트, 딕셔너리, 셋이 이 유형에 해당한다. 

변경할 수 없는 객체(immutable object)

: 객체 생성 후 객체를 수정할 수 없다. 문자열, 튜플이 이 유형에 해당한다. 

(정수나 부동소수점은 컬렉션 데이터 타입은 아니지만 이뮤터블 객체에 속한다)

<리스트>

: 리스트는 뮤터블 객체이고, 순서가 있는 자료형이다. 리스트는 인덱스를 활용해 특정 위치의 원소에 접근할 수 있다. 

기본적인 리스트 사용법은 다음과 같다. 

# 리스트 선언
tmp_list = [1, 2, 3, 4]
tmp_list2 = [5, 6] + [7, 8, 9]
tmp_list3 = list(tmp_list)
print(tmp_list) # [1, 2, 3, 4]
print(tmp_list2) # [5, 6, 7, 8, 9]
print(tmp_list3) # [1, 2, 3, 4]

# 리스트 인덱싱
tmp_list.append(5)
print(tmp_list) # [1, 2, 3, 4, 5]

# 인덱싱으로 값 삭제
del tmp_list[0]
print(tmp_list) # [2, 3, 4, 5]

리스트의 활용방법 중에 리스트 슬라이싱이라고 있다. 

슬라이싱은 시퀀스 자료형의 범위를 지정해 값을 복사하여 가져오는 방식을 말한다. 

리스트 슬라이싱 활용법은 다음과 같다. 

print(tmp_list[0:2]) # [2, 3]
print(tmp_list[1:]) # [3, 4, 5]
print(tmp_list[2:3]) # [4]
print(tmp_list[-2:-1]) # [4]

<딕셔너리>

: 딕셔너리는 뮤터블 객체이고, 키와 값 쌍을 저장하는 해시테이블로 구현돼 있다. 

키를 사용하여 값을 검색하는 자료형이다. 

기본적인 딕셔너리 사용법은 다음과 같다. 

# 딕셔너리 초기화 
dic = { }

# 딕셔너리 삽입과 출력
dic["yellow"] = 1
dic["green"] = 3
dic["blue"] = 5

print(dic) #{'yellow': 1, 'green': 3, 'blue': 5}

딕셔너리 검색 활용법은 다음과 같다.

키에 해당하는 문자열인지 확인하고, 키의 값이 딕셔너리에 존재하면 키-값을 출력한다. 

key = "yellow"
if key in dic:
    value = dic[key]
    print(f"{key}: {value}")
else:
    print(f"{key}는 딕셔너리에 존재하지 않습니다. ")

딕셔너리 수정 방법은 다음과 같다. 

dic["green"] = 5
print(dic) #{'yellow': 1, 'green': 5, 'blue': 5}

딕셔너리 삭제 방법은 다음과 같다.

del dic["green"]
print(dic) #{'yellow': 1, 'blue': 5}

<튜플>

: 튜플은 이뮤터블 객체이다. 한 번 생성하면 삽입하거나 삭제할 수 없다. 

기본적인 튜플 사용법은 다음과 같다. 

# 튜플 초기화 
tup = (1, 2, 3)

튜플은 인덱싱과 슬라이싱을 활용할 수 있고, 리스트와 활용법이 같다.

<문자열>

: 문자열은 문자의 집합 형태이며, 이뮤터블 객체이다. 

기본적인 문자열 사용법은 다음과 같다.

# 문자열 초기화 

string = "Hi" # 큰 따옴표 사용
string2 = 'Hello'# 작은 따옴표 사용

# 문자열 추가, 삭제 
string3 = "A-"
string3 += "yo" # 이때, string3은 기존의 문자열의 메모리 주소와의 연결은 끊고, 문자열을 새로 만들고 해당 문자열이 담길 메모리 주소를 새로 할당한다. 
print(string3) # "A-yo"

# 문자열 수정 
string4 = "Ha"
string4 = string4.replace("a", "o")
print(string4) # "Ho"

04-3 함수

파이썬에서의 함수 사용법은 다음과 같다.

def add(num1, num2):
    result = num1 + num2
    return result 

# 함수 호출

ret = add(5, 10)
print(ret)

함수를 더 간단하게 사용하기 위한 방법으로 파이썬에서는 람다식을 사용할 수 있다. 

또한 람다식은 익명 함수를 만드는데 사용한다. 

익명 함수는 이름 없는 함수이고, 코드에서 일시적으로 실행할 목적으로 사용하거나, 다른 함수의 인수로 사용할 수 있다. 

람다식의 사용법은 다음과 같다. 

# 람다식 정의

lambda x, y : x + y # x와 y를 받아서 더한 값을 반환하는 람다식

# 람다식 사용 유형 1

add = lambda x, y: x + y
print(add(5, 4)) # 9

# 람다식 사용 유형 2

num = [1, 2, 3, 4, 5]
squares = list(map(lambda x: x**2, num))
print(squares) # [1, 4, 9, 16, 25]

04-4 코딩 테스트 코드 구현 노하우

1. 조기 반환

: 코드 실행 과정이 끝나기 전에 반환하는 기법

2. 보호 구문

: 본격적인 로직 진행 전 예외 처리 코드를 추가하는 기법 

3. 합성 함수

: 2개 이상의 함수를 활용해 함수를 추가로 만드는 기법

보통 합성 함수로 람다식을 활용한다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

코딩테스트 준비를 하기 위해서 연습 문제를 풀때, 제한 시간을 한번쯤 볼 수 있었을 것이다. 

여기서 말하는 제한 시간은 알고리즘이 실행되고 종료될 때 걸리는 시간의 제한 시간을 말하는 것이다. 

컴퓨터에서 1초당 처리되는 연산 횟수가 대략적으로 정해져있다.

(코딩테스트를 치는 환경(연습으로 문제푸는 환경도 마찬가지)에는 모든 컴퓨터의 성능이 동일하다고 가정한다. )

(1초당 1억개의 연산 가능)

그런데 문제에 대해 알고리즘을 어떻게 짜냐에 따라서 1초당 처리되는 연산 횟수가 줄어들 수도 있고 유지될 수도 있다. 

더 많아질 수는 없다. (컴퓨터가 자가 발전하지 않는 이상(?))

코드를 작성하고 나서 이 알고리즘이 어떻게 짜여졌냐? 어떻게 짜여졌길래 1초당 처리되는 연산 횟수가 이런가?

작성한 알고리즘이 1초당 처리되는 연산 횟수가 이정도면 대략 이정도의 복잡도를 가진 알고리즘일 것이다. 

(단, 입력 크기를 N으로 일반화 해야함. 왜냐하면 입력 크기가 1인 경우 알고리즘을 작성해야 하는 경우로 예를 들자면, 입력크기가 1일때만  연산 횟수가 1인 성능을 가지는 것이기 때문 == 해당 상황에 한정된것, 입력 크기가 다른 값으로 바뀔경우 연산 횟수 성능도 바뀔 것)

이런 맥락에서의 복잡도를 가지고,

==> 우리는 이것을 알고리즘의 시간복잡도라고 하기로 했다. 

입력 크기에 따른 연산 횟수 추이를 활용해 시간 복잡도를 표현하는 방법을 점근적 표기법이라 한다. 

[시간 복잡도(time complexity)]

: 알고리즘의 성능을 나타내는 지표. 입력 크기(알고리즘이 처리해야 할 데이터의 양)에 대한 연산 횟수의 상한을 의미한다. 

시간 복잡도는 낮으면 낮을 수록 좋다. 

시간 복잡도는 최선, 보통, 최악의 경우로 나눌 수 있지만, 코딩테스트에서는 작성한 알고리즘의 최악의 경우를 고려하여 시간 복잡도를 계산해야한다. 왜냐하면, 모든 경우의 수에서 알고리즘이 문제를 처리하는 것을 고려해야 하기 때문이다. 

* 빅오 표기법

: 빅오 표기법은 최악의 경우일 때의 시간 복잡도를 표현하는 방법이다. 

빅오 표기법은 특정 알고리즘의 연산 횟수가 f(x)일 때, 함수의 최고차항만을 남기고 남은 자수를 지워 O(최고차항)와 같이 표현하면 된다. 

* 빅오 표기법을 쉽게 쓸 때 최고차항만 남기고 차수를 지우는 이유

: 시간복잡도 식에서 최고차항 이외의 값들을 2차원 그래프에서 표현해보면 최고차항 이외의 값들은 무시할 수 있을 정도로 작으므로 무시한다. 

컴퓨터는 1초에 최대 1억번 연산할 수 있다. 

코딩 테스트의 문제는 출제자의 의도대로 로직을 구현했을 경우 대부분 코드를 정답처리 할 수 있게끔 채점시간을 정한다. 

이때, 언어별로 다른 성능의 차이는 고려하지 않는다. 

[시간 복잡도 계산해보기]

: 과정

1. 문제 정의

2. 연산 횟수 측정

3. 시간 복잡도 분석

* 고려할 점

출력 자체도 연산이다. 

비교도 연산이다. 

* 정리된 개념 출처: 코딩 테스트 합격자 되기 - 박경록(파이썬 편)

LCS란?

:"가장 긴 공통 부분 수열"이다. 알고리즘 LCS에서는 가장 긴 공통 부분 문자열이다. 두 개의 문자열이 있을 때, 그 문자열에서 순서를 유지하면서 공통으로 나타나는 글자들을 이어서 만들 수 있는 가장 긴 문자열을 찾는 것을 의미한다.

*부분 문자열이란?

:부분 문자열에는 연속된 부분 문자열인 Substring과 연속되지 않은 부분 문자열인 Subsequence라는 개념이 있다. 

Subsequence라는 개념을 예시를 들어 설명하자면, "ABCDEF"와 "AEBDF"라는 두 문자열이 있다면, 이 두 문자열에서 공통으로 나타나며 글자들이 두 문자열에서 같은 순서로 나타나는 문자열 중 가장 긴 부분 수열은  "ABDF"이다. 

예시

* 위 배열 활용법 *

조회하는 문자열이 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야한다. 

조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값을 교체한다. 

맨 첫번째 행의 모든 열을 0으로 하고 다음 모든 행의 첫번째 열에 0은 왜 넣는걸까?

=> 조회하는 문자열이 같을때, 서로 같은 문자열임이 확인되면 현재 자리에서 대각선(왼쪽 위)의 값 +1을 해야하는데, 

앞에 0을 넣지 않으면 첫번째 문자열의 맨첫번째 값과 두번째 문자열의 맨 첫번째 값에 어떤 값을 넣어줘야 할지 모르기 때문이다. 

왜 바로 앞의값(왼쪽)의 값에서 +1을 하지 않을까? 

=> 바로 앞의값에서 +1을 하면 lcs의 값에 +1을 하는 꼴이 된다.

(하지만 두번째 단어의 조회할 자리는 여전히 같은 자리임=> 두번째 단어의 조회할 자리를 +1 하면 할수록 lcs의 값이 중복으로 +1되는 꼴)

왜 조회하는 문자열이 서로 다른 문자열임이 확인되면 현재 자리에서 왼쪽, 위의 값 중 큰 값으로 현재의 값으로 교체할까? 

왜 하필 현재 자리에서 왼쪽, 위의 값을 비교할까? 

 => 현재 자리의 왼쪽은 현재 자리의(같은행, 다른열==현재열-1) lcs값은 고려하지 않고 이전 문자까지의 lcs값만을 가지고 있는 것이고,

현재 자리의 위쪽은 현재 자리의 lcs값을 고려하지만, 새로 조회하는 문자와의 비교는 하지 않은 값이다. (다른행==현재행-1, 같은열)

왼쪽, 위의 값은 각각 자신이 할 수 있는 최적의 lcs를 구한 상태이다.

따라서 둘 중에 큰 값을 골라 현재의 자리의 값을 교체해줌으로써 최적의 값을 유지할 수 있게된다. 

https://www.acmicpc.net/problem/9252

문제 해결 방법

1. dp배열을 만들어서 lcs를 구함

2. lcs를 구한 dp배열을 역추적하여 문자열을 구함 

코드 구현

정답 코드 

s1 = input()
s2 = input()

m=len(s1)
n=len(s2)

dp = [[0] * (n+1) for _ in range(m+1)]

for i in range(1, m+1):
    for j in range(1, n+1):
        if s1[i-1]==s2[j-1]:
            dp[i][j]=dp[i-1][j-1]+1
        else:
            dp[i][j]=max(dp[i][j-1], dp[i-1][j])

result =''
startm = m
startn = n

print(max(dp[-1]))
if max(dp[-1])!=0:
    while 1:
            if dp[startm][startn]==0:
                break
            # 위에것이 더 큰지
            if dp[startm][startn] == dp[startm-1][startn]:
                startm-=1
            # 왼쪽 것이 더 큰지
            elif dp[startm][startn] == dp[startm][startn-1]:
                startn-=1
            # 둘다 안크면 대각선 이동 
            # 값도 넣어줌 
            elif ((dp[startm][startn]-1) == dp[startm-1][startn-1]):
                
                startm-=1
                startn-=1

                result+=s2[startn]


            
            

    print(result[::-1])

시간/공간 복잡도

0.1초로 시간제한이 있었는데, 해당 시간에 1000만 번의 연산을 해야하는거고, 최대로 입력할 수 있는 문자열의 길이가 1000이기 때문에 

O(n)으로 푸는것이 맞다. 

최적화 및 개선

따로 하지 않음 

어려웠던 점

lcs의 개념, lcs의 역추적의 개념을 잘 몰라서 접근하기 어려웠다. 

역추적 부분은 아직도 어렵게 느껴진다. 비슷한 문제를 여러번 풀어봐야 할 것 같다. 

https://www.acmicpc.net/problem/17829

문제 해결 방법

1. 맵은 행과 열이 항상 2의 배수일 수 밖에 없다는 것을 인지한다. 

2. 따라서 0행0열 0행 2열 0행 4열... 2행 0열 2행 2열.... 이렇게 맵의 크기만큼 조회한다. 

2-1. 출발지 기준 이때 오른쪽으로 한칸, 아래로 한칸, 아래 오른쪽으로 한칸 을 리스트에 넣는다. 

2-2. 리스트에서 두번재로 큰 수만 모아서 또다른 리스트를 만든다. 

2번을 맵의 원소가 1개 남을때 까지 반복하다보면 결과 값이 나온다. 

코드 구현

정답 코드 

import sys

n = int(input())
block=[]
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().strip().split()))
    block.append(tmp)

while 1:
    if len(block[0])==1:
        print(block[0][0])
        break

    makeBlock = [item[:] for item in block]

    block = []
    for i in range(0, len(makeBlock),2):
        tmp=[]
        for j in range(0, len(makeBlock[0]),2):
            realT=[makeBlock[i][j], makeBlock[i][j+1], makeBlock[i+1][j], makeBlock[i+1][j+1]]
            realT.sort(reverse=True)
            tmp.append(realT[1])

        block.append(tmp)

시간/공간 복잡도

해당 문제는 구현문제이기 때문에 시간/공간 복잡도를 따지지 않는다. 

최적화 및 개선

따로 하지 않음

어려웠던 점

쉬운 구문을 까먹어서 검색해서 찾아봤다 아예 그 구문은 외워야겠다. 

리스트 복사하는 구문과 sort함수 사용법.

https://www.acmicpc.net/problem/2504

문제 해결 방법

1. 괄호가 정상적인지 확인한다. 

2. 스택을 만들고, 괄호열의 값을 계산하기 위한 변수를 선언한다. (변수의 초깃값은 1)

3. 여는 괄호일 경우, 변수에  괄호의 종류에 따라 2혹은 3을 곱한다. 

4. 닫는 괄호가 나올경우, 그 이후 또다른 여는 괄호가 나올 때까지 닫는 괄호가 나올 수 있다.
(여는 괄호가 나오지 않는다면 결국 모든 괄호열의 순회를 완료하게 됨)

단, 괄호를 연만큼 닫는 괄호가 나오지만, 괄호가 닫히지 않은 경우는 계속 나머지 값들에 영향을 줘야만 한다. 

따라서, 괄호가 닫히는 경우 나머지 값들에 영향을 주지 않기 위해 괄호의 종류에 따라 2 혹은 3으로 나눈다. 

5. 3-4를 괄호열 순회를 마칠 때 까지 수행한다. 

6. 결과값을 출력한다. 

코드 구현

정답 코드 

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        checkingStack = []
        result=0
        tmpV=1
        for index, j in enumerate(s):
            if j=='(':
                tmpV*=2
                check =1
                checkingStack.append('(')
            elif j=='[':
                tmpV*=3
                check =1
                checkingStack.append('[')

            elif j==')':
                if check ==1: # 최초로 닫는괄호 
                    result+=tmpV
                    tmpV=tmpV//2
                    check=0
                    checkingStack.pop()
                else:
                    tmpV=tmpV//2
                    checkingStack.pop()

            elif j==']':
                if check ==1: # 최초로 닫는괄호 
                    result+=tmpV
                    tmpV=tmpV//3
                    check=0
                    checkingStack.pop()
                else:
                    tmpV=tmpV//3
                    checkingStack.pop()

            #print('checkingStack', checkingStack, ' result: ', result, 'index: ', index, ' tmpV: ', tmpV)
        print(result)

시간/공간 복잡도

해당 문제는 구현문제이기 때문에 시간/공간 복잡도를 따지지 않는다. 

최적화 및 개선

따로 하지 않음

어려웠던 점

문제를 풀다보면 결국 관건은 괄호를 닫을때 지금까지 계산한 값을 곱셈( (X) 혹은 [X] )을 할 것이냐 덧셈(결합)을 할 것이냐를 구분하는 것이 어렵다. 그런데 어떤식으로 하든 해결할 방법이 생각나지 않았다. 

(후위 계산인가 싶어서 별거 다해봄)

결과적으로는 분배법칙의 아이디어를 통해 해당 문제를 해결했다. 

( ( ) [ [ ] ] ) 해당 괄호의 경우, 분배법칙을 적용하면 ...

( ( ) ) ( [ [ ] ] )  이렇게 풀 수 있다. 

두 괄호는 계산해보면 결과 값이 같다. 

이를 잘 고려하여, 계산을 위한 변수 값을 잘 다루어 문제를 해결할 수 있었다. 

흔적 (보지마세요)

# 괄호열이 뭔지? 

# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크

# 닫기를 시작했을때, 계산시작 
# () = 2, [] = 3

# 다 닫고(if stack:) 새로 열때 +

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        print('좋다  시작하자 ')
        checkingStack = []
        cal=''
        result = 0
        for index, j in enumerate(s):
            if j=='(':
                if not checkingStack:
                    cal+='(2*'
                    checkingStack.append(j)
                else:
                    if checkingStack[-1]=='(':
                        cal+='((2+'
                        checkingStack.append(j)
                    elif checkingStack[-1]=='[':
                        cal+='(2#'
                        checkingStack.append(j)
                    elif checkingStack[-1]==')' or checkingStack[-1]==']':
                        cal+='+(2$'
                        checkingStack.append(j)
            elif j=='[':
                if not checkingStack:
                    cal+='(3'
                    checkingStack.append(j)
                else:
                    if checkingStack[-1]=='[':
                        cal+='*3'
                        checkingStack.append(j)
                    elif checkingStack[-1]=='(':
                        cal+='(3'
                        checkingStack.append(j)
                    elif checkingStack[-1]==']' or checkingStack[-1]==')':
                        cal+='+(3'
                        checkingStack.append(j)

            elif j==')':
                if checkingStack[-1]=='(':
                    cal+=')'
                    result= result+(result*2)
                    checkingStack.pop()
                

            elif j==']':
                if checkingStack[-1]=='[':
                    cal+=')'
                    result*=3
                    checkingStack.pop()
                    
            print('')
            print('j: ', j)
            print('checkingStack', checkingStack, ' result: ', result)
            print('cal',cal)
        check = 0

        # # + 추가 작업 // replace, find 다시 공부하기 
        # while 1:
        #     check = 0

        #     result1 = s.find(")(")
        #     result2 = s.find("][")
        #     result3 = s.find(")[")
        #     result4 = s.find("](")

        #     if result1!=-1:
        #         s=s.replace(")(", ")+(")
        #         check =1
        #     elif result2!=-1:
        #         s=s.replace("][", "]+[")
        #         check =1
        #     elif result3!=-1:
        #         s=s.replace(")[", ")+[")
        #         check =1
        #     elif result4!=-1:
        #         s=s.replace("](", "]+(")
        #         check =1

        #     if check == 0:
        #         break
        # print('result:', s)
        
        # # 2, 3 교체 작업 

        # while 1:
        #     check = 0
        #     result1 = s.find("()")
        #     result2 = s.find("[]")

        #     if result1!=-1:
        #         s=s.replace("()", "2")
        #         check =1
        #     elif result2!=-1:
        #         s=s.replace("[]", "3")
        #         check =1
            
        #     if check == 0:
        #         break

        # print('result?:', s)
        # tmpStack=[]
        # for i in s:
        #     tmpStack.append(i)
        
        # print('tmpStack', tmpStack)
        # p=[]
        # result = 0

# 괄호열이 뭔지? 

# 올바른 괄호열인지 체크 = 쌍을 이루는지 체크

# 닫기를 시작했을때, 계산시작 
# () = 2, [] = 3

# 다 닫고(if stack:) 새로 열때 +

from collections import deque

s = input()
stack=[]
check = 0
for i in s:
    if i =='(':
        stack.append('(')
    elif i == '[':
        stack.append('[')
    elif i == ')':
        if stack:
            if stack[-1]=='(':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check = 1
            print(0)
            break
    elif i == ']':
        if stack:
            if stack[-1]=='[':
                stack.pop()
            else:
                check = 1
                print(0)
                break
        else:
            check =1
            print(0)
            break
if check == 0:
    if stack:
        print(0)
    else:
        #print('좋다  시작하자 ')
        calStack=deque([])
        checkingStack = []
        cal=''
        result = 0
        
        for index, j in enumerate(s):
            if j=='(' or j=='[': 
                if index==0:
                    calStack.append(0)
                    checkingStack.append(j)
                else:
                    if s[index-1]==')' or s[index-1]==']':
                        checkingStack.append(j)
                        # print('된건가?')
                    elif s[index-1]=='(' or s[index-1]=='[':
                        checkingStack.append(j)
                    else:
                        checkingStack.append(j)
                        if calStack:
                            result = calStack[-1]
                            calStack.clear()
            if j==')':
                if s[index-1]=='(':
                    if checkingStack[-1]=='(':
                        print("들어오긴해?", index)
                        if index-2>=0:
                            if s[index-2]==')'or s[index-2]==']':
                                calStack[-1]+=2
                                print("나왔어?")
                            else:
                                if calStack[-1]==0:
                                    calStack[-1]+=2
                                    checkingStack.pop()
                                    print("!")
                                else:
                                    calStack[-1]*=2
                                    checkingStack.pop()
                                    print("!!")
                        elif index-1>=0:
                            calStack[-1]+=2
                            print("*")

                    else:
                        calStack.append(2)
                        result+=calStack[-1]
                        calStack.clear()
                        checkingStack.pop()
                        print("@")
                elif s[index-1]==')':
                    if calStack:
                        if len(checkingStack)==1:
                            v=sum(calStack)*2
                            calStack.clear()
                            calStack.append(v)
                        else:
                            calStack[-1]=calStack[-1]*2
                            checkingStack.pop()
                            print("??????????")
                    else:
                        result=result*2
                        checkingStack.pop()
                        print("#")
                elif s[index-1]==']':
                    if checkingStack[-1]=='(':
                        calStack[-1]=calStack[-1]*2
                        # result += sum(calStack)*2
                        # calStack.clear()
                        # checkingStack.pop()
                    print('?뭘까???')

                
            if j==']':
                if s[index-1]=='[':
                    if checkingStack[-1]=='[':
                        if index-2>=0:
                            if s[index-2]==')'or s[index-2]==']':
                                calStack[-1]+=3
                                # print("나왔어?")
                            else:
                                if calStack[-1]==0:
                                    calStack[-1]+=3
                                    checkingStack.pop()
                                else:
                                    calStack[-1]*=3
                                    checkingStack.pop()
                        elif index-1>=0:
                            calStack[-1]+=3
                        # print("!")
                    else:
                        calStack.append(3)
                        result+=calStack[-1]
                        calStack.clear()
                        checkingStack.pop()
                elif s[index-1]==']':
                    if calStack:
                        if len(checkingStack)==1:
                            v=sum(calStack)*3
                            calStack.clear()
                            calStack.append(v)
                        else:
                            calStack[-1]=calStack[-1]*3
                            checkingStack.pop()
                            # print("?")
                    else:
                        result=result*3
                        checkingStack.pop()
                    
                    #print('?뭘까')
                elif s[index-1]==')':
                    if checkingStack[-1]=='[':
                        # result += sum(calStack)*3
                        # calStack.clear()
                        # checkingStack.pop()
                        calStack[-1]=calStack[-1]*3

            print('checkingStack', checkingStack, ' result: ', result, ' calStack: ', calStack, 'index: ', index, ' j: ', j)

        for i in calStack:
            result+=i

        print(result)

알게된 것

해당 문제에 대한 접근법

https://www.acmicpc.net/problem/10799

문제 해결 방법

0. 카운트 변수를 만든다. 초기화는 0으로 한다. 

1. 받은 문장을 한글자씩 순회하며  현재 열려있는 괄호를 스택에 넣는다. (flag 표시를 해준다 flag = 1)

2. 문장을 순회하다가 닫는 괄호가 나오면 바로 직전에 본 글자가 열려있는 괄호인지 확인한다. (확인은 flag를 통해서 한다. )

 2-1. flag가 1이면 레이저로 확인되었으므로 그동안 열려있는 괄호의 수만큼 카운트 변수에 +1을 해준다. 

 2-2. flag가 0이면 단순 닫는 flag이니 괄호를 닫아주되(들어가있는 값중 -1 인덱스의 값이 열린괄호가 있으면 pop), 하나의 종이를 레이저가 한번 자르면 종이가 n개면 +1이 된다는 것을 고려하여 카운트값에 +1을 해준다.  

3. 순회가 끝날 때 까지 2번을 반복한다. 

코드 구현

정답 코드 

# ()는 레이저다 

s = input()
stack=[]
cnt = 0
flag=0
for i in s:
    if i =='(':
        stack.append('(')
        flag=1
    elif i==')':
        if stack[-1] =='(':
            stack.pop()
            if stack and flag==1:
                if flag ==1:
                    cnt+=len(stack)
            if flag ==0:
                cnt+=1
            flag=0


    # print('난 ',i,'에요', stack, 'cnt: ', cnt)
print(cnt)

시간/공간 복잡도

괄호 문자는 최대 100,000 이므로, O(NlogN)으로 풀어야한다. 

최적화 및 개선

따로 하지 않음 

어려웠던 점

없음

알게된 것

따로 없음 

https://www.acmicpc.net/problem/2110

문제 해결 방법

0. 카운트 변수를 생성한다 초기값은 0

1. 받은 활호문장을 순회하면서 현재 괄호를 열고있는게 몇개인지 계속 체크를 한다. 

2. 괄호를 닫게 될 경우가 2가지 가 있다. 

    2-1. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나왔는지 체크한다. 이것은 괄호를 순회하며 사전에 flag로 지속적으로 체크한다. (flag=1)

    2-2. 순회하면서 닫는 괄호가 나온 경우, 직전에 여는 괄호가 나오지 않은 경우, flag는 0인 경우이다. 

3. 2-1의 조건을 통과한 경우, 현재 열고있는 괄호의 갯수만큼 카운트 변수에 더해준다. 

    2-2의 조건을 통과한 경우, 

코드 구현

정답 코드 

import sys
input = sys.stdin.readline

n, c = map(int, input().split())

tmp=[]
for i in range(n):
    x = int(input())
    tmp.append(x)

tmp.sort()
print(tmp)

start = 1 # 최소 거리
end = tmp[-1]-tmp[0] # 최대 거리
cnt=1
result = 0
while start<=end:
    mid = (start + end) // 2 # 중간 간격 거리
    cnt = 1 # 첫번째 원소는 이미 방문한 것으로 침
    curr = tmp[0]

    for i in range(1, len(tmp)):
        if tmp[i] >= mid + curr: # 이동하려는 간격이 (중간간격 거리 + 현재 위치) 보다 크면
            cnt+=1
            curr=tmp[i]
        
    if cnt >= c: # 공유기 설치가 끝났으면, 범위를 좀 더 퍼트려줄 필요가 있다. 
        start=mid+1
        result=mid
    else: # 범위에 못미치면 범위를 줄여줄 필요가 있다. 
        end=mid-1

print(result)

시간/공간 복잡도

n^2으로 못풂

최적화 및 개선

• 따로 하지않음

어려웠던 점

• 상당히 낯설고 어렵게 느껴지는 문제이다. 
• 이분탐색 알고리즘을 적용하고 싶은데 와닿는 이해가 되지 않는 문제였다. => 다음에 다시 풀어볼 문제

알게된 것

• 이분탐색을 이렇게도 사용할 수 있다는점 
• 이진탐색을 공유기 사이에 거리에 써야하는 것
•