수테크📱⌚️👀

문제 😵‍💫

수빈이는 동생과 숨바꼭질을 하고있다. 수빈이는 현재 점N에 있고 동생은 점 K에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다, 순간이동을 하는 경우에는 1초 후에 2 * X의 위치로 이동하게 된다

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력!

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력!

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.4

내 풀🦷

# 1697. 숨바꼭질
from collections import deque
def bfs(start, depth):
    visited = [0] * 100001
    q = deque()
    q.append((start, depth))
    visited[start] = 1
    while q:
        s, d = q.popleft()

        if s == K:
            return d

        for nxt_s in [s-1, s+1, s*2]:
            if 0 <= nxt_s <= 100000 and (not visited[nxt_s] or visited[nxt_s] > d+1):
                q.append((nxt_s, d+1))
                visited[nxt_s] = d+1

N, K = map(int, input().split())
visited = [0] * K
result = dfs(N, 0)
print(result)

 처음에 도대체가 어떻게 접근해야할지도 모르겠고 dp나 while문으로 풀어야겠다 싶었는데 알고보니 bfs 문제였다ㅜㅜ

시작점과 깊이를 넣어서 시작점이 끝점과 같아지면 return으로 깊이를 받아주면 최소값을 구할 수 있다!!

어려웠던 부분은 방문 했던 곳 또는 깊이가 더 깊은곳과 그전까지의 깊이에 해당하는 값이 같았을때는 배제해 주어야 한다는 것이었다... 다른 분들 코드를 보았을때는 이미 방문한곳을 continue로 넘겨서 간단히 해결해 주는것을 볼 수 있었다...어떻게 풀어야할지까지 고민한 문제는 오랜만이라 더욱 힘들었다 😂😂😂😂

유튜버 딩코딩씨 보고 정리해보는 순열과 조합...

재귀, 백트래킹, dfs... 등등 정말 많이 연관되어있어서 정리하면 좋을것 같아 올려봅니다...

##### permutation(순열)

'''
순열 : permutation(포함되어 있는 수가 같은 수여도 순서가 다르면 다른걸로 친다)
dfs 트리와 체크리스트 사용

3개의 공 중에 2개를 뽑는 경우(3P2)
사용한 경우 넣으면 안되므로 체크리스트 사용하는 것임....
깊이 + 1 한후 길이에 맞는 값을 리턴을 하고나면
다시 체크리스트에 빼줘서 다시 넣을 수 있도록 해준다..

1 2
1 3
2 1
2 3
3 1
3 2
6가지
'''

def dfs(L):
    # 종료 조건
    # 리스트의 길이가 찾아야 할 개수(r)가 된다면 종료
    if L == r:
        print(result)
    else:
        for i in range(len(n)):
            # 체크리스트에 해당하는 값이 없다면
            if checklist[i] == 0:
                # result 리스트에 값을 추가
                result[L] = n[i]
                # 체크리스트에 값이 생겼다고 표시해주기
                checklist[i] = 1
                # 다음 깊이로 이동
                dfs(L+1)
                # 다음 번에 다시 사용하기 위해서 빼준다고 그냥 생각하셈 ^^;;;
                checklist[i] = 0

n = [1, 2, 3]
r = 2
result = [0] * r
checklist = [0] * len(n)
dfs(0)

이해도 이해지만 어느정도 외울만큼은 외우라고 하심...

이해해야 외우지 싶다가도 이러다가 진도가 영 안나갈거 같아서 적당히 이해시켜서 외우는것이 좋을 듯...

'''
조합 : 같은 숫자가 포함되어 있으면 같은 걸로 인정....
순열보다 경우의 수가 훨씬 작음...
순열보다 더 간단...
한번 썼으면 다시 쓰지를 않으니까 체크리스트도 필요없음...
DFS 트리를 이용해서 푼다

3C2

1 2
1 3
2 3

3가지
'''
def dfs(L, BeginWith):
    # 종료 조건
    if L == r:
        print(*result)
    else:
        for i in range(BeginWith, len(n)): # 시작하는 값부터 끝까지
            result[L] = n[i] # 해당하는 값을 넣어주기
            dfs(L+1, i+1) # 다음 깉이 다음 숫자로 이동하여 전 값을 들어오지 못하도록


