문제 : https://programmers.co.kr/learn/courses/30/lessons/62284

▶ FROM 절에서 사용되는 서브쿼리

FROM 절에서 사용되는 서브쿼리를 인라인 뷰(inline view)라고 한다.

FROM 절에는 테이블 명이 오도록 되어 있다.

그런데 서브쿼리가 FROM절에 사용되면 뷰(View)처럼 결과가 동적으로 생성된 테이블로 사용할 수 있다.

임시적인 뷰이기 때문에 데이터베이스에 저장되지는 않는다.

또한, 인라인 뷰로 동적으로 생성된 테이블이어서 인라인 뷰의 컬럼은 자유롭게 참조가 가능하다.

(출처: https://snowple.tistory.com/360)

▶ SQL 코드

CREATE DATABASE file;
USE file;

CREATE TABLE customer (
	user_id varchar(50),
    user_name varchar(50),
    membership int);
    
CREATE TABLE library (
	book_id int,
    book_name varchar(50),
    price int);
    
CREATE TABLE orderinfo (
	order_no int,
    buyer_id varchar(50),
    book_id int);
    
insert into customer values ('랄로123', '랄로', 2);
insert into customer values ('도파123', '도파', 1);
insert into customer values ('파카123', '파카', 3);
insert into customer values ('미야123', '미야', 4);
insert into customer values ('말구123', '말구', 1);

insert into library values (10, '메이플 1권', 30000);
insert into library values (11, '메이플 2권', 31000);
insert into library values (12, '메이플 3권', 32000);
insert into library values (13, '메이플 4권', 33000);

insert into orderinfo values (1, '랄로123', '12');
insert into orderinfo values (2, '도파123', '10');
insert into orderinfo values (3, '도파123', '11');
insert into orderinfo values (4, '파카123', '13');
insert into orderinfo values (5, '미야123', '12');
insert into orderinfo values (6, '말구123', '10');
insert into orderinfo values (7, '말구123', '13');

select*from customer;
delete from customer;
select*from library;
delete from library;
select*from orderinfo;
delete from orderinfo;

#문제: 멤버십등급이 1등급인 고객을 찾아 해당 고객의 아이디와 전체 기간에 대한 누적 구매액을 구하시오.
#ex) 
#고객 아이디   누적 구매액
# 도파123      100000

SELECT sum(price)
FROM library
WHERE book_id = '10';

SELECT user_id as '고객 아이디'
FROM customer
WHERE membership = 1;

#join으로 풀면 될듯...
#정답 쿼리문
SELECT c.user_name, sum(lb.price)
FROM customer c, orderinfo oi, library lb
WHERE c.user_id = oi.buyer_id 
	AND lb.book_id = oi.book_id
    AND c.membership = 1
GROUP BY c.user_id;

문제 : https://www.acmicpc.net/problem/11724

▶ 코드

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

parent = [0]*(n+1)
for i in range(1, n+1):
    parent[i] = i

# 최상위 부모를 찾습니다
def getParent(parent, x):
    if parent[x] == x:
        return x
    return getParent(parent, parent[x])

# 최상위 부모끼리 비교해서, 더 작은 값으로 바꿉니다. 
def unionParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)

    # 둘중, 더 작은 부모를 갖습니다. 
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
    
for _ in range(m):
    a, b = map(int, input().split())
    unionParent(parent, a, b) # 노드끼리 연결합니다.


result = [] # 최상위 부모노드들만 담을 배열
for a in parent:  # parent의 각 원소마다 최상위 부모노드를 구합니다.
    result.append(getParent(parent, a))
#print(result)

result = result[1:] # 0번째 노드는 필요없으니 잘라줍니다.

print(len(set(result)))

문제 : https://www.acmicpc.net/problem/7576

▶ 서로 다른 여러점에서, 동시에 물들여서 며칠이 걸리는지 알아내는 문제 

▶ 코드 ( 큐 ver. )

# 예외처리가 중요
# 예외1)) 다 물들였는데, 0 남아있는 경우 : -1 출력
# 예외2)) 애초에 0원소가 없는경우 : 0 출력 


