일단 하나를 해보자

서버에서 두 개 이상의 응답을 보내려 하는 경우 나타나는 에러다. 

나는 아무리봐도 res. 응답이 중복되지 않았는데 뭐지 했더니

res.send().json 이렇게 있지도 않은 메서드로 응답했던 것~!

res.status(200).json() 으로 바꿔주었더니 해결되었다. 

이진탐색은 정렬된 배열에서 특정한 값을 찾는 알고리즘이다

배열의 중간값을  기준으로 값을 찾고 

찾고자하는 값과 중간값을 비교하고 탐색범위를 반으로 줄인다

탐색범위가 없을 때까지 반복한다

chatqpt에거 물어본 이진탐색 

def binary_search(arr, target):   #정렬, 찾고자 하는 값이 인수로 들어감
    left = 0  #arr의 맨왼쪽인덱스
    right = len(arr) - 1 #arr의 맨오른쪽인덱스

    while left <= right:  #비교했을 때 오른쪽이 작을때까지 반복 (즉 탐색할 배열이 없을때까지)
        mid = (left + right) // 2

        if arr[mid] == target: #가운데데 인덱스의 값이 찾고자하는 값이면 
            return mid   #가운데인덱스를 리턴
        elif arr[mid] < target: #찾고자하는 값보다 가운데 인덱스의 값이 작으면
            left = mid + 1  #맨왼쪽, 첫번째 인덱스가 중간값부터 시작됨 (시작점을 바꿔서 기존 정렬을 반으로나누는것 뜻)
        else:
            right = mid - 1 #맨오른쪽, 마지막 인덱스가 중간값부터 시작됨(시작점을 바꿔서 기존 정렬을 반으로나누는것 뜻

    return -1 #값을 못찾으면 -1 내보냄 너가 찾는 값없어~~

이진 탐색은 검색, 정렬, 최솟값/최댓값 찾기 등 다양한 문제에서 사용됩니다.
이진 탐색은 탐색할 배열이 정렬되어 있어야 한다는 조건이 있지만, 이 조건을 만족한다면 빠른 탐색을 수행할 수 있는 알고리즘입니다. 이진 탐색은 효율적인 탐색을 위해 항상 고려해야 할 알고리즘 중 하나입니다.

정렬은 주어진 데이터를 일정하게 재배열하는 것이다. 

데이터를 재배열하는 정렬 종류는 다양하다

1) 버블 정렬

비교해서 큰 데이터를 오른쪽으로 보내서 재배열하는 방법

전체 배열를 모두 조회해서 데이터를 비교한다. -> 반복 : 큰데이터에는 효율적이지 못한 알고리즘이다.

2) 선택 정렬

가장 작은 최솟값을 골라서 맨앞에 보내는 식으로 재배열한다. 

가장 작은 최솟값 고르려면 전체 배열을 모두 조회해야한다. -> 반복 : 마찬가지로 큰데이터에는 효율적이지 못한 알고리즘

이처럼 정렬 알고리즘의 성능을 평가하는데에는 주로 '시간복잡도' 개념이 쓰인다. 

시간복잡도란 알고리즘 수행시간이 입력한 값에 따라 얼마나 증가하는지를 나타내는 지표이다. 

3) 힙정렬

힙 - 더미, 데이터를 특정한 형태로 쌓아올리는 것을 의미. 

노드간의 관계를 나타내는 이진트리구조에서 힙 구조가 나타난다. 

기본 리스트를 힙정렬로 만들려면 일단 최대 혹은 최소값을 가지는 루트를 설정하고 

루트를 기준으로 값(노드)를 정렬한다. 

4) 삽입정렬

삽입정렬은 버블정렬과 비슷해보이지만 

모든 데이터를 조회하며 비교하는 버블정렬과 달리

이미 정렬된 부분과 정렬되지 않은 부분을 유지하며

정렬된 부분에는 요소를 삽입하여 배열하므로 버블 정렬보다 효율적인 정렬이다.

5) 퀵 정렬

기준을 세워 분할한다(보통 중간값을 기준으로 함).작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치한다.