n = [1, 2, 3]
r = 2
result = [0] * r

dfs(0, 0) # level, begin(어디서 시작할지)

# 11651. 좌표 정렬하기2

N = int(input())
result = []
for _ in range(N):
    x, y = map(int, input().split())
    result.append([x, y])

# for k in result:
#     print(k[-1])

for i in range(N-1):
    if result[i][-1] > result[i+1][-1]:
        result[i], result[i+1] = result[i+1], result[i]
        # print(result)
for i in range(N-1):
    if result[i][-1] > result[i+1][-1]:
        result[i], result[i+1] = result[i+1], result[i]

for s in result:
    print(*s)

처음에는 앞에것부터 비교하면서 앞에값이 뒤에값보다 크면 바꿔주는 느낌으로 로직을 구성했는데... for문을 두번 돌리니까 테스트 케이스의 답은 나왔는데 아마 히든케이스들은 다 걸려서 페일을 받았다...

아마 다른 애들은 두번으로 안되겠지..

그래서 어떤 방법으로 하면 좋을까 다시 생각해보다가...

y값을 차례로 정렬하면 되니까 먼저 받아서 소트??

내 풀 🦷

# 11651. 좌표 정렬하기2
import sys
input = sys.stdin.readline
N = int(input())
result = []

# y 값의 오름차순으로 정렬 
for _ in range(N):
    x, y = map(int, input().split())
    result.append([y, x])

result.sort()
# print(result)

for y, x in result:
    print(x, y)

결과는 성공이었다!!!! 생각보다 너무 간단하게 해결 ㅋㅋㅋㅋㅋ

그러고 다른 사람들의 풀이를 봤는데 정말 많은 사람들이 람다를 많이 사용하셨다...

잘 몰라서 못 쓰기도 했어서 이번기회에 공부하기로 했다 ^^

참고하면 좋을 개념들 ✍️

- sorted()에서 key lambda 사용 (오름차순이 기본)

• 단순히 sorted만 사용한 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
b = sorted(a)  # a.sort()와 동일
print(b)

# [(0, 4), (1,  -1), (1, 2), (2, 2), (3, 3)]
# 사실 굳이 람다로 어렵게 안 쓰고... 거꾸로 받아서 정렬하는게 더 좋은듯 ^^^^^^^^

• key 인자에 함수를 넘겨준 경우

1. 첫번째 들어있는 값을 오름차순 정렬해준 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
c = sorted(a, key = lambda x : x[0])
print(c)

# [(0, 4), (1, -1), (1, 2), (2, 2), (3, 3)]
# 앞의 인자의 오름차순으로 정렬되는것을 볼 수 있다

  2. 두번째 들어있는 값을 오름차순 정렬해준 경우

a = [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]
d = sorted(a, key = lambda x : x[1])
print(d)

# [(1, -1), (1, 2), (2, 2), (3, 3), (0, 4)]
# 뒤의 인자의 오름차순으로 정렬되는것을 볼 수 있다

   3. 첫번째 들어있는 값은 오름차순, 두번째 들어있는 값은 내림차순 정렬해준 경우

# 내림차순은 앞에 -를 붙여주면 된다!!
e = sorted(a, key = lambda x = (x[0], -x[1]))
print(e)

# [(0, 4), (1, 2), (1, -1), (2, 2), (3, 3)]

# 11651. 좌표 정렬하기2
import sys
input = sys.stdin.readline
N = int(input())
result = []

# x값에 상관없이 y 값을 정렬 => y 값 정렬
for _ in range(N):
    x, y = map(int, input().split())
    result.append([x, y])

ans = sorted(result, key = lambda x : (x[1], x[0]))
for x, y in ans:
    print(x, y)

배운 것을 토대로 람다를 사용하여 다시 문제를 풀면 이러한 코드를 얻을 수 있다!!

