수테크📱⌚️👀

문제😂

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 문을 다 돌았는데도 찾지못한다면 검색 실패