바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

이분탐색의 사용 조건: 리스트에 원소가 이미 '잘 정렬되어 있을 때'

• 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.
• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정.

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search

# 재귀 함수로 구현한 이진 탐색
def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2

    # 원하는 값 찾은 경우 인덱스 반환
    if array[mid] == target:
        return mid
    # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
    # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
    else:
        return binary_search(array, target, mid + 1, end)

# 반복문으로 구현한 이진 탐색
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 원하는 값 찾은 경우 인덱스 반환
        if array[mid] == target:
            return mid
        # 원하는 값이 중간점의 값보다 작은 경우 왼쪽 부분(절반의 왼쪽 부분) 확인
        elif array[mid] > target:
            end = mid - 1
        # 원하는 값이 중간점의 값보다 큰 경우 오른쪽 부분(절반의 오른쪽 부분) 확인
        else:
            start = mid + 1

    return None

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

문제 개요

<Input>

Places: ‘자리에 앉아있는 응시자들의 정보와 대기실 구조’를 대기실별로 담은 2차원 문자열 배열.

*대기실은 5개이며, 각 대기실은 5x5 크기

*P(응시자가 앉아있는 자리),O(빈 테이블),X(파티션)로 이루어진 문자열

*Rule

1. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
2. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.

예: [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]]

<Output>

각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아.

예: [1, 0, 1, 1, 1]

내 코드

못생긴 코드ㅡ... 코드가 왜 이렇게 길지? ^__^

ㅎㅎ

모범코드 보면서 공부해야겠다..

from collections import deque
def solution(places):
    
    answer = [1 for _ in range(5)]

    next_i, next_j = [-1, 0, 0, 1], [0, -1, 1, 0]
    doub_i, doub_j = [-2, 0, 0, 2], [0, -2, 2, 0]
    cross_i, cross_j = [-1, -1, 1, 1], [-1, 1, -1, 1]

    cnt = -1
      
    for place in places:
        cnt += 1
        place = list(map(list, place))
        p_lst = deque() #각 대기실에서 P가 있는 좌표 리스트
        for i, row in enumerate(place):
            for j, col in enumerate(row):
                if place[i][j] == 'P':
                    p_lst.append((i,j))
                    
        loopbreak = False
        while p_lst and (loopbreak == False):
            (i,j) = p_lst.popleft() #현재 중심이 되는 좌표 (i,j)
            for k in range(4): #위반 케이스 1
                ci = i + next_i[k]
                cj = j + next_j[k]
                
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    answer[cnt] = 0
                    loopbreak = True
                    break
                
            if loopbreak == True: break
            for k in range(4): #위반 케이스 2
                ci = i + doub_i[k]
                cj = j + doub_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if place[i + next_i[k]][j + next_j[k]] == "O":
                        answer[cnt] = 0
                        loopbreak = True
                        break
            if loopbreak == True: break
            for k in range(4): #위반 케이스 3
                ci = i + cross_i[k]
                cj = j + cross_j[k]
                if ci <0 or ci>4 or cj<0 or cj>4:
                    continue
                if place[ci][cj] == 'P':
                    if k == 0:
                        if place[i-1][j]=='X' and place[i][j-1]=='X': continue   
                    elif k == 1:
                        if place[i-1][j]=='X' and place[i][j+1]=='X': continue  
                    elif k == 2:
                        if place[i][j-1]=='X' and place[i+1][j]=='X': continue
                    elif k == 3:
                        if place[i][j+1]=='X' and place[i+1][j]=='X': continue
                    
                    answer[cnt] = 0
                    loopbreak = True
                    break

    return(answer)

• 테케 3, 8, 31번 오답의 반례 : 'POP'가 포함된 경우 '0'을 반환해야 한다
• answer의 default 원소로 1 채워놓고, 위반하는 경우=>  0으로 바꿈 & 다음 place로 바로 이동(기존 반복문 break)
• visited 리스트 이용해서 좀 더 효율적으로 구현했었는데 => 딱히 효과가 없다 ^__^ BFS 개념에 집착하지 말자,,