다음 정렬 문제는 람다로 도전해봐야겠다 😂😂😂

오늘 친 시험 문제중에 bfs, dfs  문제 해결을 하지 못해서 복습 하려다가 시험 친 기념으로(?)😂😂😂

단계별 위에 안 푼거 중에 7단계 일반수학을 마무리하기로했다!!! 

대부분 브론즈고 규칙만 찾으면 해결 가능한 간단한 문제인데 분수찾기가 골머리가 조금 아팠다 ^________^

문제🤔

내 풀🦷

# 1193. 분수 찾기
N = int(input())

line = 0 # 대각선 갯수
idx = 0 # 마지막 인덱스 (1, 3, 6, 10...)
while idx < N:
    line += 1
    idx += line # 마지막 인덱스는 라인에 있는 분자의 갯수 만큼 늘어난다

result = []
# 라인 홀수일 떼
if line % 2:
    ja = idx - N + 1     # 분자
    mo = line - idx + N  # 분모
    result.append(ja)
    result.append('/')
    result.append(mo)
else:
    ja = line - idx + N
    mo = idx - N + 1
    result.append(ja)
    result.append('/')
    result.append(mo)
    
print(''.join(map(str, result)))

뭔가 느낌적인 느낌은 알겠는데 찾기 쉽지 않았지만 분수를 하나하나 적고 뜯어보면 규칙을 찾을 수 있었다!!  ㅜㅜㅜ

N만을 가지고 분자와 분모를 어떻게 적어야할지를 제일 고민을 많이 했던 부분인것 같다.....

ja = 분자 / mo = 분모 입니다 ㅋㅋㅋ

참고함면 좋을 개념들 ✍️

• 리스트를 다양한 방법으로 출력하기

result = [1, 2, 3, 4]
# 공백없이 출력
print(''.join(map(str, result)))   # 1234
# 공백있이 출력
print(' '.join(map(str, result)))  # 1 2 3 4
# , 쉼표로 연결하여 출력
print(', '.join(map(str, result))  # 1, 2, 3, 4
# 언패킹
print(*result)                     # 1 2 3 4

문제😂

bfs(V, E, R) {  # V : 정점 집합, E : 간선 집합, R : 시작 정점
    for each v ∈ V - {R}
        visited[v] <- NO;
    visited[R] <- YES;  # 시작 정점 R을 방문 했다고 표시한다.
    enqueue(Q, R);  # 큐 맨 뒤에 시작 정점 R을 추가한다.
    while (Q ≠ ∅) {
        u <- dequeue(Q);  # 큐 맨 앞쪽의 요소를 삭제한다.
        for each v ∈ E(u)  # E(u) : 정점 u의 인접 정점 집합.(정점 번호를 오름차순으로 방문한다)
            if (visited[v] = NO) then {
                visited[v] <- YES;  # 정점 v를 방문 했다고 표시한다.
                enqueue(Q, v);  # 큐 맨 뒤에 정점 v를 추가한다.
            }
    }
}

내 풀🦷

# 24444. 알고리즘 수업 - 너비 우선 탐색1
from collections import deque # 요거 안하고 그냥 stack으로 하면 에러 나요...
import sys  
input = sys.stdin.readline

def bfs(R, V): # V: 정점 개수, E 간선, R : 시작 정점
    global visited
    visited = [0] * (V+1)
    q = deque([R])   # deque = deque() => 비어있는 큐 만들기
    visited[R] = 1
    order = 1   # 몇번째인지 알기위해서 순서를 1로 초기화해주고
    while q:
        t = q.popleft() # pop(0)
        # num[t].sort()
        for i in num[t]:
            # for i in sorted(num[t]): #sorted를 쓸꺼면 이렇게!!!
            if visited[i] == 0:
                q.append(i)
                order += 1 # 찾을떄마다 순서를 1씩 더해준다
                visited[i] = order


N, M, R = map(int, input().split())
num = [[] for _ in range(N+1)]

for _ in range(M):
    v1, v2 = map(int, input().split())
    num[v1].append(v2)
    num[v2].append(v1)

for k in num:
    k.sort()

bfs(R, N)

for s in visited[1::]:
    print(s)

문제 풀면서 어려웠던 점...

1. 시간초과 => import collections import deque와 import sys로 해결!!

- deque와 stack과 다른 점들... 

• deque = deque() => 비어 있는 큐 만들어주기  (stack은 q = [])
• popleft() => 제일 첫 값 빼주기 (stack은 pop(0))

2. 오름차순으로 뽑아 입력받은것들을 오름차순으로 정렬 (나는 입력 받은 순 고대로 만들어서 계속 정답이 안 나왔다...)

• num[t].sort()
• for i in sorted(num[t])
• for k in num: k.sort() .... 등등 여러 방법이 있다(이차원 배열이라 쉽지않음..)

참고하면 좋을 개념들 ✍️

1) BFS(너비우선탐색)

