개발자 아지트

https://school.programmers.co.kr/learn/courses/30/lessons/12973

문제설명

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한사항

문자열의 길이 : 1,000,000이하의 자연수

문자열은 모두 소문자로 이루어져 있습니다.

입출력 예

s         result

baabaa  1

cdcd     0

입출력 예 설명

입출력 예 #1

위의 예시와 같습니다.

입출력 예 #2

문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

문제 해결 방법

주어진 str을 list로 바꿔서 list 요소를 순회시킨다. 

스택으로 쓸 배열을 하나 만든다. 

첫번째 요소는 스택에 넣고,

두번째 요소부터는 스택에 있는 값을 꺼내어 비교한 후 같으면 아무 동작하지 않고 넘어간다. 

만약 같지 않으면, 꺼낸 값을 스택에 다시 넣고, 현재 보고있는 list 요소도 스택에 같이 넣는다. 

순회가 끝나고, 스택의 길이를 재봤을때, 길이가 0이면 1을 반환, 길이가 0보다 크면 0을 반환한다. 

코드 구현

def solution(s):
    #O(nLogN)으로 구현
    stakk =[]
    newS=s
    newS=list(newS)
    
    for i in range(len(newS)):
        if i == 0 or len(stakk)==0:
            stakk.append(newS[i])
        else:
            a = stakk.pop()
            if newS[i] == a:
                continue
            else:
                stakk.append(a)
                stakk.append(newS[i])
    
    if len(stakk)==0:
        return 1
    else:
         return 0

시간/공간 복잡도

문제 제한 사항을 보니 O(NlogN)으로 풀어야 할 것 같았다. 

나는 O(N)으로 구현하게 되었다. 

최적화 및 개선

안함

어려웠던 점

머릿속으로 확신을 가지고 구현한게 아니라 이게 맞나 싶었는데 풀렸다. 

이런식으로 풀면 안좋다 그러던데,,, 담엔 확신 가질만큼 종이에 로직을 써보고 문제 풀어야겠다.

https://school.programmers.co.kr/learn/courses/30/lessons/76502#

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.

만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.

만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

s의 길이는 1 이상 1,000 이하입니다.

입출력 예

s         result

"[](){}"    3

"}]()[{"    2

"[)(]"     0

"}}}"      0

입출력 예 설명

입출력 예 #1

다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.

x         s를 왼쪽으로 x칸만큼 회전          올바른 괄호 문자열?

0         "[](){}"    O

1         "](){}["    X

2         "(){}[]"    O

3         "){}[]("    X

4         "{}[]()"    O

5         "}[](){"    X

올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.

x         s를 왼쪽으로 x칸만큼 회전          올바른 괄호 문자열?

0         "}]()[{"    X

1         "]()[{}"    X

2         "()[{}]"    O

3         ")[{}]("    X

4         "[{}]()"    O

5         "{}]()["    X

올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

문제 해결 방법

문제가 스택 자료구조로 풀어야 할 문제임에도 불구하고, 스택으로 풀 생각을 구체적으로 하지않고 그냥 단순히 함수만 쓸 생각으로 코드를 짰다. 아니나 다를까 문제는 거진 통과인데 제일 마지막 테스트케이스에서 딱 멈췄다. 

아~~ 테스트케이스를 추가하고 나서 어떻게 풀지 다시 생각해봤다. 

추가한 테스트 케이스는 다음과 같다. 

마지막 테스트 케이스를 풀기위해서는.. 아무리 생각해봐도 ... 스택적으로 문제를 풀 방법이 없다는 것을 깨달았다...

코드를 전면 수정했다. 기존 코드는 싹 지우고 다시 시작했다. 

주어진 string을 순회 시키고, 

각 string에서 한자 한자씩 읽는다. 

(, {, [ 를 왼쪽 괄호라고 부르겠다. 배열 하나를 새로 만들고

왼쪽 괄호가 나오면 그 배열에 왼쪽 괄호를 PUSH 한다. 

), }, ] 가 나오면 그 배열에서 POP한 것과 읽고 있는 글자가 같으면 넘어가고 카운트 한다

만약 글자가 같지 않으면 올바르지 않은 괄호 문자열이라고 판단한다. 

코드 구현

개선된 코드