• 이중 반복문 빠져나오는 법: loopbreak과 같은 변수 사용,,
• 반복문 continue 개념

https://velog.io/@banana/break-continue%EB%A1%9C-%EB%B0%98%EB%B3%B5%EB%AC%B8-%EC%A0%9C%EC%96%B4%ED%95%98%EA%B8%B0

• 상하좌우 살피는 예쁜 코드 [-1,0,0,1] 등 사용해서 짰는데 (왜 전체 코드가 이리 장황할까?)

그래도 아래 코드는 유용하게 사용하쟈~

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

for k in range(4):
            cx = i + dx[k]
            cy = j + dy[k]
            if cx < 0 or cx >= N or cy < 0 or cy >= M:
                continue
            if arr[cx][cy] != 1:
                graph[i*M+j].append(cx*M+cy)

공부한 자료

https://daebaq27.tistory.com/82

https://veggie-garden.tistory.com/42

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

풀이 코드

from collections import deque

def solution(tickets):
    # 주어진 항공권은 모두 사용
    # 주어진 공항수 꽤 많음
    tickets.sort()
    dic = {}
    for tic in tickets:
        if tuple(tic) not in dic.keys():
            dic[tuple(tic)] = 1
        else:
            dic[tuple(tic)] +=1

    for root in [x for x in tickets if x[0]=="ICN"]:
        deq = deque()
        deq.append([root]) #dic, visited list
        while deq:
            visited = deq.popleft() #현재 다루는 dic과 그것이 사용된 횟수
            for tic in tickets:
                if (visited[-1][1] == tic[0]) and (visited.count(tic) < dic[tuple(tic)]):
                    if len(visited)+1 == len(tickets):
                        mod = [x[1] for x in visited+[tic]]
                        mod.insert(0, visited[0][0])
                        # print(mod)
                        return mod
                    else:
                        deq.append(visited+[tic])


    return #방문하는 공항 경로 #알파벳 순서가 앞서는 경로

• 알파벳 정렬은, 처음부터 input 리스트 'tickets'을 sort시키고 시작하면 해결된다.
• DFS의 특이한 버전이었다. 
  
  - input에 동일한 티켓이 여러 장 포함될 가능성이 있다. 따라서 다음 탐색 노드를 추가할 때 visited 존재 여부로 결정해서는 안 된다. (이미 방문하여 visited에 존재하지만, 탐색 가능한 것이 여전히 남아 있을 수 있다)
     ✂︎ 미리 counter dictionary를 생성하고, visited가 포함하는 개수와 비교해야 한다:
          visited.count(tic) < dic[tuple(tic)]
  
  - 지금까지 경로 데이터를 모두 가지고 있어야 한다
     ✂︎ deque의 원소 자체를 visited 리스트로 저장
     ✂︎ deep 하게 for문 돌 때, 기존 visited에 현재 탐색 원소를 append하여 기존 visited의 몸뚱아리를 키우는 것이 아니다.
         별도의 리스트(visited + [tic])로 만들어 그것을 deque에 append한다.
         (효율성 괜찮나..? 싶었으나 더 간단한 방법이 떠오르지 않음)
  
  
• 리스트를 원소로 가지는 리스트의 처리는 Unhashable error에 주의해야 한다. 나는 dictionary 생성 및 count를 위해 각 리스트 원소를 tuple로 변환하였다.
  https://daewonyoon.tistory.com/363 

• 트리 형태로 시각화한 후 수도코드 짜는 게 훨씬 수월할 듯.

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

문제 개요

비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램.

입력한 키: 알파벳 대문자, 소문자, 숫자, 백스페이스, 화살표

'-' : 백스페이스 (커서 바로 앞에 있는 글자를 지움(글자가 있으면))

‘<‘: 커서를 왼쪽으로 1만큼 움직임 (움직일 수 있다면)

‘>’: 커서를 오른쪽으로 1만큼 움직임 (움직일 수 있다면)

나머지 문자는 비밀번호의 일부. (나중에 백스페이스를 통해서 지울 수 있음)

Input

첫째 줄에 테스트 케이스의 개수