: 그래프와 트리의 가까운 노드부터 탐색하는 알고리즘.. 큐의 자료구조를 이용

- 동작과정

• 탐색 시작 노드를 큐에 삽입하고 방문 처리
• 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 곳을 큐에 삽입하고 방문처리
• 큐가 없어질 때까지 반복!!

def bfs(s, V): # 시작 정점 s, 마지막 정점 V
    # visited 생성 => 이 순서 기억하기!!!!!
    visited = [0] * (V + 1)
    # 큐생성
    q = []  # 이 타이밍에 q = [s] 해도 됩니당
    # 시작점 인큐
    q.append(s)
    # 시작점 방문 표시
    visited[s] = 1
    while q: # 큐에 정점이 남아있으면 계속 진행... (front != rear 라고도 사용가능!! 같으면 빈거니까
        t = q.pop(0) # 디큐, 앞에서 뽑아야겟쥬
        print(t)    # 방문한 정점에서 할일
        # 인접한 정점 중 인큐되지 않은 정점 w가 있으면
        for w in adj_l[t]:
            if visited[w] == 0:
                # w를 인큐, 인큐 되었음을 표시
                q.append(w)
                # visited[w] = 1
                visited[w] = visited[t] + 1 #### 최소거리를 구할 때 좋아용 ###
    # print(visited[1:])

저희 시험이 import를 사용할 수 가 없어가지구...

문제 풀때 deque를 쓰지 않아 생소한데요... 데크 쓰는 법은 👇👇

from collections import deque

def bfs(start):
    global graph, visited
    
    queue = deque([start]) # 시작점을 큐에 넣어줍니다
    visited[start] = True  # 방문 표시를 해줍니다
    
    while queue: # 큐에 남아있는 값이 없을 떄까지 반복!!
        v = queue.popleft() # 큐의 첫번째 값을 빼옵니다
        print(v, end = '') # 어떤 경로로 방문했는지 적어줍니다
        
        for i in graph[v]:  # v에 인접한 곳을 돌면서
            if not visited[i]: # 방문하지 않았다면
                queue.append(i) # 큐에 넣어주고
                visited[i] = True # 방문 표시를 해줍니다

bfs(1) # 1은 그냥 시작점 예를 1로 든거..

문제😂

내 풀🦷

# 4875. 미로
# 출발지에서 목적지에 도착하는 경로가 존재하는지 확인

# 사방 탐색
dx = [0, 1, 0, -1] # 범위 제대로 확인
dy = [-1, 0, 1, 0]
def miro(i, j):
    global result # 결과값 전역변수로 설정해주기
    visited[i][j] = True # 방문한 곳 true로 바꿔주기
    for k in range(4): # 사방탐색 진행
        di = i + dx[k]
        dj = j + dy[k] # 하나하나 신경써서 적기
        if 0 <= di < N and 0 <= dj < N and not visited[di][dj]:

            # 0이라 갈수 있는데 아직 방문을 안했다면 새롭게 그 지점을 다시 방문해야 하니까 재귀
            if arr[di][dj] == 0:
                miro(di, dj) # 재귀랄^^;;;;;

            # 3 도착하면 성공
            elif arr[di][dj] == 3:
                result = 1 # 결과값 성공으로 바꾸기
                break


