문제 : 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/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))

▶ 문제 : 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://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://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=' ')

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

▶ 코드(딕셔너리)

# 이진탐색으로 풀이 불가
# 딕셔너리로 풀이

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

dic1 = {}
dic2 = {}
for i in range(n):
    name = input()
    dic1[i+1] = name # i=1번째 부터 시작~
    dic2[name] = i+1

for _ in range(m):
    word = input()

    if word.isdigit(): # 입력된 str이 숫자형태면
        word = int(word)
        print(dic1[word])
    else:
        print(dic2[word])

▶ 이진탐색으로 어떻게 풀이..?

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

▶ 코드

import sys

# arr배열의 원소가 숫자일때만 가능 
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
    
if __name__ == "__main__":
        N = int(sys.stdin.readline())
        A = list(map(int, sys.stdin.readline().split()))
        M = int(sys.stdin.readline())
        B = list(map(int, sys.stdin.readline().split()))

        A = sorted(A) # 매개변수로 들어갈 배열이 미리 정렬 되어있어야됨 

        for b in B:
            if BinarySearch(A, b, 0, N-1): # 배열, 찾으려는 원소, start, end
                print(1)
            else:
                print(0)

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

▶ (참조)위상 정렬 : https://blog.naver.com/ndb796/221236874984

▶ (참조)deque 사용법 : https://dongdongfather.tistory.com/72

▶ 코드

# 위상 정렬 - 사이클이 없어야 가능하다.
# 단계1) 진입차수가 0인 정점들을 큐에 삽입한다.
# 단계2) 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
# 단계3) 간선 제거 이후에 진입차수가 0 이 된 정점을 큐에 삽입한다.
# 큐가 빌 때까지 단계2~3을 반복한다.
# 모든 원소를 방문하기전에 큐가 빈다면 사이클이 존재하는것이다.

from collections import deque
import sys

n, m = map(int, sys.stdin.readline().split())

dq = deque()
indegree = [0]*(n+1) # 진입차수 (노드 : 1~N)
tree = [[] for i in range(n+1)] # 트리 구조 (노드 : 1~N)
result = []

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    tree[a].append(b)
    indegree[b] += 1
#print('tree=', tree)
#print('indegree=', indegree)

# 단계1
for i in range(1,n+1):
    if indegree[i] == 0:
        dq.appendleft(i)
#print('dq=', dq)

# 큐가 빌 때까지 단계2 ~ 3 을 반복 
while dq:
    a = dq.pop() # 단계2
    result.append(a)
    for b in tree[a]:
        indegree[b] -= 1
        if indegree[b] == 0: # 단계3
            dq.appendleft(b)
#print('result=', result)

for a in result:
    print(a, end=' ')
        

▶ 코드

# [ 1, 1, 2, 3, 5, 8, 13 ... ]
n = int(input())

memo = [0]*91

def bnr(n):
    if n==1:
        return 1
    if n==2:
        return 1
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = bnr(n-1)+bnr(n-2)
        return memo[n]

print(bnr(n))

▶ 코드

n = int(input())
p = []

for i in range(n):
    p.append(list(map(int, input().split())))

for i in range(1, len(p)):
    p[i][0] += min(p[i-1][1], p[i-1][2])
    p[i][1] += min(p[i-1][0], p[i-1][2])
    p[i][2] += min(p[i-1][0], p[i-1][1])

print(min(p[-1][0], p[-1][1], p[-1][2]))


''' 메모리 초과됐던 코드 '''
'''
N = int(input())

temp = []
prev = []
for i in range(N):
    if i == 0:
        temp = list(map(int, input().split())) # [26, 40, 88]
    else:
        temp2 = []
        input_num = list(map(int, input().split())) # [49, 60, 57]
        

        if i == 1:
            for j in range(3):
                for k in range(3):
                    if j != k:
                        temp2.append( [temp[j], input_num[k]] ) 
            temp = temp2
            
        else:
            max_value = 0
            for j in range(len(temp)): # 0~5
                index = prev.index(temp[j][1])
                #print('index = ', index)
                
                for k in range(3):
                    if k != index:
                        temp2.append( [ sum(temp[j]), input_num[k] ] )
            temp = temp2

        prev = input_num
        
    print(i, temp)
    print()


for i in range(len(temp)):
    temp[i] = sum(temp[i])

print(min(temp))

'''

▶ 코드

# 1, 2, 3, 5, 8, 13, 21, 34, 55 ...

N = int(input())

memo = [0]*1001

def fib(N):
    if N == 1:
        return 1
    if N == 2:
        return 2
    if memo[N] != 0:
        return memo[N]
    else:
        memo[N] = fib(N-1) + fib(N-2)
        return memo[N]

print( fib(N) % 10007 )

▶ 코드

# N을 만드는 방법 = [1개, 2개, 4개, 7개, 13개...]
# 7은 4+2+1
# 13은 7+4+2

T = int(input())

memo = [0]*11

def onetwothree(N): # N = 1~10
    if N == 1:
        return 1
    if N == 2:
        return 2
    if N == 3:
        return 4
    
    if memo[N] != 0:
        return memo[N]
    else:
        memo[N] = onetwothree(N-1)+onetwothree(N-2)+onetwothree(N-3)
        return memo[N]

for _ in range(T):
    N = int(input())
    print( onetwothree(N) )