from collections import deque

m,n = map(int, input().split()) # m: 가로, n: 세로
myMap = []
ripe = deque() # 익은 토마토 위치 

for i in range(n):
    row = list(map(int, input().split()))
    for j in range(m):
        if row[j] == 1:
            ripe.append([i,j])
    myMap.append(row)
#print(myMap)
#print(ripe) # deque([[0, 0], [3, 5]])

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

#visited = [[0]*m for _ in range(n)] # 필요 X

def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs():
    
    days = -1

    while ripe:
        days += 1
        for _ in range(len(ripe)):  # 현재 ripe의 원소 개수만큼만 반복 !! ★
            x, y = ripe.popleft()   # [0,0], [3,5] 까지만  

            tx = 0
            ty = 0
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]

                if isInGraph(tx, ty):
                    if myMap[tx][ty] == 0: # [tx, ty] not in ripe 조건 추가하면 시간초과
                        myMap[tx][ty] = 1
                        ripe.append([tx,ty])

    # 예외1)) 
    for row in myMap:
        if 0 in row:
            return -1
    return days
        

print( bfs() )
#print(myMap)

#참조: https://dojinkimm.github.io/problem_solving/2019/11/03/boj-7576-tomato.html

※ python3로 채점해야 메모리초과 X

※ 방문한 myMap의 원소를 0 -> 1로 바꿔주므로, visited를 통한 방문처리 필요 X

※ [tx, ty] not in ripe 조건 추가하면 시간초과

문제 : https://www.acmicpc.net/problem/2178

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 안해서 시간초과

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 추가. 정답

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1 and [tx,ty] not in dq:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

※ python3로 채점해야 메모리초과 X

※ 원배열이 모두 1이므로, visited를 통해 방문처리 해줘야 한다.

※ 큐에서 뺀 원소가 큐에 있는지 검사 추가 해줘야 시간초과 X 되는 문제 

문제 : https://www.acmicpc.net/problem/1012 

▶ 코드 ( 재귀 ver. )

import sys
sys.setrecursionlimit(10**8) # 10^8 까지 늘림.


T = int(input())