T = int(input())
for tc in range(1, T + 1):
    N = int(input()) # 미로의 크기
    arr = [list(map(int, input().strip())) for _ in range(N)]
    # 방문 검사
    visited = [[False for _ in range(N)] for _ in range(N)]
    result = 0 # 결과값 (일단 실패)

    for i in range(N-1, -1, -1):
        for j in range(N-1, -1, -1):
            if arr[i][j] == 2:
                miro(i, j) # 함수에 시작점 넣어주기

    print(f'#{tc} {result}')

내가 잘 못 풀었던 점...

1. 사방 탐색 범위 확인!!! : 잘못 적었드래요.. 꼭 확인하고 적기;;;

2. Runtime error : strip()을 사용해 주어야 한다고 그러는데...

    우리 눈에는 안 보이지만 \n 이 포함 되어 있을지도 모른다고하네요....

    그리고 input()은 알아서 공백을 제거해주지만

    sys를 사용할 떄는 그런 기능이 없어서sys.stdin.readline().strip() 같이 무조건 써줘야 한데요!! 😵‍💫

참고함면 좋을 개념들 ✍️

1) 탐색

: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

 ex) DFS, BFS

2) DFS(깊이 우선 탐색)

• 스택 자료구조에 기초한다..
• 실재로는 스택보다는 재귀 함수를 이용하여 간결하게(?) 구현할 수 있다
• 시간 복잡도 : O(N)

# dfs & 재귀 함수
def dfs(v): # v : 시작점
    global visited, graphs  # 함수 안에서 만들어준게 아니라 안정성을 위해 전역변수로 설정해주었다
    visited[v] = True
    
    for i in graphs[v]: # 인접해 있는 곳 중에 
        if not visited[i]: # 방문을 안했다면
            dfs(i)  # 그 곳을 탐색!!
        
        else:
            continue # 이미 방문한 곳 패스 # 이 부분 안 적어줘도 된다
            
graph = [] # 그래프를 표현하는 인접 리스트(인접 행렬 어려움 ㅜㅜ)
visited = [] # 각 노드가 방문된 정보를 표현하는 1 차원 리스트(true, flase/ 0,1로 구문)

dfs(0)

 => 경로가 있는지 확인할 떄는 dfs 를 사용하는 것이 더 좋다고 하네요..

문제 😂

Forth라는 컴퓨터 언어는 스택 연산을 기반으로 하고 있어 후위 표기법을 사용한다. 예를 들어 3+4는 다음과 같이 표기한다.
 

3 4 + .
 

Forth에서는 동작은 다음과 같다.
 

숫자는 스택에 넣는다.

연산자를 만나면 스택의 숫자 두 개를 꺼내 더하고 결과를 다시 스택에 넣는다.

‘.’은 스택에서 숫자를 꺼내 출력한다.

Forth 코드의 연산 결과를 출력하는 프로그램을 만드시오. 만약 형식이 잘못되어 연산이 불가능한 경우 ‘error’를 출력한다.
 

다음은 Forth 연산의 예이다.
 

[입력]
 

첫 줄에 테스트 케이스 개수 T가 주어진다.  1≤T≤50
 

다음 줄부터 테스트 케이스의 별로 정수와 연산자가 256자 이내의 연산코드가 주어진다. 피연산자와 연산자는 여백으로 구분되어 있으며, 코드는 ‘.’로 끝난다.

나눗셈의 경우 항상 나누어 떨어진다.

[출력]
 

#과 1번부터인 테스트케이스 번호, 빈칸에 이어 계산결과를 정수로 출력하거나 또는 ‘error’를 출력한다.

내 풀🦷

# 4874. Forth