def solution(s):
    left1 = [] 
    left2 = [] 
    left3 = [] 
    
    check = [0]*3
    pass1=0
    pass2=0
    
    for i in s:
        if i == '(':
            check[0]+=1
        elif i == '[':
            check[1]+=1
        elif i == '{':
            check[2]+=1
        elif i ==')':
            check[0]-=1
        elif i == ']':
            check[1]-=1
        elif i == '}':
            check[2]-=1
    
    if check[0] ==0 and check[1]==0 and check[2]==0:
        pass1=1
    
    mylist=list(s)
    
    if pass1==0:
        return 0
    
    else:
        thisis = 0
        for i in range(len(s)):
            stakk = [] 

            
            word = mylist.pop()
            mylist.insert(0, word)
            #print(mylist)
            #print("---")
            breakk=0
            for i in mylist:
                #print(i)
                if i == ']':
                    try: 
                        word = stakk.pop()
                        if word == '[':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == ')':
                    try: 
                        word = stakk.pop()
                        if word == '(':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == '}':
                    try: 
                        word = stakk.pop()
                        if word == '{':
                            continue
                        else:
                            breakk=1
                            break
                    except:
                        breakk=1
                        break
                elif i == '[':
                    stakk.append('[')
                elif i == '(':
                    stakk.append('(')
                elif i == '{':
                    stakk.append('{')
            
            if len(stakk)==0 and len(stakk)==0 and len(stakk)==0 and breakk==0:
                thisis+=1

        return thisis

기존 코드

def solution(s):
    left = [0] * 3
    
    check = [0]*3
    pass1=0
    pass2=0
    
    for i in s:
        if i == '(':
            check[0]+=1
        elif i == '[':
            check[1]+=1
        elif i == '{':
            check[2]+=1
        elif i ==')':
            check[0]-=1
        elif i == ']':
            check[1]-=1
        elif i == '}':
            check[2]-=1
    
    if check[0] ==0 and check[1]==0 and check[2]==0:
        pass1=1
    
    mylist=list(s)
    
    if pass1==0:
        return 0
    
    else:
        thisis = 0
        for i in range(len(s)):
            left = [0] * 3
            
            word = mylist.pop()
            mylist.insert(0, word)
            #print(mylist)
            #print("---")
            for i in mylist:
                #print(i)
                if i == ']':
                    left[0]-=1
                elif i == ')':
                    left[1]-=1
                elif i == '}':
                    left[2]-=1
                elif i == '[':
                    left[0]+=1
                elif i == '(':
                    left[1]+=1
                elif i == '{':
                    left[2]+=1
            
                if left[0]<0 or left[1]<0 or left[2]<0:
                    break
            #print('left[0]', left[0], 'left[1]', left[1], 'left[2]', left[2])
            
            if left[0]>=0 and left[1]>=0 and left[2]>=0:
                thisis+=1

            
                

        return thisis

시간/공간 복잡도

제한 사항을 보아하니 O(N^2)으로 구현해도 되겠다 싶었다. 

구현도 O(N^2)로 맞춰서 했다. 

최적화 및 개선

이렇게 되면 사실상 개선된 코드에서 짝맞추는 코드는 없애도 될 것 같다. 

어려웠던 점

생각하기,, 자료구조를 적용해서 생각하기,, 

브랜치 삭제 방법

1. 로컬 브랜치 삭제

git branch -D [브랜치 이름]

2. 원격 브랜치 삭제 

원격 브랜치에 내 브랜치가 있는지 확인해본다. 

git branch -r

원격 브랜치를 삭제한다. 

git push [원격저장소 이름] -d [원격 브랜치 이름]

자주 쓰는 명령어

$git remote update #git remote를 갱신

$git status #현재 git 에서의 상태를 타나냄

$git branch -r #-r옵션으로 원격 저장소의 branch list를 볼 수 있음

$git branch -a #-a옵션으로 로컬과 원격 저장소 모두의 branch list를 볼 수 있음

$git branch -d <branchname> #git 브랜치 삭제

참고 - $echo ‘hello world’ > a.txt 하면 내용들어간 파일 생성됨

git add 할 때 숨김 파일도 추가하게 하기

특정 폴더에 있는 모든 파일을 추가하고자 할 때 git add * 명령어를 쓰곤 한다. 그런데 저렇게 하면 숨김파일은 추가가 안됨.

숨김파일까지 추가하고자 한다면?

$git add /.

Git원격저장소에 다른 branch push하기

master 브랜치말고 예를들어서 me 브랜치에 푸시한다 치자.

‘me’ branch가 안만들어 졌으면

$git branch me 를 하면 브랜치 생성됨

사용하는 작업 디렉토리를 me 브랜치로 변경

$git checkout me

정상적으로 변경되었으면 밑에 Switched to branch ‘me’ 이런 문구 뜸

테스트가 하고싶으면 .txt파일 하나 작성.

$git add . or $git add 특정파일

$git commit -m “메모 메모 메모 ~”

$git push origin (origin의 master가 아닌 다른 브랜치명)

해시는 해시 함수를 통해 변환한 값을 인덱스처럼 사용하고, 키와 값을 저장하여 데이터 탐색을 빠르게 할 수 있다. 