분할하고 배열하고를 재귀적으로 반복 후 합쳐서 정렬.

6)병합 정렬

리스트를 반으로 나눈다. 리스트 크기가 1이하가 될때까지 반으로 나눈다.

나눈 작은 리스트를 정렬한다. 나눴던 리스트의 가장 작은 요소를 비교해서 

작은 순서대로 병합한다. 

입력크기와 상관없이 일정한 시간복잡도를 가진다. 

위에서 아래로 일방향, 계층구조인 트리와 다르게

그래프는 어떤 노드들과도 연결될 수 있다.

마치 지하철 노선도 처럼

다양한 그래프 종류들!

그래프는

연결점(노드)과 연결점 사이를 잇는 간선으로 이루어져 있다.

그래프는 표현하는 방법은

크게 3가지가 있다. 

1. 인접리스트 (adjacency list)

모든 노드에 연결된 노드들을 순서대로 기록한 리스트

연결된 노드만 기록한다. 

파이썬에서 딕셔너리를 써서 키 : 값으로 적어서 사용 많이 함. 

const graph = [[2,3],[1,3],[1,2,4],[3]]

2. 인접행렬 (adjacency matrix)

그래프에서 어느 연결점(노드)들이 변(간선)으로 연결되었는지 나타내는 정사각 행렬

가로 123456 세로 123456 노드

(가로,세로)
(1,1) 자기 자신은 연결할 수 없어서 0

(1,2) 연결되어서 1 임

무방향 그래프에서  인접행렬은 다음과 같이 대칭이다.

const graph = [

      [0, 1, 0, 0, 1, 0],     

   [1, 0, 1, 0, 1, 0],  

   [0, 1, 0, 1, 1, 0],  

 [0, 0, 1, 0, 1, 1],

 [1, 1, 0, 1, 0, 0],

 [0, 0, 0, 1, 0, 0]

]

3. 암시적 그래프

그래프의 정점과 간선을 직접적으로 표현하지 않고, 

필요한 상황에서 동적으로 그래프의 일부 또는 전체를 생성하거나 탐색하는 방식이다.

연결표시를 하지 않아도 주변이 연결되어있음을 암시적으로 알 수 있는 경우!

ex) 미로 찾기 문제

DFS(깊이우선탐색)  vs BFS(너비우선탐색)

DFS(깊이우선탐색)

노드의 간선을 타고 깊이를 우선적으로 탐색함

스택 또는 재귀함수로 구현

스택: 쌓아놓은 더미. 마지막으로 넣은 걸 먼저 꺼낼 수 있음.

(

왼쪽 살펴서 있으면 깊이 끝까지 탐색 후 오른쪽.

오른쪽 노드가 다시 첫번째 노드가 되어서 왼쪽 깊이 탐색 후 오른쪽.

반복되어 재귀함수로 구현 가능. )

BFS(너비우선탐색)

전체 너비, 행순으로 탐색함

큐로 구현

큐: 버스 앞에 줄선 사람. 먼저 선 사람이 버스 탈 수 있음.

코드는 차후에 정리해보겟음..

컴백함. 정리해보겠음

--------------------

chatgpt한테 물어봄

DFS(깊이우선탐색) 알고리즘 코드구현

def dfs(graph, start, visited): #인자에 그래프, 시작노드, 방문한 노드 집합
    visited.add(start)  # 현재 노드를 방문 처리
    print(start, end=' ')
    
    # 현재 노드와 인접한 노드들을 순회
    for adjacent_node in graph[start]:
        if adjacent_node not in visited: #만약에 방문하지 않은 노드라면 
            dfs(graph, adjacent_node, visited) #그 노드를 시작노드로 해서 재귀함수 실행 -> 현재노드를 방문처리~ 반복

# 그래프를 인접 리스트로 표현한 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

visited = set()  # 방문한 노드를 저장하기 위한 집합

print("깊이 우선 탐색 결과:")
dfs(graph, 'A', visited)

그래프의 모든 노드를 깊이를 우선하여 탐색하는 DFS는 

재귀함수 또는 스택으로 구현될 수 있다.

여기서는 재귀함수로 구현됨