각 테스트 케이스는 한줄로 & 입력한 순서대로 길이가 L인 문자열 (input이 매우 큼 => 효율성이 중요함)

<<BP<A>>Cd-

Output

비밀번호를 출력한다. (비밀번호의 길이는 항상 0보다 크다.)

문제 풀이

class Node:
    def __init__(self, x):
        self.item = x
        self.before = None
        self.next = None

class LinkedList:
    def __init__(self) -> None:
        dummy = Node(-1)
        self.head = dummy
        self.cursor = self.head
    
    def append(self, x):
        new = Node(x)
        new.next = self.cursor.next
        new.before = self.cursor # type: ignore
        if self.cursor.next != None:
            self.cursor.next.before = new
        self.cursor.next = new # type: ignore
        self.cursor = new
        
    def delete(self):
        if self.cursor == self.head: return
        self.cursor.before.next = self.cursor.next
        if self.cursor.next != None:
            self.cursor.next.before = self.cursor.before
        self.cursor = self.cursor.before
    
    def left(self):
        if self.cursor == self.head: return
        self.cursor = self.cursor.before
        
    def right(self):
        if self.cursor.next == None: return
        self.cursor = self.cursor.next
        
    
L = int(input())
inputs = []
for _ in range(L):
    inputs.append(input())

for cmd in inputs:
    link_lst = LinkedList()
    answer = []
    for i in range(len(cmd)):
        if cmd[i] == "-":
            link_lst.delete()
        elif cmd[i] == "<":
            link_lst.left()
        elif cmd[i] == ">":
            link_lst.right()
        else:
            link_lst.append(cmd[i])

    crt = link_lst.head
    while crt.next != None:
        crt = crt.next
        answer.append(crt.item)
    
    print(''.join(answer))

=> cursor의 위치를 정확히 정의해야 함!

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

양방향 Linked List에 구현 로직이 동일한 것 같은데

왜 내 코드는 효율성 테스트를 통과하지 못하는 거지..?

비교해서 효율성 개선 방법 찾아내야겠다 ㅠㅠ

효율성 통과 코드

class Node:
    def __init__(self,data=None,prev=None,next=None):
        self.prev= prev
        self.data= data
        self.next= next
class DoubleLinkedList:
    def __init__(self,data=None):
        # for easy calculate at end set two dummy head_dummy and tail_dummy
        self.head = Node()
        self.tail = Node()
        # link two dummy
        self.head.next = self.tail
        self.tail.prev = self.head
        self.current_ptr = self.head
        self.delete_array = []


    def init_insert(self,data):
        new_node = Node(data)
        # get tail-1 node
        node = self.tail.prev
        node.next = new_node
        
        new_node.prev = node
        new_node.next = self.tail
        
        self.tail.prev = new_node
    
    def set_current_ptr(self, num):
        for i in range(num+1):
            self.current_ptr = self.current_ptr.next

    
    def c_instruction(self):
        self.before_ptr = self.current_ptr
        self.current_ptr = self.current_ptr.next
        if(self.current_ptr == self.tail):
            self.current_ptr = self.current_ptr.prev
            self.current_ptr = self.current_ptr.prev
        # delete!!
        self.delete_array.append(self.before_ptr)
        # modify linked list
        self.before_ptr.prev.next = self.before_ptr.next
        self.before_ptr.next.prev = self.before_ptr.prev
        
    def u_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.prev
    
    def d_instruction(self, num):
        for i in range(num):
            self.current_ptr = self.current_ptr.next
    
    def z_instruction(self):
        node_to_z = self.delete_array.pop(-1)
        node_to_z.prev.next = node_to_z
        node_to_z.next.prev = node_to_z
    def return_del_array(self):
        to_return = []
        for i in range(len(self.delete_array)):
            to_return.append(self.delete_array[i].data)
        return to_return

            