해시는 키를 사용해서 데이터 탐색을 빠르게 한다. 

값을 검색하기 위해서 활용하는 것은 키고, 키를 통해 해시값이나 인덱스로 변환할 때는 해시 함수를 통한다. 이때, 해시 함수는 키를 일정한 해시 값으로 변환 시킨다. 

해시의 특징

1. 해시는 키를 통해 값을 찾을 수 있지만, 값을 통해 키를 찾을 수는 없다. 

2. 키 자체가 해시함수를 통해 값이 포함된 인덱스이므로 값을 찾기 위한 과정이 필요 없다. 따라서 탐색은 O(1)의 시간복잡도가 걸린다. 

3. 값을 인덱스로 활용하기 위해서는 적절한 변환 과정을 거쳐야 한다. 

해시 테이블은 키와 대응한 값이 저장되어 있는 공간이고, 해시 테이블의 각 데이터를 버킷이라고 한다. 

해시 함수

해시 함수 구현시 고려 사항

1. 해시 함수를 통한 결과는 해시 테이블의 크기인 0~(N-1) 사이의 값을 내야한다. 

2. 해시 함수가 변환한 값의 충돌(중복 발생)은 최대한 작은 확률로 일어나게끔 해야한다.  (충돌 발생은 불가피함)

자주 사용하는 해시 함수

나눗셈법

나눗셈법에 소수가 아닌 수를 사용하면 충돌이 많이 발생한다. 

따라서 나눗셈법의 해시 테이블의 크기는 소수를 사용해야한다. 

이렇게 하면, 나눗셈법의 해시 테이블 크기는 K가 된다.

왜냐하면 K에 대해 나머지 연산(모듈러 연산)을 했을 때, 나올 수 있는 값은 0 ~ (K - 1)이기 때문이다. 

그러나, 매우 큰 소수를 구하는 방법 중 효율적인 방법은 없다는 점이 단점이다. 

곱셈법

곱셈법도 나눗셈법 처럼 모듈러 연산을 활용하지만 소수는 사용하지 않는다. 

곱셈법의 공식 

 h(x) = ((( x * A ) mod 1 ) * m)

m은 최대 버킷의 개수, A는 황금비이고 무한소수이지만, 소수부의 일부인 0.6183만 이용한다. 

1. 키에 황금비를 곱한다. 

2. 1번 결과에 모듈러 1을 취한 후, 소수 부분만 취한다. 

3. 2번 결과 값에 테이블 크기 m을 곱한다. 

3번 결과를 통해 테이블의 인덱스인 0 ~ (m - 1)에 매치할 수 있다. 

곱셈법은 소수가 필요없고, 테이블의 크기가 커져도 추가 작업이 필요없다. 

문자열 해싱

키의 자료형이 문자열일 때, 문자열을 해싱하는 방법은 다음과 같다. 

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될만한 값으로 숫자를 다듬어주면 된다. 

문자열을 해싱하기 위해 사용하는 다항식 rolling method이다. 

hash(s) = (s[0] + s[1]*p + s[2]*p^2  … s[n-1]*p^n-1) mod m

문자열의 문자를 숫자로 변환해준 후, 테이블의 인덱스에 매칭될 만한 값으로 숫자를 다듬어 줄 때, 

중간 중간에 모듈러 연산을 한 후 더한값에 대해 모듈러 연산을 하게되면 오버플로우를 최대한 방지할 수 있다. 

*** 일반적인 수식에도 모듈러 연산이 있는 문제중에서 큰 수를 다루는 문제는 오버플로우를 어떻게 처리하는지 확인하는 함정이 있으니, 유의해야한다. 

충돌 처리

해시 테이블은 충돌 발생이 불가피 하므로, 반드시 충돌 처리를 해줘야한다. 

체이닝

충돌 처리는 체이닝으로 처리할 수 있다. 

체이닝은 해싱한 값중 중복값이 나올 경우, 해당 버킷에 링크드리스트로 같은 해시값을 가지는 데이터를 연결하는 방법이

다.

그러나 이 방법에는 두가지 단점이 존재한다. 

1. 충돌이 많아질 경우, 링크드리스트의 길이가 길어지고 사용하지 않은 해시 테이블의 공간은 덜사용하게 되므로 공간 활용성이 떨어진다. 

2. 충돌이 많아질 경우, 링크드리스트의 한계로 인해 검색 성능이 떨어진다. 

왜냐하면, 링크드리스트로 검색할때 맨 처음부터 검색하기 때문이다. 

최악의 경우, O(N)의 시간복잡도가 발생할 수 있다. 

개방 주소법

이를 개방 주소법으로 개선할 수 있다. 
개방 주소법은 체이닝과 달리, 빈 버킷을 찾아서 충돌값을 삽입한다. 