for _ in range(T):
    m, n, k = map(int, input().split())
    myMap = [[0]*m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        myMap[b][a] = 1

    #print(myMap)
    visited = [[0]*m for _ in range(n)]

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

    def isInGraph(r, l): # r: 세로, l: 가로
        if r < 0 or r >= n or l < 0 or l >= m:
            return False
        return True
        
    def bfs(r, l):
        visited[r][l] = 1

        tx = 0
        ty = 0
        for i in range(4):
            tx = r + dx[i]
            ty = l + dy[i]

            if isInGraph(tx, ty):
                if visited[tx][ty] == 0 and myMap[tx][ty] == myMap[r][l]:
                    bfs(tx, ty)

    ans = 0
    for i in range(n): # 세로길이
        for j in range(m): # 가로길이 
            if visited[i][j] == 0 and myMap[i][j] != 0:
                bfs(i, j)
                ans += 1
    print(ans)


# pypy로 제출하면 메모리초과. python3로 제출해야됨 

※ python3로 채점해야 메모리초과 X

문제 : https://www.acmicpc.net/problem/2667

▶ 코드( 재귀 ver. )

n = int(input())

m = []

for _ in range(n):
    num = str(input())
    num = list(map(int, num))
    m.append(num)
#print(m)

visited = [[0]*n for i in range(n)]

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

def isInGraph(r, l):
    if r < 0 or r >= n or l < 0 or l >= n:
        return False
    return True
    
def bfs(r, l):
    visited[r][l] = 1
    cnt = 1

    tx = 0
    ty = 0
    for i in range(4):
        tx = r + dx[i]
        ty = l + dy[i]

        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and m[tx][ty] == m[r][l]:
                cnt += bfs(tx, ty)
    return cnt
            
            
    
ans = []

for i in range(n):
    for j in range(n):
        if visited[i][j] == 0 and m[i][j] != 0:
            ans.append(bfs(i, j))
ans.sort()
print(len(ans))
for a in ans:
    print(a)

문제 : https://www.acmicpc.net/problem/2606

▶ 코드 ( 큐 ver. )

from collections import deque

n = int(input())
m = int(input())

s = [[0]*(n+1) for i in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    s[a][b] = 1
    s[b][a] = 1

def bfs(v):
    dq = deque([v])
    visited[v] = 1
    c = 0
    
    while(dq):
        v = dq.popleft()
        for i in range(1, n+1):
            if visited[i] == 0 and s[v][i] == 1:
                dq.append(i)
                visited[i] = 1
                c += 1
    print(c)


bfs(1)
    

문제 : https://www.acmicpc.net/problem/1260

▶ 코드 ( 큐 ver. )

from collections import deque

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

s = [[0]*(n+1) for i in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    s[a][b] = 1
    s[b][a] = 1



def dfs(v):
    print(v, end=' ')
    visited[v] = 1
    for i in range(1, n+1):
        if visited[i] == 0 and s[v][i] == 1:
            dfs(i)

def bfs(v):
    dq = deque([v])
    visited[v] = 1
    while(dq):
        v = dq.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if visited[i] == 0 and s[v][i] == 1:
                dq.append(i)
                visited[i] = 1
        



dfs(v)
print()
visited = [0]*(n+1) # visited 초기화 
bfs(v)

비슷한 문제 : https://www.acmicpc.net/problem/17472

▶ 코드

.

문제 : https://programmers.co.kr/learn/courses/30/lessons/62050

▶ 코드

.

문제: https://www.acmicpc.net/problem/1717

▶ 코드

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

def getParent(parent, x):
    if parent[x] == x: return x
    return getParent(parent, parent[x])
def unionParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)
    
    if x < y:
        parent[y] = x
    else:
        parent[x] = y
        
parent = [0]*(n+1)
for i in range(1,n+1):
    parent[i] = i
    
for _ in range(m):
    a, b, c = map(int, input().split())
    if a == 0:
        unionParent(parent, b, c)
    else:
        b = getParent(parent, b)
        c = getParent(parent, c)
        
        if b == c: print('YES')
        else: print('NO')
        

개념 : https://blog.naver.com/ndb796/221230967614

# 최상위 부모를 재귀로 찾습니다.
def getParent(parent, x):
    if parent[x] == x: return x
    return getParent(parent, parent[x])

# 각 부모 노드를 합칩니다.
def unionParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)

    # 더 작은 수를 부모로 갖습니다.
    if x < y:
        parent[y] = x
    else:
        parent[x] = y


# [확인]같은 부모 노드를 가지는지 확인합니다.
def findParent(parent, x, y):
    x = getParent(parent, x)
    y = getParent(parent, y)
    if x == y : return 1
    else: return 0



parent = [0] * 11
for i in range(1, 11):
    parent[i] = i

unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)
unionParent(parent, 1, 2)

print('1과 5는 연결되어 있나요?', findParent(parent, 1, 5))
unionParent(parent, 1, 5)
print('1과 5는 연결되어 있나요?', findParent(parent, 1, 5))

절대 arr = [[0]*n]*n으로 초기화 X

문제 : https://programmers.co.kr/learn/courses/30/lessons/49995

▶ 코드 (정확성 100, 시간초과)

def solution(cookie):
    n = len(cookie)

    s = [0]*(n+1)
    for i in range(n): # 중복연산을 피하기 위해 i인덱스 까지의 sum배열 생성: O(n)
        s[i+1] = s[i] + cookie[i]
    #print(s)

    max_value = 0
    for M in range(1, n): # 인덱스 1~ (n-1)
        for L in range(0, M):
            for R in range(M+1, n+1): # L연산하는 순간에, R도 같이 연산해줘야한다.
                left_part_sum = s[M] - s[L]
                right_part_sum = s[R] - s[M]

                # max_value와 같거나, 더 작다면 즉시 탈출 
                if left_part_sum <= max_value or right_part_sum <= max_value: 
                    continue
                    
                #print(M, left_part_sum, right_part_sum)

                if left_part_sum == right_part_sum:
                    max_value = left_part_sum

    #print(max_value)
    return max_value
    