def solution(n,k,cmd):
    answer_string = ["O"]*n
    my_list = DoubleLinkedList()
    for i in list(range(n)):
        my_list.init_insert(i)
    my_list.set_current_ptr(k)
    for instruction in cmd: 
        if instruction[0] == "U":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.u_instruction(move_cnt)
        elif instruction[0] == "D":
            instruction_list = instruction.split()
            move_cnt = int(instruction_list[1])
            my_list.d_instruction(move_cnt)
        elif instruction[0] == "C":
            my_list.c_instruction()
        elif instruction[0] == "Z":
            my_list.z_instruction()
    deleted_element = my_list.return_del_array()
    for element in deleted_element:
        answer_string[element] = "X"
    return ''.join(answer_string)

효율성 통과하지 못하는 코드

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = [i for i in range(n)] #비효율의 원인
    link_lst = LinkedList()
    
    for i in answer:
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    final = ["O" if x not in del_lst else "X" for x in answer] #비효율의 가장 큰 원인: O(N)
    final = ''.join(final)
    # print(final)
    return final

• 양방향 LinkedList까지 로직 참 좋았다 ! 
• input의 크기가 무지막지하게 크다는 사실을 기억해야 한다
• input 처리에 대한 단순한 코드때문에 => 눈덩이처럼 커진 비효율이,,,!!!!!!!
• input의 value는 사실 중요하지 않다. 서로가 '중복되지 않음'만 확인되면 된다.
  나는 처음에 각 Node를 생성하고 해당 노드의 value(Node.item)가 저장된 answer 리스트를 따로 생성했었다.
  그러나, integer로 채워진 answer 리스트를 임의로 생성할 필요가 없었다. 생성하면 무조건 비효율 문제가 발생하게 된다
  => answer 생성: O(N) + final 생성: O(N) = 2*O(N)
  이미 각 Node들의 item 값은 서로 다르기때문에 '중복되지 않음'의 속성이 반영되어 있다.
• 초반에 append한 각 Node의 value 값과 idx 값이 동일함을 이용하여 answer 리스트의 원소로 미리 "O"를 넣어둔다
• 마지막에 del_lst의 item값을 answer의 idx값으로 이용하여 answer 리스트에서 해당 idx의 값을 "X"로 바꾸어준다
  => final 리스트 따로 생성하지 않음! answer 리스트 내에서 변형.
  => O(N) + O(len(del_lst))
  => 이때 N보다 del_lst가 작으므로, N이 무지막지한 크기인 본 문제에서 효율성을 크게 높일 수 있다..!!

최종 효율성 통과 코드

class Node:
        def __init__(self, x):
            self.item = x
            self.before = None
            self.next = None

class LinkedList:
    def __init__(self):
        dummy = Node(-1)
        self.bins = [dummy]
        self.tail = dummy
        self.current = None

    def append(self, x):
        new = Node(x)
        self.tail.next = new
        new.before = self.tail
        self.tail = new
        return new
    
    def up(self, x):
        for _ in range(x):
            self.current = self.current.before
        
    def down(self, x):
        for _ in range(x):
            self.current = self.current.next
    
    def delete(self):
        self.bins.append(self.current)
        
        if self.current.next == None:
            self.current = self.current.before
            self.current.next = None

        else:
            self.current.before.next = self.current.next
            self.current.next.before = self.current.before
            self.current = self.current.next
        
        
    def restore(self):
        if self.bins:
            res_data = self.bins.pop()
            res_data.before.next = res_data
            if res_data.next != None:
                res_data.next.before = res_data
        
    
    def return_del(self):
        del_lst = [x.item for x in self.bins]
        return del_lst


def solution(n, k, cmd):
    answer = ["O" for _ in range(n)] #효율 개선
    link_lst = LinkedList()
    
    for i in range(len(answer)):
        if i == k:
            link_lst.current = link_lst.append(i)
        else:
            link_lst.append(i)

    for x in cmd:
        
        if x[0] == "U":
            link_lst.up(int(x[2:]))
        
        elif x[0] == "D":
            link_lst.down(int(x[2:]))
        
        elif x[0] == "C":
            link_lst.delete()
        
        else:
            link_lst.restore()
    
    del_lst = link_lst.return_del()
    for x in del_lst[1:]: #주의
        answer[x] = "X" #효율 개선
        
    answer = ''.join(answer)
    print(answer)
    return answer