# 입력받기
T = int(input())
for tc in range(1, T + 1):
    # 여기서 문자로 받아서 나중에 숫자로 따로 바꿔줘야 함
    susik = input().split()
    # 마지막에 점이 있어서 미리 지워줌
    susik.pop()
    # 연산을 담아줄 리스트 만들기
    num = []
    # 결과값 1로 초기화, 0이면 에러로 출력, 1이면 리스트의 마지막 값 출력
    result = 1

    # 수식을 도는 동안
    for i in range(len(susik)):
        # 수식이 피연산자면
        if susik[i] not in ['+','-','*','/']:
            # 수식에 그 숫자를 정수로 바꿔서 넣어준다
            num.append(int(susik[i]))

        # 수식이 연산자면
        else:
            # 숫자가 두개 이상 남아있어야 연산자를 처리해 주는데 아니면
            # 맞는 수식이 아니니까 틀렸으므로 결과값을 0으로 바꿔준다
            if len(num) < 2:
                result = 0
                break

            else: # 리스트의 길이가 2 이상이면 맞는 수식이므로 진행
                n1 = num.pop() # 두가지 숫자를 뽑는거는 모든 과정에서 진행되므로 미리 뽑아줌
                n2 = num.pop()
                new = 0

                if susik[i] == '*':
                    new = n2 * n1
                    num.append(new) # 연산 후 다시 리스트에 넣어준다
                    # num.append(n2*n1) # => 이런식으로 바로 처리하는게 더 좋은 듯
                elif susik[i] == '+':
                    new = n2 + n1
                    num.append(new)
                elif susik[i] == '-':
                    new = n2 - n1
                    num.append(new)
                elif susik[i] == '/':
                    new = n2 // n1 
                    ####### 이떼 몫 연산자로 안해주면 나중에 .0이 나오는 케이스가 발생한다!!####
                    num.append(new)

    # 리스트의 길이가 1이 아니면 연산자와 숫자가 남아있거나
    # 아니면 아예 없어지는 틀린 수식이다
    if len(num) != 1:
            result = 0

    if result:
        print(f'#{tc} {num[-1]}')
    else:
        print(f'#{tc} error')

#####

이 문제 풀면서 2가지를 잘못했는데....

- 숫자를 정수로 안 받았으면서 나중에 int로 값을 넣지 않은 것..

- 나누기 연산자를 사용하면 딱 정수로 나눠 떨어지는 것이 아닌 경우도 발생하므로 // 몫 연산자를 사용해주어야 한다..

참고함면 좋을 개념들 ✍️

중위 표기법(infix notation)

: 연산자를 피연산자의 가운데 표기하는 방법

  ex) A + B (우리가 평소에 사용하는 방법)

후위 표기법(postfix notation)

: 연산자를 피연산자 뒤에 표기하는 방법

 ex) AB + (컴퓨터가 사용하는 방법)

후위 표기법의 수식을 스택을 이용해서 계산하기

1.  피연산자를 만나면 스택 push
2. 연산자를 만나면 필요한 만큼의 피연산자를 스택에서 pop 하여 연산하고, 연산결과를 다시 스택에 push
3. 수식이 끝나면, 마지막으로 스택을 pop하여 출력!!!

5
4 1 5 2 3
5
1 3 7 9 5

1
1
0
0
1

틀린 내 풀🦷

# 1920. 수찾기
import sys
input = sys.stdin.readline

N = int(input())
arr = list(map(int, sys.stdin.readline().split()))

M = int(input())
arr_2 = list(map(int, sys.stdin.readline().split()))
result = []

for j in range(M):
    one = []
    for i in range(N):
        if arr[i] == arr_2[j]:
            one.append(1)
            break
        else:
            one.append(0)

    # print(one)
    cnt = 0
    for k in one:
        if k == 1:
            cnt += 1
    if cnt >= 1:
        result.append(1)
    else:
        result.append(0)

for k in result:
    print(k)

구직구직하게 짜기 달인이 되버린 나,,,,

단계별 풀이로 안들어가고 성공률로 들어가서 안 풀어져 있는거 풀어가지고