solution([1]) # 0
solution([2,2]) # 2
solution([2,3]) # 0
solution([1,7,8]) # 8
solution([1,2,3,5]) # 5
solution([1,1,1,1,3,4,7]) # 7
solution([1,1,2,3]) # 3
solution([1,2,4,5]) # 0

▶ 문제 : https://www.acmicpc.net/problem/5052

▶ Trie란?

insert함수를 이용해 단어들을 삽입한뒤, 단어들의 알파벳끼리 연결해서 트리형태로 만든다.

1) 단어가 트리내에 존재하는지 확인해보거나(search함수)

2) 주어진 단어를 prefix로 가지는 단어의 배열을 리턴해준다(starts_with함수)

3) 시간복잡도는 O(m)이다.

class Node:
    def __init__(self, key,data=None):
        self.key = key     # 단어의 글자 하나를 담는곳
        self.data = data   # 사실상 마지막 글자인지 나타내주는 flag
                           # 마지막 글자의 경우에 단어 전체를 data필드에 저장하고,
                           # 아닌 경우는 null로 둔다.
        self.children = {} # dict

    # 즉, Jack의 경우 J, a, c, k 에서 마지막 글자인 K노드의 data필드에만
    # "Jack"이 들어가고, 그 외 노드의 data필드는 널(None)이다


    # trie구조를 예쁘게 출력해주는 함수 (http://cd4761.blogspot.com/2017/02/trie-1.html)
    def __str__(self, depth=0): 
        s = []
        for key in self.children:
            s.append('{}{} {}'.format(' ' * depth, key or '#', '\n' 
                                      + self.children[key].__str__(depth + 1)))

        return ''.join(s)
    
class Trie:
    def __init__(self):
        self.root = Node('') # key=None

    def __str__(self, depth=0):
        return self.root.__str__()
    
    # 트라이에 문자열을 삽입
    def insert(self, inputString): # print, python, pytorch
        curr_node = self.root # 루트부터 시작 

        for c in inputString: # p, y, t, h, o, n
            if c not in curr_node.children: # 알파벳이 자식에 존재하지 않으면 
                curr_node.children[c] = Node(c)
            curr_node = curr_node.children[c] # curr_node를 업데이트 

        # inputString의 마지막 글자 차례이면,
        # 노드의 data필드에 inputString문자열 전체를 저장한다.
        curr_node.data = inputString  


    # inputString이 트라이에 존재하는지 여부 반환
    def search(self, inputString):
        curr_node = self.root # 루트부터 시작

        for c in inputString:
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
            else:
                return False # 없으면 즉시 False반환 

        # inputString의 마지막 글자에 도달했을때,
        # curr_node에 data가 있다면 inputString이 트라이 안에 존재하는것!
        
        if curr_node.data != None:
            return True

    # 주어진 prefix로 시작하는 단어들을,
    # BFS로 트라이에서 찾아 리스트 형태로 반환
    def starts_with(self, prefix): # pr
        curr_node = self.root # 루트부터 시작 
        result = []
        subtrie = None

        # 트라이에서 prefix를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        
        for c in prefix: # prefix 알파벳 한글자씩 비교 ( p , r )
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
                subtrie = curr_node # subtrie로 설정
                print(prefix, '의 알파벳: [',c,']일때 <subtrie>')
                print(subtrie)
            else:
                return None # 없으면 즉시 함수 종료

        # BFS로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        
        # 여기 이해 X
        queue = list(subtrie.children.values()) # queue = [Node(i)]
        print('초기 큐 길이=', len(queue))
        while queue:
            curr = queue.pop()
            print('ㅡㅡㅡㅡㅡㅡㅡ')
            print('큐에서 꺼낸 <curr>')
            print(curr)
            if curr.data != None: # curr.data는 마지막노드에만 존재한다.(완전한 단어형태로 저장되어있다)
                result.append(curr.data) # curr.data = 완전한 단어
                print()
                print('>>>result=', result)
                print()
            queue += list(curr.children.values()) # queue = [Node(n)]

        return result