이 방법은 체이닝보다 메모리를 더 효율적으로 사용하는 방법이다. 

개방 주소법 중 하나로 선형 탐사 방식이 있다. 

이 방식은 충돌발생 시 다른 빈 버킷을 찾을 때 까지 일정한 간격으로 이동한다. 

h(k, i) = (h(k) + i) mod m

*보통 간격은 1로 한다

단, 이 방법에도 단점이 있다. 

충돌 발생 시 한 칸씩 이동하며 해시 테이블의 빈 곳을 찾아서 값을 넣을 경우, 해시 충돌이 발생한 값끼리 모이는 영역이 발생한다. 이를 클러스터를 형성한다고 한다. 이런 영역이 발생하면 해시값이 충돌할 확률이 더 높아진다. 

이를 개선하기 위해 이중 해시 방식이 있다. 

이 방식은 해시 함수를 2개 사용하는 방식이다.  N개로도 늘려서 사용할 수 있다. 

첫번째 해시 함수는 기존 해시 함수의 역할을 수행하고, 두번째 해시 함수의 역할은 첫 번째 해시 함수의 결과로 충돌이 발생하면, 해당 위치를 기준으로 위치를 어디로 정할지 새로 결정하는 역할을 한다. 

*h1은 1차 해시함수, h2는 2차 해시함수이다. 

h(k,i) = (h1(k) + i * h2(k)) mod m

수식을 보면 선형 탐사 방식과 비슷하지만 클러스터를 줄이기 위해, m을 제곱수나 소수로 한다. 

실제 코테 문제에서 해시 문제의 핵심은 키와 값을 매핑하는 과정이다. 

특정 값이나 정보를 기준으로 자주 검색하거나 특정 값과 매핑 값의 관계를 확인해야 하는 작업이 문제에 포함되면 해시를 고려해봐야 한다. 

front와 rear을 사용하는 큐는 원형 큐에 비해서 메모리 낭비가 있는 편이다. 

파이썬에서 원형 큐를 사용하기 위해서는 리스트나 덱을 활용하여 구현할 수 있다. 

리스트를 큐 처럼 사용하기 

queue = []

# 큐에 데이터 추가

queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거 

first_item = queue.pop(0)
print(first_item) # 출력: 1

# 큐에 데이터 추가
queue.append(4)

 #  큐의 맨 앞 데이터 제거 
first_item = queue.pop(0)
print(first_item) # 출력: 2

덱을 큐처럼 활용하기 

# deque = Double Ended Queue의 줄임말 
# 양 끝에서 삽입이나 삭제할 수 있는 큐 
# 위의 특징 때문에 큐를 구현할 때 덱을 사용하는 것이 좋음

from collections import deque

queue = deque( )

# 큐에 데이터 추가
queue.append(1)
queue.append(2)
queue.append(3)

# 큐의 맨 앞 데이터 제거 

first_item = queue.popleft()
print(first_item) # 1

# 큐에 데이터 추가 
queue.append(4)

# 큐의 맨 앞 데이터 제거 

first_item = queue.popleft()
print(first_item) # 2

*pop(0)이 popleft()보다 훨씬 느리므로, 반드시 pop(0) 대신에 popleft() 를 사용할 것.

6장 스택

스택의 개념 

• 먼저 입력한 데이터를 제일 나중에 꺼낼수 있는 자료구조
• 맨 나중에 입력한 데이터를 제일 먼저 꺼낼 수 있는 자료구조
• 스택에 삽입하는 연산을 Push이라고 함
• 스택에서 꺼내는 연산을 Pop이라고 함

스택의 정의

ADT(Abstract data type) 추상 자료형이다. 

이때, 추상 자료형은 인터페이스만 있고 실제로 구현은 되지 않은 자료형을 말한다. 

즉, 구현되지 않은 설계만 된 자료형이라고 생각하면 된다. 

스택을 ADT형태로 정의해보면 다음과 같다. 

스택의 요소는 다음과 같다. 

• 푸시 Push(반환타입 - 없음)
• 팝 Pop (반환타입 - 아이템의 반환타입)
• 가득 찼는지 확인 isFull (반환타입 - boolean 타입)
• 비었는지 확인 isEmpty (반환타입 - boolean 타입)
• 최근에 삽입한 데이터의 위치를 저장할 변수인 탑 Top (반환타입 - int 타입)
  • 통상적으로 Top은 -1로 초기화 한다
  • Top이 0이 되면 값이 하나 있다는 의미이다. 
• 스택의 자료를 관리하는 배열 (아이템 타입 data[maxsize])

스택의 세부 동작

이번 포스팅에서 이 부분이 제일 중요하다. 