너무 잘 정리된 LinkedList 개념

https://wayhome25.github.io/cs/2017/04/17/cs-19/

표 편집 솔루션에 대한 좋은 레퍼런스

https://latte-is-horse.tistory.com/329

https://life318.tistory.com/2

유용한 링크

https://blockdmask.tistory.com/443

https://blockdmask.tistory.com/445

부모클래스의 생성자를 상속받으려면 => 자식클래스의 생성자 __init__ 아래 줄에 super 사용해야 함.

반면, 부모클래스의 메소드를 상속받으려면, 자식클래스 괄호 안에 부모클래스 언급만 하고, super 할 것  없음.

만약 메소드를 변형하고자 한다면 그게 곧 '오버라이딩' 한다는 거임.그때 def 하면 됨.

이외 자식클래스에만 별도로 추가로 함수 정의하고자 한다면 def 하고.

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

문제

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.

(버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.)

Tip & 풀이 핵심

1. '시간제한 1초' & '첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다.'

• (시간제한이 1초이면) input 길이가 10,000이 넘어가면 O(N**2)의 알고리즘으로 절대 풀 수 없음!!!
  => Bubble sort, Insertion sort, Selection sort: O(N**2)
  => Merge sort: O(N* logN) / Quick sort
  => Counting sort

2. Merge sort에서 swap하는 과정이 있더라!

   => "어떻게 하면 Merge sort 로직에 result 구하는 코드 구현?"

모범 코드

모범 코드 보면서 효율적이고 정확하게 코드 짜는 방법을 많이 배웠다.

import sys
input = sys.stdin.readline
result = 0 #최종 결과값

N = int(input())
A = list(map(int, input().split()))
A.insert(0,0) # 0 index에 0을 추가 # index 처리 쉽게 하기 위함
tmp = [0] *(N+1) # A배열의 크기를 맞춤 # A를 바로 처리하기 부담스러우므로 복제

def merge_sort(s, e):
    global result
    if e-s < 1: return
        
    else:
        m = (e+s) // 2
        merge_sort(s, m)
        merge_sort(m+1, e)
        
        for i in range(s, e+1):
            tmp[i] = A[i]
        
        # two pointers
        k = s #현재 바꾸어야 하는 A의 index
        index1 = s
        index2 = m+1
        while index1 <= m and index2 <=e:
            if tmp[index1] > tmp[index2]:
                A[k] = tmp[index2] #swap
                result += (index2-k)
                k += 1
                index2 += 1
                # A[index2] = tmp[index1]
            
            else:
                A[k] = tmp[index1]
                k += 1
                index1 += 1
         
        while index1 <= m:
             A[k] = tmp[index1]
             k += 1
             index1 += 1
        
        while index2 <= e:
            A[k] = tmp[index2]
            k += 1
            index2 += 1
        

merge_sort(1, N) # 1번째 idx부터 N번째 idx까지 merge_sort 진행
print(result)

• global 이해 필수: https://lets-hci-la-ai-withme.tistory.com/68
• A.insert(0,0) : idx 처리 편하도록 0번째에 0value 추가
• tmp 생성: input 리스트(A) for문으로 복제 (value 값 저장하여 안전하게)
• 재귀식에서 base condition 처리, return만: if e-s<1: return
• 함수에서 return이 없을 수 있다. 단 위 경우, 전역변수인 result에 계속 값을 저장.
• 특히, Merge_sort에서 return 없이, 시작 idx(s)와 끝 idx(e)만을 입력 파라미터로 이용하여 처리 가능.
• k는 현재 처리해야 하는 A에서의 idx. 따로 지정.

내가 작성한 시간 초과 코드:

def merge_sort(inputs):
    
    if len(inputs) < 2:
        return inputs, 0
    
    else:
        mid = len(inputs)//2
        left = inputs[:mid]
        right = inputs[mid:]
        left_ , l_count  = merge_sort(left)
        right_ , r_count = merge_sort(right)
        
        merged, count = merge(left_, right_, l_count, r_count)

        return merged, count