# 테스트 코드
trie = Trie()
trie.insert('print')
trie.insert('python')
trie.insert('pytorch')
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
if trie.search('python'):
    print('python단어 존재!')
if trie.search('java'):
    print('java단어 존재!')
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')

print('<전체 trie구조>')
print(trie)

print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
trie.starts_with('pr') # ['print']
print('ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ')
trie.starts_with('pyt') # ['pytorch', 'python']


# 출처 : https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0

▶ 5052 전화번호 목록 풀이

class Node:
    def __init__(self, key,data=None):
        self.key = key     # 단어의 글자 하나를 담는곳
        self.data = data   # 사실상 마지막 글자인지 나타내주는 flag
                           # 마지막 글자의 경우에 단어 전체를 data필드에 저장하고,
                           # 아닌 경우는 null로 둔다.
        self.children = {} # dict

    # 즉, Jack의 경우 J, a, c, k 에서 마지막 글자인 K노드의 data필드에만
    # "Jack"이 들어가고, 그 외 노드의 data필드는 널(None)이다

    # trie구조를 예쁘게 출력해주는 함수 (http://cd4761.blogspot.com/2017/02/trie-1.html)
    def __str__(self, depth=0): 
        s = []
        for key in self.children:
            s.append('{}{} {}'.format(' ' * depth, key or '#', '\n' 
                                      + self.children[key].__str__(depth + 1)))

        return ''.join(s)
    
    
class Trie:
    def __init__(self):
        self.root = Node('') # key=None

    def __str__(self, depth=0):
        return self.root.__str__()
    
    # 트라이에 문자열을 삽입
    def insert(self, inputString): # print, python, pytorch
        curr_node = self.root # 루트부터 시작 

        for c in inputString: # p, y, t, h, o, n
            if c not in curr_node.children: # 알파벳이 자식에 존재하지 않으면 
                curr_node.children[c] = Node(c)
            curr_node = curr_node.children[c] # curr_node를 업데이트 

        # inputString의 마지막 글자 차례이면,
        # 노드의 data필드에 inputString문자열 전체를 저장한다.
        curr_node.data = inputString  


    # inputString이 트라이에 존재하는지 여부 반환
    def search(self, inputString):
        curr_node = self.root # 루트부터 시작

        for c in inputString:
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
            else:
                return False # 없으면 즉시 False반환 

        # inputString의 마지막 글자에 도달했을때,
        # curr_node에 data가 있다면 inputString이 트라이 안에 존재하는것!
        
        if curr_node.data != None:
            return True

    # 주어진 prefix로 시작하는 단어들을,
    # BFS로 트라이에서 찾아 리스트 형태로 반환
    def starts_with(self, prefix): # pr
        curr_node = self.root # 루트부터 시작 
        result = []
        subtrie = None

        # 트라이에서 prefix를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        
        for c in prefix: # prefix 알파벳 한글자씩 비교 ( p , r )
            if c in curr_node.children: # 알파벳이 자식에 존재하면 
                curr_node = curr_node.children[c] # curr_node를 업데이트
                subtrie = curr_node # subtrie로 설정
                #print(prefix, '의 알파벳: [',c,']일때 <subtrie>')
                #print(subtrie)
            else:
                return None # 없으면 즉시 함수 종료

        # BFS로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        
        # 여기 이해 X
        queue = list(subtrie.children.values()) # queue = [Node(i)]
        #print('초기 큐 길이=', len(queue))
        while queue:
            curr = queue.pop()
            #print('ㅡㅡㅡㅡㅡㅡㅡ')
            #print('큐에서 꺼낸 <curr>')
            #print(curr)
            if curr.data != None: # curr.data는 마지막노드에만 존재한다.(완전한 단어형태로 저장되어있다)
                result.append(curr.data) # curr.data = 완전한 단어
                #print()
                #print('>>>result=', result)
                #print()
            queue += list(curr.children.values()) # queue = [Node(n)]

        return result