파이썬과 같은 언어로 스택을 구현하면 위에있는 모든 추상자료형의 요소들을 구현하지 않아도 스택을 쉽게 구현할 수 있다. 

그러나 뭐든지간에 본질이 기본이되어야 하는법이다. 

본질적인 것만 알면 스택에 관한건 통!! 한다. ㅎㅎ 

스택의 세부 동작은 다음과 같은 두 경우를 통해 설명하겠다. 

[스택에 3을 push 하는 경우]

1. isFull을 통해 push하고자 하는 스택에 공간이 있는지 확인한다. 
2. 공간이 있다면, top의 값을 +1한다.
3. 해당 인덱스의 칸에 데이터를 삽입한다. 

[스택에 3을 pop 하는 경우]

1. isEmpty를 통해 pop하고자 하는 스택이 혹시 빈공간은 아닌지, 꺼낼 값이 없는건 아닌지 확인한다. 
2. 값이 있다면, top의 값을 -1 한다.
3. top의 값을 -1하기 전의 값을 반환한다.

이때 반환한 값, 배열의 데이터를 지우거나 하지 않는다. 

top의 값만 -1을 해준다. 

향후 이것은 아무 문제가 되지 않는다. 왜냐하면 top은 -1이 된 위치를 가리키기는데, isEmpty라던지 isFull을 통해 스택의 내부 사정을 물어볼 때 top을 통해 상태를 확인하기 때문이다. 

파이썬에서는 list자료 구조(그 외의 다른 자료구조 또한 사용가능), append()나 pop(), len()을 통해 스택을 쉽게 구현할 수 있다. 

5장 배열 

배열의 개념 

배열은 자료구조로서 데이터를 저장할 수 있는 모든 공간마다 인덱스와 일대일 대응한다. 

따라서 어떤 위치에 있는 데이터든 한 번에 접근할 수 있어서 인덱스만 알면 데이터를 빠르게 탐색할 수 있다. 

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

배열 선언

1)배열 선언의 방법 

일반적인 방법

arr = [0, 0, 0, 0, 0, 0]
arr = [0] * 6
# 두 코드의 결과 값은 동일하다.

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

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

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

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

2)배열의 특징

• 배열은 인덱스가 0부터 시작한다. 
• 파이썬의 경우 배열을 지원하는 문법은 없고 대신 리스트 문법을 사용하면 된다. 
• 파이썬의 리스트는 동적으로 크기를 조절할 수 있도록 구현되어있고, 슬라이싱, 삽입, 삭제, 연결 등 연산을 사용할 수 있어서 편리하다. 

배열과 차원

배열은 2차원, 3차원 등 다차원 배열로 존재할 수 있다. 

하지만 컴퓨터 메모리는 1차원이다. 때문에 배열은 차원과 무관하게 메모리에 연속적으로 할당된다. 

1) 1차원 배열

만약 배열이 0번부터 10번까지 있다면 0번 배열에는 낮은 메모리 주소에서 시작하여 10번 배열까지는 오름차순으로 메모리 주소가 높아진다. 

2) 2차원 배열 

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

# 2차원 배열을  다음과 같이 출력할 수 있다. 
print(arr[2][3]) #12 출력

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

#변경된 값을 출력
print(arr[2][3]) # 15

리스트 컴프리헨션을 사용하면 다음과 같이 선언할 수 도 있다. 

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

배열 연산의 시간 복잡도

배열은 임의 접근이라는 방식으로 접근함으로 모든 위치에 있는 데이터를 한번에 접근할 수 있다. 

따라서 데이터에 접근하기 위한 시간 복잡도는 O(1)이다. 

배열 데이터에 맨 앞에 다른 새로운 데이터를 추가한다면, 기존에 있던 데이터는 뒤로 한칸씩 밀어야 한다. 

따라서 이를 위한 연산이 필요한데, 이때 총 데이터의 개수가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

만약 배열의 데이터의 중간에 다른 데이터를 삽입할 경우 중간 이후에 있는 데이터를 뒤로 한칸씩 밀어야한다. 

중간 이후에 있는 데이터가 N개라면 이를 위한 연산의 시간 복잡도는 O(N)이 된다. 

== 배열은 특정한 경우에 따라서 데이터 추가나 삭제에 드는 비용이 많을 수 있다. 

배열을 선택할 때 고려할 점 

배열은 임의 접근이라는 특징으로 인해 인덱스를 통해 데이터로 바로 접근할 수 있어서 데이터에 빈번하게 접근하는 경우에 효율적이지만, 메모리 낭비가 발생할 수 있다. 따라서 다음과 같은 사항을 고려해야한다. 

1. 할당할 수 있는 메모리의 크기 확인(배열로 표현하고자 하는 데이터에 대한 메모리의 크기 확인)