코드풀이~

시작노드를 방문처리하고

그 시작노드의 인접노드가 방문하지 않은 노드라면

해당 노드를 다시 시작노드로 설정해서 재귀함수~ (다시 그 시작노드로 방문처리하고 반복)

스택으로 구현한 코드

def dfs(graph, start):
    visited = set()  # 방문한 노드를 저장하기 위한 집합
    stack = [start]  # 탐색할 노드를 저장하기 위한 스택

    while stack:
        node = stack.pop()  # 스택의 가장 위에 있는 노드를 가져옴

        if node not in visited:
            visited.add(node)
            print(node, end=' ')

            # 인접한 노드들 중에서 방문하지 않은 노드를 스택에 추가
            for adjacent_node in graph[node]:
                if adjacent_node not in visited:
                    stack.append(adjacent_node)

# 그래프를 인접 리스트로 표현한 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("깊이 우선 탐색 결과:")
dfs(graph, 'A')

BFS 너비탐색 알고리즘 코드구현

from collections import deque
#먼저 collections 모듈에서 deque를 가져옵니다. 
#deque는 양쪽 끝에서의 빠른 append와 popleft 연산을 지원하는 큐(queue) 자료구조입니다

#이 함수는 그래프와 시작노드를 인자로 받는다.
def bfs(graph, start):
    visited = set()  # 방문한 노드를 저장하기 위한 집합 초기셋팅
    queue = deque([start])  # 탐색할 노드를 저장하기 위한 큐
    visited.add(start)  # 시작 노드를 방문 처리
    
    #큐가 비어있지 않은 동안 반복한다
    while queue:
        node = queue.popleft()  # 큐에서 가장 앞에 있는 노드를 가져옴. popleft를 해서큐에서 노드를 제거
        print(node, end=' ')
        
        # 인접한 노드들 중에서 방문하지 않은 노드를 큐에 추가하고 방문 처리
        
        for adjacent_node in graph[node]: #현재 처리중인 node의 인접한 노드들을 순회
            if adjacent_node not in visited:#방문했다는 집합에 해당노드가 없다면
                queue.append(adjacent_node) #큐에다가 인접 노드 넣기
                visited.add(adjacent_node) #방문했다고 방문집합에 추가하기

# 그래프를 인접 리스트로 표현한 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("너비 우선 탐색 결과:")
bfs(graph, 'A')

코드풀이는 다음과 같다~

선택한 시작 노드 주변을 확인. 

(인접노드 확인).

 확인할 애들을 큐에 저장

확인마친, 즉 방문한 애들은 방문집합에 저장.

큐가 텅빌때까지 반복

확인할 노드는 큐에서 꺼내서 씀. 맨 처음 넣은 앞에서부터 꺼낼거임

그래프의 현재 노드  주변에 있는 애들을  for문 반복문으로 다 확인해볼것임

 방문집합에 해당 노드가 없다면 방문안한거니까

아까 꺼냈던 노드를 큐에다가 다시 추가

그리고 그 노드에 방문(그 노드를 탐색)한거니까  방문집합에 그 노드를 넣는다. 

while은 조건문이 true일 때 수행하고 

조건이 false가 되면 빠져나온다. (강제로 빠져나오고 싶을 때 break)

for문은 순서열 처음부터 끝까지 실행

자바스크립트와 달리 === 연산자 없다. 

파이썬에서 대입 연산자는 = 기호뿐입니다. 변수에 값을 할당하는 데 사용됩니다.

반면에 ==는 두 값이 같은지 여부를 확인하는 비교 연산자입니다. 값이 같으면 True를 반환하고 그렇지 않으면 False를 반환합니다. 예를 들어, x == y는 x와 y의 값이 같은지 확인합니다.

Python에는 JavaScript와 같은 === 연산자가 없습니다. 대신 is 키워드를 사용하여 두 변수가 메모리에서 동일한 개체를 참조하는지 여부를 확인할 수 있습니다. 예를 들어 x is y는 x와 y가 동일한 개체를 참조하는지 여부를 확인합니다.

조건 있을 때 elif

조건없을 때 else