T = int(input())
for _ in range(T):

    trie = Trie() # Trie class 초기화  
    
    n = int(input())
    lst = []
    
    for _ in range(n):
        word = str(input())
        lst.append(word)
        trie.insert(word)
    #print(lst)
    #print(trie)

    flag = 0
    for a in lst:
        t = trie.starts_with(a)
        #print(t)
        if len(t)>0:
            flag = 1
            break
    if flag == 1:
        print('NO')
    else:
        print('YES')

▶ 문제 : https://programmers.co.kr/learn/courses/30/lessons/64062

▶ 이분탐색을 이용해서 풀이한다. 

▶ 정규표현식으로 "0이 연속된 개수" 구하면 시간초과 !

▶ 이분탐색 코드 (정답)

# 건널 수 없는 경우가 있으면 false -> 이때, mid값을 줄여줘야됨 
# 건널 수 없는 경우가 없으면 true  -> 이때, mid값을 키워줘야됨 
def isPossible(stones, k, mid):
    disappearedStones = 0
    
    for s in stones:
        if s - mid <= 0:
            disappearedStones += 1
            if disappearedStones == k: # disappearedStones이 연속해서 k개가 나오면, False
                return False 
        else:
            disappearedStones = 0
            
    return True
 
    
def solution(stones, k):
    answer = 0
    
    left = 1
    right = 200000000 # stones의 원소값은 1 ~ 200,000,000
    
    while left <= right:
        mid = (left + right) // 2
        print('[left, right, mid]=', left, right, mid)
        
        if isPossible(stones, k, mid):
            print('>[true]')
            left = mid + 1 # mid값을 키워야 되니까, 반갈죽에서 오른쪽 택하겠다 
        else:
            print('>[false]')
            answer = mid # false일때, mid값으로 answer를 업데이트 해나간다.
                         # mid값(=빼야할 숫자)이 결국, 다리를 건넌 사람수와 동일 !
                         # Why? 문제의 조건 : 한명 건널때마다 전체 1씩 감소시키는 조건
            right = mid - 1 # mid값을 줄여야 되니까, 반갈죽에서 왼쪽 택하겠다

    print(answer)
    return answer


solution([2, 4, 5, 3, 2, 1, 4, 2, 5, 1], 3)

(정답 참조 : https://hellominchan.tistory.com/262)

문제 : https://www.acmicpc.net/problem/10816

▶ 이분탐색으로 arr에 해당 숫자 있는지 구하고, 해당 숫자의 '개수' 구하는 문제 

▶ 이분탐색은 항상 arr이 정렬 되어있어야 한다.

▶ 시행착오 1

한번 찾은 값을 다시찾지 않기위해서, 10,000,001 과 같이 큰 숫자로 바꿔버리면, arr의 정렬된 형태가 깨져버린다. 

ex) [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10] 의 경우, '3'에 대한 이분탐색을 하면 두번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 왼쪽에 있다.

ex) [-1, -1, -1, 3, 3] 의 경우 '3'에 대한 이분탐색을 하면 첫번째 위치한 3이 먼저 출력된다.

다음 3은 현재 index의 오른쪽에 있다.

▶ 시행착오 2

한번 찾은 값을 다시 찾지 않기 위해서, 따로 표시하는 방법은 어떨까.

그러나 이러한 과정을 거치면 시간초과

표시한다해도, 그다음 이분탐색으로 넘어갈때 같은 값이 왼쪽에 있는지 오른쪽에 있는지 모른다.

▶ 풀이방법 1 : 배열 count 함수 + 딕셔너리 사용   → 시간초과 (오답)

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

dic = {}
for c in card:
    dic[c] = lst.count(c)
print(' '.join(str(dic[c]) for c in card))

▶ 풀이방법 2: 이분 탐색 할때 해당 값 찾은후, 배열에서 count + 딕셔너리 사용 

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(lst, n, low, high):
    if low > high: # 이분탐색 조건 
        return -1

    mid = (low + high) // 2

    if n < lst[mid]:
        return BinarySearch(lst, n, low, mid-1)
    elif n > lst[mid]:
        return BinarySearch(lst, n, mid+1, high)
    else:
        return lst[low:high+1].count(n)