2. 중간이나 맨 앞에 데이터 삽입이 빈번한가?(이럴 경우 시간복잡도가 높아짐)

(단, 현재 파이썬에서 리스트로 배열을 구현함으로써 배열 크기에 대한 고민은 하지 않아도 되고, 배열의 특성정도로만 이해하면 됨)

배열 구현을 위해 자주 사용하는 파이썬 리스트 기법

리스트에서 데이터 추가하기 

append() 메서드로 데이터 추가하기 

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

+연산자로 데이터 추가하기 

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

insert() 메서드로 데이터 추가하기 

tmp_list = [1, 2, 3, 4, 5]
tmp_list.insert(2, 9999) # [1, 2, 9999, 3, 4, 5]

리스트에서 데이터 삭제하기 

pop() 메서드로 특정 위치의 데이터 팝

tmp_list = [1, 2, 3, 4, 5]
popped_element = tmp_list.pop(2) # 3
print(tmp_list) # [1, 2, 4, 5]

remove() 메서드로 특정 데이터 삭제 

- 인수로 받은 값이 처음 등장하는 위치의 데이터를 삭제함 

tmp_list = [1, 2, 3, 2, 4, 5]
tmp_list.remove(2) # [1, 3, 2, 4, 5]

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

리스트에 제곱 연산 적용 예

numbers = [1, 2, 3, 4, 5]
squares = [num**2 for num in numbers] # [1, 4, 9, 16, 25] 이래도 nubers는 여전히 [1, 2, 3, 4, 5]임

4장 코딩테스트에 필요한 필수 문법 

빌트인 데이터 타입

파이썬의 데이터 타입은 다음과 같다. 

정수형 산술 연산에서 헷갈리는 부분만 코드를 통해 기술하였다. 

a = 13
b = 4

