https://www.acmicpc.net/problem/1463

나만 어려운 문제일 수 있다 ㅎㅎ

피보나치문제는 되게 간단하던데 이 문제는 답지를 봐도 이해가 안되어서 하나하나 적으면서 풀어봤다.

이해가 안갔던 이유:

계산한 값들을 배열에 저장해야된다고 생각했다. 

숫자가 인덱스라는 점이 안 와 닿았다. 

코드 보면서 얘기해보자~~

먼저 dp 다이나믹 프로그래밍은

반복적인 계산을 효율적으로 처리를 하는 알고리즘이다. 

큰문제를 작은 문제로 나누어 해결하고 그 결과를 저장해놨다가 재사용하여 중복계산을 피한다.

피보나치 보면 이해가 바로 가능하다

https://www.acmicpc.net/problem/2748

n = int(input())
#앞서 계산된 결과를 저장하기 위한 DP테이블 초기화
#n번째
d = [0]* (n+1)
print("d:",d)
#피보나치 수 : 0, 1, 1, 2, 3, 5....
#0,1로 시작하는 값
#인덱스 1번째 1  
d[1] =1
#반복문은 2번째부터 시작. 
for i in range(2, n+1): #2~n까지
	#1= 1+0
    d[i] = d[i-1]+ d[i-2]
    print(d[n])

처음 0,1을 주고 시작함!

그러면 인덱스 2, 부터 계산됨

그렇다면 이 문제.

피보나치는 더한 값들을 배열 d에 기록해서 간단했는데

이문제는 구하고자 하는 값이 횟수이다. 횟수를 기록해야한다.

숫자 10이 몇 번의 횟수를 거쳐 1이 되었냐~ 는 문제이다.

이 숫자 10과 횟수의 관계를 코드로 정립 못했었다..

횟수를 기록한 d배열의 인덱스가  "주어진 숫자" 역할을 했다. 그게 잘 안와닿았다.

즉 인덱스 3은 숫자 3. 그러면 인덱스 3에 횟수를 기록하게 되는 것이다. 

횟수를 기준으로 하니, 현재 횟수가 이전횟수 + 1이다라는게 겨우 이해되었다.

숫자가 2나 3으로 나눠지는 경우 : 예) 숫자가 6이면 "이전5의 횟수+ 1"을 하면 4가 되는데, 숫자 6은 2로 나눠지기때문에
최솟값으로 비교를 한다. "이전5의 횟수+ 1"  과 "d[6//3] 즉 d[2] 숫자2의 횟수에 1을 더한 값"을 비교하는 것이다.

나는 하나하나 값 넣어서 적어보면서 이해했다 ㅎㅎㅎ

# 답지
# n = int(input())
n = 10
print('n',n)
 
#계산한 횟수를 저장하는 용이래!!!
d = [0] * (n+1) 
print("d",d)