dic = {}
for n in lst:
    low = 0
    high = len(lst)-1
    if n not in dic:
        dic[n] = BinarySearch(lst, n, low, high)
        
#print(dic)

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

            

▶ 풀이방법 3 : arr은 정렬되어있으므로, 이분 탐색으로 해당 값을 찾고, 양 옆에 같은 수 몇개 있는지 세기

+ 딕셔너리 사용

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))

def BinarySearch(arr, val, low, high):
    if low > high:
        return 0

    mid = (low + high) // 2

    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        i = 1
        j = 1
        c = 1
        while mid - i >= 0:
            if arr[mid] != arr[mid-i]:
                break
            else:
                c += 1
            i += 1
        while mid + j < len(arr):
            if arr[mid] != arr[mid+j]:
                break
            else:
                c += 1
            j += 1
        return c

dic = {}
for n in lst:
    if n not in dic:
        dic[n] = BinarySearch(lst, n, 0, len(lst)-1)
        
#print(dic)     
print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

→ 이분 탐색 함수에서 해당 값 찾고, while 문 안에서 같지 않은것 찾았을때 즉시 빠져나오는 break 해주지 않으면 시간초과 

▶ 풀이방법 4: 딕셔너리만 사용 

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


dic = {}

for n in lst:
    if n in dic: # 딕셔너리에 있으면
        dic[n] += 1
    else: # 딕셔너리에 없으면
        dic[n] = 1

print(' '.join(str(dic[c]) if c in dic else '0' for c in card))

▶ 풀이방법 5: collections 라이브러리의 Counter() 사용

from collections import Counter

N = int(input())
lst = sorted(list(map(int, input().split()))) # 정렬 
M = int(input())
card = list(map(int, input().split()))


counter = Counter(lst)

print(' '.join(str(counter[c]) if c in counter else '0' for c in card))

출처 : (https://chancoding.tistory.com/45)

출처 : https://zetawiki.com/wiki/%ED%8C%8C%EC%9D%B4%EC%8D%AC_join()

문제 : https://www.acmicpc.net/problem/1654

▶ 이분탐색 조건1 : while (low <= high): ...

▶ 이분탐색 조건2 : low와 high의 초기값을 문제의 조건에 맞게 잘 설정해주자.

▶ 코드

n, k = map(int, input().split()) # 문제의 조건: 항상 N<=K

lst = []
for _ in range(n):
    lst.append(int(input()))
    
low = 1 # 시작을 1로 해야됨 !! (0으로 해버리면 mid로 나누는 부분에서 Error될 수 있음)
high = max(lst)
ans = -1
    
while low<=high: # 이분탐색 조건 !!
    mid = (low + high) // 2
    #print(low, mid, high)

    sum_val = 0
    for a in lst:
        sum_val += a//mid
            
    if sum_val >= k: # k개 '이상' 이라면..(=문제의 조건)
        ans = mid  # mid값으로 ans를 업데이트 해나간다.
        low = mid+1
    else:
        high = mid-1

print(ans)

문제 : https://www.acmicpc.net/problem/10815

▶ 코드

# 숫자 배열에만 이분탐색 가능
def BinarySearch(arr, val, low, high):
    if low > high:
        return False

    mid = (low + high) // 2

    if val < arr[mid]:
        return BinarySearch(arr, val, low, mid-1)
    elif val > arr[mid]:
        return BinarySearch(arr, val, mid+1, high)
    else:
        return True

n = int(input())
lst = list(map(int, input().split()))
lst.sort() # 이분탐색 하기전에 반드시 arr 정렬 !
m = int(input())
card = list(map(int, input().split()))
ans = []
for number in card:
    if BinarySearch(lst, number, 0, len(lst)-1):
        ans.append(1)
    else:
        ans.append(0)
#print(ans)
for a in ans:
    print(a, end=' ')