print(a / b)  # 나누기 (소수점 포함) 3.25
print(a // b) # 나누기 (소수점 제외)  3
print(a % b)  # 모듈러 연산 (나머지) 1
print(-a)     # 부호를 바꿈 -13
print(abs(-a))# 절대값 13
print(a**b)   # a의 b승 28561

정수형 비트 연산 정리는 코드를 통해 기술하였다. 

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

부동소수형 데이터를 다룰 일이 생겼을 때 엡실론을 항상 생각해야 한다. 

• 앱실론이란? 파이썬 부동소수형 데이터를 이진법으로 표현하기 때문에 표현 과정에서 발생하는 오차를 말한다. 

컬렉션 데이터 타입에서 컬렉션은 여러 값을 담는 데이터 타입을 말한다. 

대표적으로 리스트, 튜플, 딕셔너리, 셋, 문자열 등이 있다. 

여기서 데이터 수정 여부에 따라 뮤터블객체(변경할 수 있는 객체), 이뮤터블객체(변경할 수 없는 객체)로 구분할 수 있다. 

뮤터블 객체의 리스트는 사용 방법은 5장 배열의 코드를 통해 기술하였다. 

인덱싱은 인덱스를 활용해 특정 위치의 원소에 접근하는 것을 말한다. 

리스트 슬라이싱 방법은 코드를 통해 기술하였다. 

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

딕셔너리에 대한 정리는 코드를 통해 기술하였다. 

# 딕셔너리 선언
tmp_dict = { }

# 딕셔너리 값 삽입
tmp_dict["mouse"] = 1
tmp_dict["keyboard"] = 2
tmp_dict["monitor"] = 3

# 딕셔너리 값 출력
print(tmp_dict) # {'mouse': 1, 'keyboard': 2, 'monitor': 3}

# 딕셔너리 값 검색
key = "mouse"
if key in tmp_dict:
	value = tmp_dict[key]
    print(f"{key}: {value}") # mouse: 1
else:
	print(f"{key}는 딕셔너리에 존재하지 않음")

# 딕셔너리 값 삭제
del tmp_dict["mouse"]
print(tmp_dict) # {'keyboard': 2, 'monitor': 3}

튜플에 대한 정리는 코드를 통해 기술하였다. 

리스트, 딕셔너리와 달리 한 번 생성하면 삽입하거나 삭제할 수 없다. 

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

# 튜플 인덱싱, 슬라이싱 
# 문법 자체는 리스트와 같다. 

# 인덱싱
python(tmp_tuple[0]) # 1
python(tmp_tuple[1]) # 2
python(tmp_tuple[2]) # 3

# 슬라이싱

python(tmp_tuple[1:])  # (2, 3)
python(tmp_tuple[:2])  # (1, 2)
python(tmp_tuple[1:2]) # (2,)

리스트도 있는데 굳이 튜플을 쓰는 이유는 실수로 값을 변경하는 실수를 방지하기 위함이다. 

문자열에 대한 정리는 코드를 통해 기술하였다. 

# 문자열 추가 
string = "h"
string += "i"
print(string). # "hi"

# 문자열 수정
string = "hii"
string = string.replace("ii", "") # "i"를 모두 삭제
print(string)					  # H

함수의 람다식에 대한 정리는 코드를 통해 기술하였다. 

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

# 람다를 이용한 간단한 함수 정의
add = lambda x, y: x + y
print(add(5, 4)) # 9

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

코딩 테스트 구현 노하우는 3가지이다. 

조기반환은 코드 실행 과정에 있어서 함수 끝까지 가기전에 반환하는 기법이다. 이를 통해 코드의 가독성을 높이고 예외를 깔끔하고 빠르게 처리할 수 있다. 조기반환에 대한 정리는 코드를 통해 기술하였다. 

def total_price(quantity, price):
	total = quantity * price
    if total > 100:
    	return total * 0.9
        # 이렇게하면 이후 예외에 대한 처리를 하지 않아도 된다. 
    return total 
    
print(total_price(4, 50))

보호구문은 본격적인 로직을 진행하기 전 예외 처리 코드를 추가하는 기법임.
예를 들어 조건문을 사용해 초기 입력값이 유효한지 검사하고, 그렇지 않으면 바로 함수를 종료하는 보호 구문을 쓸 수 있음 

def calculate_average(numbers):
	if numbers is None:
    	return None
    
    if not isinstance(numbers, list): # numbers가 리스트가 아니면 종료(예외)
    	return None
        
    if len(numbers) == 0: # numbers의 길이가 0이면 종료(예외)
    	return None
        
    total = sum(numbers)
    average = total / len(numbers)
    return average

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

이는 람다식을 활용하여 구현한다. 

def add_three(x):
	return x + 3
    
def square(x):
	return x * x
    
composed_function = lambda x: square(add_three(x))
print(composed_function(3)) # 36

https://school.programmers.co.kr/learn/courses/30/lessons/49994

문제설명

게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.

U: 위쪽으로 한 칸 가기

D: 아래쪽으로 한 칸 가기

R: 오른쪽으로 한 칸 가기

L: 왼쪽으로 한 칸 가기

캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.

제한사항

dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.

dirs의 길이는 500 이하의 자연수입니다.

입출력 예

dirs      answer

"ULURRDLLU"     7

"LULLLLLLU"       7

입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

입출력 예 #2

문제의 예시와 같습니다.

문제 해결 방법

1. 우선 음수 좌표의 끝(-5,-5)를 (0,0)으로 생각하고 구현했다. 

2. set() 함수를 통해 중복을 제거함

3. U,D,L,R은 조건문을 통해서 처리되게 하였고, 제한하는 영역을 벗어나면 돌아올 수 있게 해줌

4. 지나간 거리는 예를들어 하나의 거리를 왼쪽에서 오른쪽으로 지나든, 오른쪽에서 왼쪽으로 지나든 방향 상관이 없기 때문에 해당 부분을 잘 체크해주었음 

코드 구현

개선한 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    arr=[]
    now = [5, 5]
    
    result = set()
    
    for dir in dirs:

        n1, n2 = now[0], now[1]
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
        xtox, ytoy = now[0], now[1]

        if n1==xtox and n2==ytoy:
            pass
        else:
            result.add((n1, n2, xtox, ytoy))
            result.add((xtox, ytoy, n1, n2))
        
    answer=len(result)/2
    
    return answer

기존의 코드 

def solution(dirs):
    answer = 0
    
    c = [[0]*11 for _ in range(11)]
    # 나는 (5, 5)에 있다. 거기서부터 시작한다. 
    
    print(c)
    
    arr=[]
    
    now = [5, 5]
    arr.append([5,5])
    
    for dir in dirs:
        if dir == "U":
            now[1]+=1
            if now[1]==11:
                now[1]=10
                
        elif dir == "D":
            now[1]-=1
            if now[1]==-1:
                now[1]=0
                
        elif dir == "L":
            now[0]-=1
            if now[0]==-1:
                now[0]=0
                
        elif dir == "R":
            now[0]+=1
            if now[0]==11:
                now[0]=10
                
        print(now)    
        one=now[0]
        two=now[1]
        c[one][two]=1
        arr.append([one, two])
        
    print(arr)
    #중복제거를 먼저하고
    #이전에 갖고있던 원소랑 
    
    cnt=0
    for i in c:
        cnt += i.count(1)
        
    print("cnt:", cnt)
    
    return answer

시간/공간 복잡도

O(N)

최적화 및 개선

처음에는 좌표만큼의 이차원 배열을 0으로 채워 구현하고 그 좌표를 지나면 좌표에 대한 자리를 1로 바꿔주었다. 그런데 문제 예시 1번과 2번의 케이스에 대해 답이 다르게 나왔다. 이 케이스를 공통적으로 해결하기 위해서는 반드시 어디에서 출발했는지도 포함이 되어야 답이 나오는 문제였다. 

따라서 어떤 좌표에 도착했는지만 메기던 기존 코드에서 어디에서 출발했는지도 추가해서 4요소를 set을 통해서 추가하였다. 

어려웠던 점

아직 내공이 부족하구나~ 혼자 힘으로 해결하는 것도 좋지만, 안되겠다 싶으면 빠르게 인정하고 배움의 자세로 바로 공부하고 다음에 또 도전하는 것이 나에게 더 좋은 방법인것 같다~ 고집 이제 안녕~

https://school.programmers.co.kr/learn/courses/30/lessons/42889

문제설명

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

실패율은 다음과 같이 정의한다.

스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

스테이지의 개수 N은 1 이상 500 이하의 자연수이다.

stages의 길이는 1 이상 200,000 이하이다.

stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.

각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.

단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.

만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.

스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

N                 stages        result

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

4                  [4,4,4,4,4]                    [4,1,2,3]

입출력 예 설명

입출력 예 #1

1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

3 번 스테이지 실패율 : 2/4

4번 스테이지 실패율 : 1/2

5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

[3,4,2,1,5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

[4,1,2,3]

문제 해결 방법

처음에는 for문 안에서 for문이 돌때 마다 도전한 사용자와 클리어하지 못한 사용자를 체크했었다. 

이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났다. 

이 문제를 해결하기 위해서 스테이지별로 도전하는 사용자의 수를 따로 체크하고, 실패한 사용자를 따로 체크해야했다. 

코드 구현

통과한 코드 

def solution(N, stages):
    answer = []
    # 도전 
    # 스테이지 별 도전자 수를 구함 
    challenger = [0] * (N+2)
    for stage in stages:
        challenger[stage] += 1
    
    fails = { }
    total = len(stages)
    
    for i in range(1, N+1):
        if challenger[i]==0:
            fails[i] = 0
        else:
            fails[i] = challenger[i] / total
            total=total-challenger[i]
            
    #print(fails)
    
    result = sorted(fails, key=lambda x: fails[x], reverse=True)
    #값을 기준으로 키를 정렬해서 반환함 
    
    #print(result)
    
    return result​

이 부분에서 5, 9, 22번 테스트케이스에서 계속 시간초과가 났던 코드 

def solution(N, stages):
    # 실패율을 구하는 코드를 완성하라 
    # 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수
    
    # 전체 스테이지의 개수 N
    # 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages
    
    
    # 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return
    answer = []
    
    start = 1
    over_count = 0
    target_count = 0
    
    my_answer = { }
    
    while(1):
        if start > N:
            break
        
        for i in range(len(stages)):
            if stages[i] == start: # 스테이지를 진행중인 사람 
                target_count += 1
                over_count += 1 
            elif stages[i] > start: # 스테이지를 클리어 한 사람 
                over_count += 1
            
        if target_count == 0:
            my_answer[start] = 0
        else:
            my_answer[start] = target_count / over_count    
        #print(target_count, "/", over_count)
        
        #print(my_answer)
        
        over_count = 0
        target_count = 0
        start += 1
    
    result = sorted(my_answer, key=lambda x : my_answer[x], reverse=True)
    return result

시간/공간 복잡도

문제에서 200,000의 입력이 주어지므로써 이를 무난하게 통과하기 위해서는 NlogN의 시간복잡도가 나오는 알고리즘을 짜야 했다. 

최적화 및 개선

개선을 위해서 코드짤 때 관점과 구현 방법을 바꿔야했다. 

기존에는 사용자가 stages 배열을 를 구성하는 사용자들에 대해서 start 변수를 통해 순차적으로 스테이지를 증가시키고 stages 요소들을 돌면서 이를 넘겼느냐를 체크했다.

스테이지의 개수를 기준으로 도전하는 사용자와 실패한 사용자를  각각 반복문을 통해 메기면 굳이 이중 반복문을 사용하지 않아도됐다. 

어려웠던 점

한번 코드를 작성하려고 생각한 구현 관점을 수정하기가 어려웠다. 

이런 부분은 시간이 엄청 오래걸린다. 

그리고 확실히 시간복잡도를 미리 고려하고 코드의 효율성을 잘 확인하고 구현할 생각을 해야할 것 같다. 

문제를 어떻게 풀어야 겠다는 생각과 구현을 어떻게 해야하겠다는 생각은 다른 생각이고, 구현에 대한 생각을 굳이 하지 않았는데, 앞으로 문제 통과를 위해서 제대로 해야겠다는 생각이 든다.