for i in range(2, n+1):  #2부터하는이유는0,1은 나누어떨어지지 않아서 횟수가 걍 0이라서!
    d[i] = d[i-1] +1 #더하기 1을 하는 이유는 기존횟수느 = 이전 횟수에 + 1 식 늘어나니까. 
   #i가 3으로 나눠지는 값이면 
    if i %3 == 0:
        #숫자 3의 횟수는 = 이전 횟수에 하나더한 횟수거나, 3으로 나눈 값의 횟수에 하나 더한 횟수! 둘중에 더 작은 값!
        d[i] = min(d[i], d[i//3]+1)
        print("3d[i]:", d[i])
    if i%2 == 0:
        d[i] = min(d[i], d[i//2]+1)

 
print(d[n])

다른 분들의 코드를 찾아보면서도 이해가 안되었는데 역시 직접 찍어가면서 하는게 제일 빠르다. 

물론 나는 답지를 보면서 ㅎㅎ

문제 이해를 잘못해서 엄청 헤멨다.

Magic square 마방진

마방진이란?

가로의 숫자들 더한 값,

세로의 숫자들 더한 값,

대각선숫자들 더한 값이 모두 같은 사각형!

문제가 요구하는 바:

https://www.hackerrank.com/challenges/magic-square-forming/problem?isFullScreen=true 

input값으로 만든 행렬을 마방진으로 만들어서 두 행렬을 비교하고

바뀐 값들의 차 중에 가장 작은 수들를 더해서 출력!

1. 먼저 주어진 값을 마방진으로 만들어야 한다!

근데 우리는 가장 작은 수들을 찾기를 윈해서 모든 경우의 마방진을 만들어봐야했다.

여기서 배운 파이썬 함수

permutations

순열을 만들어주는 함수다. 

(순열이란, 조합과 달리 순서를 고려해 나열한 경우의 수를 말한다)

먼저 인풋 값 자체를 코드로 체크할 수 있게 정리해줬다 

이 인풋값을 차례로 넣어줬다. 

그결과 X = [5,3,4,1,5,8,6,4,2]가 되었다. 

지금은 이것은 마방진이 아니다. 

마방진으로 만들기 위해 모든 순서의 경우의 수를 만들어보자. 

1부터 9까지! 

for문 안에 P를 찍어보면 엄청많다

여기서 마방진 조건에 맞는 애들을 찾아주자. 

가로끼리 더한 값이 15

세로끼리 더한 값이 15

대각선끼리 더한 값이 15

파이썬 코드에 익숙하지 않아서 이 조건을 이해하는데 좀 걸렸다. 

p(0:3) 은  인덱스0,1,2라는 뜻이다. 위 인풋모양 생각하면 맨 위의 가로 한면! 여기 sum() 이 감싸니까 즉, (8 +3+4)

p(3:6)은  인덱스 3,4,5 맨 오른쪽 세로 한면 (4+9+2)

p(0::3) 이건 p배열에서 p[0]에서 시작해서 세칸씩 이동한 값  p = [8,3,4,1,5,9,6,7,2 ] 이므로 (8+1+6)

p(1::3) 얘도 같음 (3+5+7)

대각선도 다 더해서 15여야함

P[0] + P[4] + P[8] == 15 

P[2] + P[4] + P[6] == 15)

P[-3::] 이건 뒤에서 3번째에서 끝까지 더한 값 (6+7+2)

이렇게 마방진 조건을 다 갖춘P와 기존인풋이었던 X의 차

둘이 그냥 빼는게 아니라 모든 인덱스의 값들을 비교해서 빼야해서 

range(0,9)  for문으로 0부터 8인덱스까지 비교해서 빼줌

abs() 로 감싼이유는 만약에 2-3 나오면 음수니까 양수로 만들어주려고 씀. 

그 차리르 다 더한 값 중에 가장 작은  값으로~ min()

"Ans가 또 들어가는 이유는 for 루프를 통해 permutations의 모든 경우를 탐색하면서 최소값을 찾기 위해서입니다.

for 루프는 permutations(range(1,10))를 통해 1부터 9까지의 숫자로 이루어진 순열을 하나씩 가져옵니다. 각 순열을 P로 표현하고, 조건문을 통해 해당 순열이 마방진(magic square)의 조건을 만족하는지 확인합니다.

만약 조건을 만족하는 마방진이라면, sum(abs(P[i] - X[i]) for i in range(0,9))를 통해 해당 마방진과 주어진 X 리스트와의 차이의 합을 계산합니다. 그리고 이 값을 기존의 Ans와 비교하여 작은 값으로 Ans를 갱신합니다.

따라서, for 루프를 통해 모든 경우를 탐색하면서 찾은 최소 차이의 합을 Ans에 저장하게 됩니다."

from itertools import *

X = []
X.extend(list(map(int,input().split())))
X.extend(list(map(int,input().split())))
X.extend(list(map(int,input().split())))

Ans = 81
for P in permutations(range(1,10)):
   
    if sum(P[0:3]) == 15 and sum(P[3:6]) == 15 and sum(P[0::3]) == 15 and sum(P[1::3]) == 15 and P[0] + P[4] + P[8] == 15 and (P[2] + P[4] + P[6] == 15) and  sum(P[-3::]) == 15:
        # print("PPPP:",P) #P is magic square
        Ans = min(Ans, sum(abs(P[i] - X[i]) for i in range(0,9)))
print(Ans)

import sys
sys.stdin = open('1920.txt','r')
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
M = int(input())
array = list(map(int, input().split()))

A.sort()
for num in array:

    lft, rt = 0, N-1
    isExist = False
    while lft <= rt:
        mid = ( lft+ rt ) //2
        if num == A[mid]:
            print(1)
            isExist =True
            break
        elif num < A[mid]:
            rt = mid -1 
        elif num >A[mid]:
            lft = mid +1
        
    if not isExist:
        print(0)

변수를 정하고 하는 것부터 적응이 안되었음

입력값 변수로 만들어 놓고

출력값 똑같이 나오도록 짜야하는데

문제 보고 이진탐색으로 하면 되겠다!

는 알았는데 

" 이 수들이 A안에 존재하는지 알아내면 된다. "

이부분이 이해가 안갔었다.

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

A리스트를 정렬해서 순서대로 해놓고

거기서 array의 값들을 하나하나 찾아보는 방식!

A안에 존재하면 1

없으면 0

이진탐색 방법으로 할것이고 

array전체를 돌기때문에 for문

https://velog.io/@deannn/BOJ-%EB%B0%B1%EC%A4%80-1920%EB%B2%88-%EC%88%98-%EC%B0%BE%EA%B8%B0-Python

----

참고

c = '1,2'

# print(list(map(int, c.split(',')))) #split은 문자열에만 된다. 배열을 하고 싶으면 join

#결과

[1,2] 

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

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

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

재귀함수

나 자산을 또 호출하는 함수

반복적으로 실행함

그래서 재귀 함수 만들 때!

1. recurrence relation 점화식

2. base case 

꼭있어야함. 

점화식으로 계속 반복되고 

그 반복이 base case에 도달하면 재귀함수가 끝이 남. 

base case가 없으면 무한루프되므로 주의!

Tree 개념

노드: 트리는 보통 노트로 구현

차수degree 각노드가 갖는 자식의 수

모든 노드의 차수가 N개 이하인 트리를 n진 트리라 한다. 

Binary Tree 이진트리 

차수가 2진 이하 

이 노드들의 구성 요소:

value값 저장, left child 주소값 저장, right child wnthrkqt wjwkd

코드로 구현시:

1. 이렇게 구현된 노드생성 

2. binary Tree 구성

트리 순회Traversal (= 트리탐색, 완전탐색)

트리의 각 노드를 방문하는 과정을 말함

모든 노드를 한번씩 방문해야해서 순회 방법으로는 

너비우선탐색의 BFS Breadth-First Search

깊이우선탐색의 DFS Depth-First Search

BFS

root기준으로 탐색. 아래로 level 0, level1 이렇게 가까운것부터 탐색

순회해서 그 노드에 "방문한다"

->

그 노드에 접근하는 것은 언제든 할 수 있음.

근데 "방문"은 그노드에 접근해서 "어떤 작동을 시키는 것"

트리순회에서 그냥 접근하는 것과 방문하는 것은 다름!

DFS

스택 반복문으로도 만들 수 있고

재귀로도 만들 수 있음.

DFS는 접근 어떻게 할지 생각하고 방문 어떻게 할지 생각.

접근을 재귀로 한다. 

방문은 순회 종류에 따라 다른데

전위순회 preorder

자식노드들에게 가기 전에 일단 자기 자신 방문(기록을 하든 뭘하든..)먼저함.

중위순회 inorder

나 자신을 방문하는게 중간에 있음

후위순회 postorder

자식들 다 방문하고 나서 자기 자신 방문

구현 방법 

Array list

Array list + linked list

해시테이블은 효율적인 탐색(빠른 탐색)을 위한 자료구조로써 key- value쌍의 데이터를 입력받음

저장,삭제, 검색의 시간복잡도 O(1)

키가 걍 Index로 쓰이기도 하고

문자열이 키면 그걸로 index 지정할 수 없어서 

index를 따로 부여하기도 함. 

근데 경우에 따라 해시테이블의 collision 충돌 가능성있음. 

index를 key로 저장

linked list는 Node라는 구조체가 연결되는 형식으로 데이터를 저장하는 자료구조이다. 

Node는 데이터 값과 next node의 주소값을 저장한다. 

linked list는 메모리 상에서는 비연속적 저장되어있지만 

각각의 node가 next node의 메모리 주소값을 가리킴으로써 

논리적은 연속성을 갖게 된다. 

Array list는 연속성 유지하려면 순차적으로 저장해야하지만

linked list는 자유롭다. 

주소값을 함께 저장하기 때문에! 근데 그만큼 데이터당 차지하는 메모리가 더 커지게 된다. 

linked list 구현시 

1. head값을 가져야함!!

2. head가 linked list의 첫번째 노드값을 가리켜야한다!

이렇게 되면 어느 인덱스에 있는 데이터에도 접근할 수 있다.

3. 마지막 노드는 다음 메모리주소가 0(none)이어야한다.

linked list의 가장 간단한 연산자 append()

get() 특정 index에 저장되어있는 값을 가져오는 연산자.

실제 구현시 

양방향으로 왔다갔다하는 양방향 doubled linked list도 있음