def merge(left_, right_, l_count, r_count):
    merged = []
    count = (l_count + r_count)
    l_ptr = 0
    r_ptr = 0
    
    while l_ptr < len(left_) and r_ptr < len(right_):
        if left_[l_ptr] > right_[r_ptr]:
            # left에서 right_[r_ptr]보다 큰 원소 중 최소인 것의 idx 찾기
            s, mid, e = 0, 0, len(left_)-1

            while s <= e:
                mid = (s + e)//2
                if right_[r_ptr] == left_[mid]:
                    break
                
                elif right_[r_ptr] < left_[mid]:
                    e = mid -1
                else:
                    s = mid+1
                        
            if left_[mid] <= right_[r_ptr] < left_[e]:
                count += len(left_) - (mid+1)

            elif right_[r_ptr] < left_[s]:
                count += len(left_) - s

            elif mid > 0 and mid <= len(left_)-2:
                idx = mid+1
                while right_[r_ptr] >= left_[idx]:
                    idx += 1
                count += len(left_) - idx
            else:
                print(-1)
            
            merged.append(right_[r_ptr])
            r_ptr += 1
        else:
            merged.append(left_[l_ptr])
            l_ptr +=1
    
    while r_ptr < len(right_):
        merged.append(right_[r_ptr])
        r_ptr += 1
        
    while l_ptr < len(left_):
        merged.append(left_[l_ptr])
        l_ptr +=1
    
    return merged, count

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))
        print(merge_sort(inputs)[1])

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

Local variable: 특정 지역 범위에서만 영향을 주고 받을 수 있는 변수

(ex. 특정 함수 내에서 선언한 변수는 return되지 않는 한 함수 밖에서 사용될 수 없다)

#1

a = 1 #Global

def function():
	print(a) 
    # 함수 내에서 별도 변수를 선언하지 않았으므로, Global과 구분되는 Local이 없음
    # 함수 전체에 적용되는 Global 'a'가 적용됨
   
funtion()
print(a)

>> 1 \n 1

여기서 a는 Global variable이다. 

함수 내에서 별도 변수를 선언하지 않았으므로 Local variable은 없다.

함수에서 별도로 변수를 선언하지 않으면 a는 global variable이다.

#2

def function():
	a = 1
    print(a)
    
function()
print(a)

>> 1 \n error

여기서 Global variable은 없다.

함수 내에서만 변수를 선언했으므로 이것은 Local variable, 밖에서 가지고 오면 error 발생.

#3

a = 1 #Global

def function():
	a = 2 #Local
    print(a) #Local
   
function() #Local
print(a) #Global
 
 >> 2 \n 1

Python

global vs nonlocal

global

Global variable: 실행하는 파이썬 파일 전체 영역에서 사용 가능한 변수

함수 내에서 선언한 variable은 기본적으로 해당 함수에서만 사용 가능한 Local이지만, Local을 Global로 전환하는 역할.

때문에 함수 밖에서 선언된 건 global 쓸 필요 없음 (이미 Global인 상태)

#1

a = 1

def function():
	global a #함수 안에서 Local이 아닌 Global을 사용하기로 선언한다
    a = 2 #Global variable 'a'가 2가 된다
    print(a)

function() #Global
print(a) #Global

>> 2 \n 2

이때 global 선언문과 & a에 대한 식을 별도로 지정해야 한다.

#2

def function():
	global a #Local -> Global
    a = 10 #Global
    print(a) #Global

function() #Global
print(a) #Global

>> 10 \n 10

함수 밖에서 변수를 이미 선언하지 않더라도, 함수에서 처음 생성한 변수를 Global variable로 지정할 수 있다.

nonlocal

주로 함수 def 내의 또 다른 함수 def에서 사용됨

nonlocal: lower scope에서의 local variable을 upper scope에서의 local variable로 전환하는 역할

아래 예시에서, function2에서 선언한 a는 기본적으로 function2에서만 사용 가능한 local인데,

그것의 상위 함수인 function1에서 선언한 local으로 전환(연결)하겠다는 의미.