어떤 방식으로 풀어야하는지 힌트(이차원 배열이다, 정렬이다, 이진탐색이다 이런거)가 없어서 어카지 하다가

찾아야할 값이 주어진 arr_2 리스트를 돌라면서 arr을 돌리는 완전 탐색으로 찾아서 있으면 더해주면 되겠다..

싶었고 무슨일로 인덱스 아웃오브레인지도 안나고 한번에 성공했는디.... 했는데.... 제출했는데...

했는데 시간초과가 나버렸다 ㅋㅋ 혹시나 몰라서 import sys로도 바꿔봤는데 실패....ㅜㅜ

수정된 내 풀🦷

백준에서 풀다가 막히면 질문게시판 들어가서 종종 힌트를 얻는데

나처럼 구질구질하게 푸는 사람이 없었고 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

set을 사용하여 입력받아 시간을 적게 걸리게 하는 방법이나 이진 탐색을 사용하였다!!

그러고 보니 이진 탐색을 이용하면 되었는데 혼자서 브로노마스(무지성)으로 하고있었다....

그래서 먼저 해본 set() 으로 입력 받기 =>

N = int(input())
arr = set(map(int, input().split())) # 출력 시간을 줄이기 위해 set 받음

M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    if i in arr: print(1)
    else: print(0)

결과는 성공~~~~~

set을 자주 안 쓰다보니 어떤 부분에서 쓸지 몰랐는데

입력을 set으로 받아 사용한다는 점을 알게 되었다!!

이진탐색으로 풀은 내 풀🦷

또 다른 방법중에 하나인 바이너리 서치를 통한 방법도 많이 보여서 도전해 보았다~~

N = int(input())
arr = list(map(int, input().split()))
arr.sort() # 이진탐색은 정렬된 것들 탐색하는데 이 부분 기억을 못해서 무한 루프로 몇번 다녀왔다
M = int(input())
arr_2 = list(map(int, input().split()))

for i in arr_2:
    # 바이너리 서치 활용하기(이진탐색)
    result = False 
    start = 0 # 시작 인덱스
    end = N - 1 # 끝 인덱스

    while start <= end:
        mid = ((start + end) // 2) # 중간값의 위치에 해당하는 수와 목표 비교해 나감
        if i == arr[mid]: # 중간값과 목표값이 같다면
            result = True
            break
        elif i > arr[mid]:
            start = mid + 1
        else:
            end = mid - 1

    if result:
        print(1)
    else:
        print(0)

시험에도 나오기는 했지만 오랜만에 이진탐색을 사용해서 계속 틀린값이 나오고

무한루프로 잠시 먼나라이웃나라 다녀왔다....

중간값과 목표값을 비교하면서 시작점이 마지막점보다 넘어서면 종료되는 기저조건을 설정하였다!!!!

참고함면 좋을 개념들 ✍️

1) 이진 검색(Binary Search)

:  자료의 가온데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

 => 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행한다

- 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다(정렬이 아니라 뒤에 수가 앞에 수보다 커버리면 오바자나.. 찾을 수가 없음!!!!!! 주의!!!!!!!!1..)

- 검색 과정

1. 자료의 중앙에 있는 원소를 고른다
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다
3. 목표값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 크다면 자료의 오른쪽 반에 대해서 세로 검색을 수행
4. 찾고자 하는 값을 찾을 떄까지 1~3의 과정을 반복한다
5. 찾는다면 성공, 못 찾으면 실패

- 구현

• 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다 => while의 종료 조건을 잘 설정하기
• 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요

# 이진 검색 알고리즘
def binarySweach(a, N, key):
	start = 0  # 시작점 
    end = N -1  # 종료점
    while start <= end:
    	middle = (start + end) // 2 # 몫으로 하는 이유 : 나누기 연산자를 사용하면 .0으로 float되걸랑
        if a[middle] == key: # 검색 성공
        	 return true
        elif a[middle] > key:
        	 end = middle - 1
        else:
        	start = middle + 1
    return flase # while 문을 다 돌았는데도 찾지못한다면 검색 실패