def function():
	a = 1 # function1의 Local
    def function2():
    	nonlocal a
        a = 2
        # nonlocal: function2의 Local -> function1의 Local
        #           function1의 a를 사용하겠어 (연결되겠어)
        # upper scope에서의 variable에 access
        # != Global (whole scope)
        
    function2()
    print(a)
    
>> 2

끝~

https://codingpractices.tistory.com/entry/Python-%EC%A0%84%EC%97%AD-%EB%B3%80%EC%88%98-%EC%A7%80%EC%97%AD-%EB%B3%80%EC%88%98-%EC%82%AC%EC%9A%A9%EB%B2%95-%EC%B4%9D-%EC%A0%95%EB%A6%AC-global-nonlocal

⬆️ 위 페이지에 잘 정리되어 있음 !!!

수많은 reportUnboundVariable error

이유를 탐색해보았다.

Reference

https://stackoverflow.com/questions/63388372/why-there-is-an-unbound-variable-error-warning-by-ide-in-this-simple-python-func

➡️ Because range(4) might be something empty (if you overwrite the built-in range), in which case the loop body will never run and a will not get assigned. Which is a problem when it's supposed to get returned.

➡️ Meaning of 'Unbound'

• A symbol that has not been given a value by assignment or in a function call is said to be “unbound.”
• An unbound variable is one that is not within the scope of a quantifier.

➡️ 해결: while문 선언 전 'mid'에 대한 default value를 할당해주었다.

Insertion Sort (삽입 정렬)

: human-like

1. 처음 주어지는 것: 빈 리스트 & 정렬해야 하는 카드들
2. 원리: index 순서대로 읽어가며 이미 정렬된 value들과 크기 비교하여 적절한 위치에 삽입함

• 새로운 빈 리스트를 하나 생성하는 것 대신(메모리 많이 잡아 먹음)
• ⇒ in-place기법 (주어진 표를 변형 + 원본이 훼손됨)

def insertion_sort(list):
	for i in range(i, len(list)):
    	key = list[i]
        j = i-1
        while j >=0 and key < list[j]:
        	list[j+1] = list[j]
        	j -= 1
        list[j+1] = key

1. sorted된 아이템들 중에 현재 Key와의 비교가 이루어질 위치 탐색: O(N) -> binary search 통해 O(logN)
2. shift : O(N)
3. 각 key에 대한 location 최종 삽입: O(1) (이미 1, 2단계로 location이 최종 선택된 상태)
4. 1~3의 단계를 N(=len(list)) 만큼 반복

=> Overall complexity: O(N^2)

관련 문제: 백준 11399 (ATM)

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

문제 개요

N명, i번 사람이 돈을 인출하는데 P_i분 소요

줄을 서는 순서에 따라 돈을 인출하는 데 각 사람이 인출하는 데 필요한 시간의 합이 달라짐

Input

줄을 서 있는 사람 수 N (ex. 5)

각 사람이 돈을 인출하는 데 걸리는 시간 P (ex. 3 1 4 3 2)

Output

각 사람이 돈을 인출하는 데 필요한 시간의 합의 최솟값 (ex. 32)

문제 풀이

Pseudo Code

: for문으로 key를 하나씩 지정

각 key의 위치를 while문 통해 탐색

그렇게 필요한 위치를 하나씩 탐색.

비록 시간 복잡도는 n^2

(3, 1, 4, 3, 2)

1 2 3 4 5 => (3, 1, 4, 3, 2) => 39분 (작은 값을 마냥 앞에 배치한다고 개선되지 않음)

2 5 1 4 3 => (1, 2, 3, 3, 4) => 32분

결론: value의 오름차순 소팅! (삽입정렬로 해결)

import sys

for t in range(2):
    if t == 0:
        n = int(sys.stdin.readline())
    else:
        inputs = list(map(int, sys.stdin.readline().split()))

for i in range(1, n):
    key = inputs[i]
    j = i-1
    while j>=0 and key < inputs[j]:
        inputs[j+1] = inputs[j] //swap
        inputs[j] = key //swap
        j -=1 //최종 목적지까지 계속 탐색

answer = [0]
for x in inputs:
    answer.append(x+answer[-1])

print(sum(answer))