오랜만이라서 싹 다 까묵음...

공부하는김에 DFS와 BFS, 두 방식으로 풀어볼게요

BFS

from collections import  deque
N = int(input())
M = int(input())
graph = list([] for _ in range(N+1))
visitChk = [False] * (N+1)

for _ in range(M) :
    i, j = map(int,input().split())
    graph[i].append(j)
    graph[j].append(i)

def bfs(start) :
    dq = deque([start])
    while dq :
        now = dq.popleft()
        visitChk[now]  = True
        for j in graph[now] :
            if not visitChk[j] :
                dq.append(j)
    count = 0;
    for i in visitChk :
        if i :
            count = count + 1
    print(count-1)
bfs(1)

BFS에서 중요한 deque !

def bfs(start) :
    dq = deque([start])
    while dq :
        now = dq.popleft()
        visitChk[now]  = True
        for j in graph[now] :
            if not visitChk[j] :
                dq.append(j)

이 부분이 BFS를 하는 부분이다

DFS

N = int(input())
M = int(input())
graph = list([] for _ in range(N+1))
visitChk = [False] * (N+1)

for _ in range(M) :
    i, j = map(int,input().split())
    graph[i].append(j)
    graph[j].append(i)

def dfs(now) :
    visitChk[now] = True
    for j in graph[now] :
        if not visitChk[j] :
            dfs(j)

dfs(1)

count = 0
for i in visitChk:
    if i:
        count = count + 1
print(count - 1)

DFS는 재귀호출을 이용하여 BFS보다 비교적 간단하게 구현 가능하다

def dfs(now) :
    visitChk[now] = True
    for j in graph[now] :
        if not visitChk[j] :
            dfs(j)

Idea)

0을 움직이는 좌표라 생각해봤다. 그래서 BFS를 이용하려고 했다.

그림을 예로 들면, 0이 이동할 수 있는 방향은 1 , 2, 3 세 방향이다.

움직인다는 것은 움직일 수 있는 방향의 있는 숫자와 자리를 바꾸는 것을 의미한다.

별도의 정답 리스트를 만들어 놓아서, 0이 4방향으로 숫자를 바꾸고(이동하고) 비교함으로써 index에 맞는 숫자가 들어갔는지 확인한다.

for _ in range(4) :
    y좌표 이동
    x좌표 이동
    이동한 좌표와 원래 있던 좌표와 값을 바꾼다.
    if not 방문 and 유효성 and ans[ny][nx] == board[ny][nx]
        d + 1
        방문처리
        q에 추가 (ny,nx,nd)
    else :
        바뀐 값을 다시 원래대로 돌려 놓는다.

board = dict()
boardStr = ''
for i in range(3):
    boardStr += ''.join(sys.stdin.readline().split())

dx = (1,0,-1,0)
dy = (0,1,0,-1)

answer = "123456780"

dq = deque()

def validChk(y,x) :
    return 0<=y<3 and 0<=x<3

def bfs(boardStr) :
    dq.append(boardStr)
    board[boardStr] = 0

    while dq :
        tmp = dq.popleft()
        if tmp == answer :
            print(board[tmp])
            return

        zeroIndex = tmp.find('0')
        zx = zeroIndex%3
        zy = zeroIndex//3

        for k in range(4) :
            nx = zx + dx[k]
            ny = zy + dy[k]
            nZeroIndex = ny*3+nx
            if validChk(ny,nx) :
                tmpList = list(tmp)
                tmpList[zeroIndex],tmpList[nZeroIndex] = tmpList[nZeroIndex],tmpList[zeroIndex]
                nxtStr = ''.join(tmpList)
                if not board.get(nxtStr):
                    board[nxtStr]  = board[tmp] + 1
                    dq.append(nxtStr)

    print(-1)

bfs(boardStr)

bfs는 방문체크를 확인할 필요가 있는데 이 문제에서는 이것을 dict() 사전 자료형을 이용하여 확인한다.

입력받은 3 x 3 배열을 문자열로 바꾸어서 저장한다.

for i in range(3):
    boardStr += ''.join(sys.stdin.readline().split())

굳이 배열이 아닌 문자열로 저장하는 이유는 탐색을 진행하면서 문제에서 요구하는 "123/456/780" 을 0이 이동할 때 마다 확인해주어야 한다. 이 때 이차원배열을 사용하면 각 index를 하나씩 비교하면서 확인해야 하는데, 이를 문자열로 바꾸어 dict를 활용해서 확인한다면 더 빠르게 확인이 가능하고 제한된 메모리 안에서 해결이 가능하기 때문이다.

때문에 처음 큐에 들어가는 것은 시작좌표가 아닌 처음 board의 모양이다. (문자열)

dict에 문자열 : 횟수 형태로 저장한다.

이 문제를 공부하면서 BFS탐색으로 찾은 결과는 최단거리거나 최소횟수를 보장한다는 것이다.

BFS는 레벨1인 노드에서 레벨2인 노드를 탐색하고 레벨3인 노드를 탐색하는 순서로

탐색을 하기 떄문이다.

결과를 찾은 순간 레벨N이 었다면, N이 최단거리나 최소횟수이다.

 zeroIndex = tmp.find('0')
        zx = zeroIndex%3
        zy = zeroIndex//3            

큐에서 pop되는 것은 문자열형태이기 떄문에 이를 탐색하기 위해서는 이차원배열의 형태로 바꿔줄 필요가 있다.

먼저 문자열에서 find()를 통해서 0의 index를 찾고 이를 이차원배열의 index로 변경해준다.

012/345/678 를 보면 각 x(행)는 0/1/2인데 3으로 나눈 나머지임을 알 수 있다. y(열)도 비슷한 개념으로 각y는 012/012/012이다. 이는 index를 3으로 나눈 몫임을 알 수 있다.

 nZeroIndex = ny*3+nx     

위에서 1차원의 index를 2차원으로 바꾼 것처럼 2차원의 index를 다시 1차원으로 바꾸어야 한다. 리스트에서 0을 바꾸는 작업을 해주어야 하기 때문이다.

이렇게 바꾼 리스트를 문자열로 바꾸어 큐에 저장한다.

전형적인 길찾기 문제로 최단거리를 구하는 문제이다. 따라서 BFS를 쓰는 것이 좋다

DFS로도 풀 수 있지만 BFS로 했을 때 정답의 경로가 발견이 되자마자 탐색을 종료하기 떄문에 운이 좋으면 같은 완전탐색인 DFS보다 시간을 더 단축시킬 수 있다.

위 문제 처럼 격자 칸이 주어지고 사방으로 움직이면서 길을 찾는 문제들은 자주 출제되는 형태의 문제이다.

이 문제를 공부하면서 중요한 포인트라고 생각되는 것은 아래와 같다.

1. dx,dy의 상대좌표를 이용하여 움직이는 좌표 계산하기
2. N x M 격자 좌표에서 유효성 검사하기
3. 격자칸을 좌표계로 대입할 때 주의하기
   • x 좌표계는 dy , y좌표계는 dx이다 [0][1] -> (1,0) [0][2] -> (2,0) [1][3] -> (3,1) [2][3] -> (3,2)
4. bfs로 탐색하는 것은 좌표의 이동이다 = 위 아래 왼쪽 오른쪽 -for k in range(4) => 4가지 방향... 8가지 방향이면 8번 반복

먼저 격자칸을 리스트에 저장하고 N x M 크기를 가지는 방문 체크 용도의 리스트를 선언하고 False로 초기화한다.

또한 격자칸은 N x M으로 크기가 정해져 있으므로 이 크기를 벗어나면 안된다.

따라서 별도의 격자칸을 벗어나는지 확인해주는 함수를 만들어준다

def vaildBoard(y,x) :
    return 0<=y<N and 0<=x<M

좌표의 움직임을 dx,dy를 이용해서 상대좌표로 나타낼 것이다.

dx = (1,0,-1,0) 
dy = (-1,0,1,0)

BFS를 사용해 문제를 해결할 것이므로 deque(q)를 사용한다.

시작좌표와 최단거리를 구해야하므로 거리(d)를 q에 append하고 시작 좌표를 방문체크한다.

q가 빌 때 까지 반복한다. q에는 현재 (0,0,1)이 저장되어있다.

이 시작 좌표와 거리를 q에서 popleft한다.

해당 좌표가 N,M이면 거리를 출력하면 된다.

아니라면 bfs탐색을 시작한다.

공부했던 bfs는 그래프를 탐색하므로 각 tree[ 노드 번호 ] 였지만 이 문제는 미로의 탐색이다. 사람이 격자칸 미로를 움직인다고 생각하면 이 사람이 미로를 탐색하면서 이동 할 수 있는 방향은 4가지 이다. 따라서 사람이 이동할 수 있는 4가지 방향에 대해서 bfs탐색을 돌린다.

for y,x,d in range(4) : #4가지 방향
    ny = y + dy[k] 
    nx = x + dx[k]
    nd = d + 1

ny와nx는 이동한 후에 좌표이다. 움직이는 좌표를 상대좌표를 이용해서 구한다고 했는데, dy,dx 리스트에 들어있는 1,-1을 이용해서 4가지 방향으로 이동한 좌표를 구한다.

좌표가 이동한 후에 방문을 한 좌표인지, 유효한 좌표인지 확인한다. 후에 q에 움직인 좌표 +1한 거리를 q에 넣어주고 방문체크를 해준다.

백준에 제출한 코드

import sys
from collections import deque

dx = (1,0,-1,0)
dy = (0,1,0,-1)

N,M = map(int, sys.stdin.readline().split())

board = [sys.stdin.readline() for _ in range(N)]
visitChk = [[False] *  M for _ in range(N)]
dq = deque()
dq.append((0,0,1))
visitChk[0][0] = True

def endChk(y,x) :
    return 0<=y<N and 0<=x<M

while len(dq)>0 :
    y,x,d = dq.popleft()

    if y == N-1 and x==M-1 :
        print(d)
        break

    for k in range(4) :
        ny = y + dy[k]
        nx = x + dx[k]
        nd = d + 1
        if endChk(ny,nx) and not visitChk[ny][nx] and board[ny][nx] == "1" :
            visitChk[ny][nx] = True
            dq.append((ny,nx,nd))

DFS와 BFS를 공부하기 좋은 문제인것 같다.

알고리즘을 공부하면서 DFS와 BFS가 무엇인지는 알았지만 정작, 파이썬으로 구현할줄은 몰랐다.

그래서 이 문제를 통해 DFS와 BFS에 대해 정확히 알아가고 싶다.

먼저 DFS는 깊이우선탐색으로 아래 그림 처럼 연결된 하위 노드가 있으면 우선적으로 하위 노드들을 탐색한다.

반면에, BFS는 너비우선탐색으로 같은 레벨의 노드를 우선적으로 탐색한다.

DFS와 BFS를 구현하기에 앞서, 탐색할 트리는 보통 리스트로 구현한다.

tree = [[False] * N for _ in range(M)]

tree[N]의 리스트가 M개 존재하는 것이다. 그래서 노드 1번과 연결된 노드는 tree[1]에 저장돼있다.

DFS와BFS 문제를 해결하기에 앞서 먼저 입력된 트리를 리스트에 저장하고 연결된 노드를 표시해야한다. 위에서는 False로 했지만, 1이나 0 .. 등 여러가지로 표현하는 방법이 있다.

BFS

보통 queue를 통하여 구현한다. BFS를 구현한 함수를 bfs라 하고 매개변수로 시작노드를 받는다고 하자.

bfs(시작노드) <시작노드 : 보통 1번 노드>

전달받은 시작노드를 queue(이하 q)에 저장한다.

현재 q 상태는 q = [1]이다

시작 노드를 방문처리한다.

별도의 방문처리를 담당하는 1차원 리스트를 선언하고 False로 처리하며, 방문한 노드의 index를 True로 변경함으로써 방문한 노드를 구별한다.

이제 q에 들어 있는 노드를 popleft(이하 pop)한다. 이하 과정부터는 q가 비워진 상태일까지 한다.

이하 과정은 모두 while q : 에 속해 q가 비워질 때 까지 반복문이 돌아간다.

pop하면서 원하는 작업을 실행하면 된다. 이 문제에서는 pop한 노드의 번호를 출력하면 된다.

현재 q 상태는 q = [1]이다

아까 만들어 놓은 트리를 이용하여 bfs를 실시하면 된다 -> tree [ q에서 pop된 노드 번호 ]를 이용하여 for 반복문을 돌린다.

이미 tree에는 노드의 연결 상태가 모두 저장되어있기 때문에 방문처리가 가능하다.

그림을 예로 들면 이미 tree[1]에는 [2,3]의 노드 번호가 저장되어있다.

tree[1]에서 반복문을 돌면서 방문 하지 않은 노드라면 q에 추가하고 방문 처리를 해준다.

대략적으로,

for tree[ q에서 pop된 노드 번호 ] :
    if 방문 안함 :
        q에 append
        해당 노드 방문처리

이런 과정을 겪는다.

1번 노드가 pop되고 bfs를 한 번 돌린 q의 상태는 q = [ 2, 3 ] 이다. 현재 방문 처리된 노드는 1, 2, 3번 노드이다.

아직 q에는 값이 들어 있으므로 다시 q에서 pop(popleft)부터 시작하는 과정이 반복된다. q에 저장된 1번 노드와 연결된 노드의 하위 노드들을 bfs하는 것이다.

2번 노드가 pop되고 tree[2]에서 반복문을 돌린다.

! 여기서 방문처리 하는 이유가 나온다. 2번 노드는 1번 노드와도 연결되어 있으므로 현재 tree[2]에 1번 노드가 저장되어 있기 때문에 1번 노드에 대하여 방문처리를 하지않으면 또 다시 1번노드가 q에 append되고 무한루프에 빠지게된다. !

1번 노드는 방문 처리됐으므로 q에 append하지 않는다. 2번과 연결된 4번과 5번 노드는 방문하지 않은 노드이므로 q에 append하고 방문처리한다.

q의 현재 상태는 = [ 3, 4, 5 ]이며, 방문처리된 노드는 1, 2, 3, 4, 5번 노드이다.

이후 과정을 계속 반복한다. q가 FIFO (First In First Out) 구조이므로 같은 레벨의 노드가 먼저 pop되고 하위 레벨의 노드는 나중에 pop되기 때문에 bfs, 너비우선탐색이 가능하다.

DFS

재귀함수를 통하여 구현가능하다. DFS를 구현한 함수를 dfs라하고 매개변수로 시작노드를 받는다고 하자.

dfs(시작노드) <시작노드 : 보통 1번 노드>

전달받은 시작노드를 방문 처리한다. 그리고 BFS와 마찬가지로 tree[ 노드 번호 ]에서 for반복문을 돌린다. 방문 하지 않은 노드라면 방문처리하고 dfs[ 해당 노드 ]를 호출한다.

dfs(1) -> tree[1] = { 2, 3 }
    dfs(2) -> tree[2] = { 4 , 5 }
        dfs(4) -> tree[4] ={ x } 
        dfs(5) -> tree[5] = { 6 }
            dfs(6) -> tree[6] = { 3 }
                dfs(3) -> tree[3] = { 7 , 8 }
                    dfs(7) -> tree[7] = { x } 
                    dfs(8) -> tree[8] = { x } 

위 과정이 그림에 해당하는 dfs호출 순서이며 곧, dfs의 탐색순서이다.

완성된 코드는 여기서 보면 된다. 완성된 코드

deque의 메소드 중 하나인 .rotata()를 이용하면 된다.

1번 연산은 첫번째 요소를 pop하므로 popleft연산이므로 일반 queue가 아닌 deque를 사용해야 한다. 2번 연산은 왼쪽으로 한 칸 씩 이동 즉, 왼쪽으로 회전하므로 rotate(음수) 또한 3번 연산은 오른쪽으로 한 칸 씩 이동 즉, 오른쪽 회전하므로 rotate(양수)이다.

2 9 5 <- 각 K를 의미한다.
2를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 1번 rotate 시켜야한다  = rotate(-(2-1)) 
오른쪽으로 9번 rotate 시켜야한다 = roata(10-(2-1))

2,3번 연산의 최소 횟수 이므로 최소한의 회전을 찾아야 하므로 min을 이용한다.


해당 요소를 popleft한 후에는 deque의 길이가 9로 줄어든다.

또한 2를 popleft하기 위해서 회전이 일어났으므로 deque의 상태는 처음 상태와는 다르다. 왼쪽으로 한번 회전하고 2를 popleft했으므로 deque의 처음 원소는 3번째 원소이다(편의상 3이라고 함) 

3에서 부터 9를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 6번 rotate 시켜야한다  = rotate(-(9-3))
오른쪽으로 3번 rotate 시켜야한다 = roata(9-(9-3))

즉 , K번째 요소를 얻기 위해서 K-deque[0](오른쪽 회전), K-(K-deque[0])(왼쪽 회전) 중 더 작은 값을 가진 방향으로 회전하면 된다.
K값이 더 작으면 음수로 무조건 양수보다 작기 때문에 절대값으로 비교한다~~~~
=>rotate(min( abs(K-deque[0]),abs(K-(K-deque[0])) ) )

9를 popleft했으므로 dequeue의 길이는 8이다. 이 때 첫번째 요소는 10이다.

10에서 부터 5를 popleft하기 위해서는 두 가지 방법이 있다.
왼쪽으로 5번 rotate 시켜야한다  = rotate(-(5-10))
오른쪽으로 3번 rotate 시켜야한다 = roata(8-(5-10)) ==> ??

라고 생각했는데 막상 해보니까 아니다...

이 문제의 idea는 ...

왼쪽, 오른쪽 회전 중 더 작은 값을 찾는 것이다.

이 값을 찾기 위해서는 빼내려는 요소의 index값을 알아야 한다. 이때 deque.index()를 이용해서 해당 요소의 index값을 알 수 있다.

즉 deque.index(2 , 5 , 9)를 통해서 현재 index를 얻어와 deque[0]에서 가까운 쪽으로 회전하는 것이다.

index()를 통해서 얻어온 요소의 index값을 K라 하자.

K는 첫번째 요소로 부터 떨어진 거리이다. 거꾸로 생각하면 deque의 끝에서 부터의 거리도 구할 수 있다. len(deque) - K이다.

즉 첫번째 요소로 부터 더 가까우면 왼쪽으로 회전, 끝에서 부터 더 가까우면 오른쪽 회전하면 된다.

이 문제는 스택으로도 풀 수 있고 덱으로도 풀 수 있는 문제이다.

나는 덱으로 풀었다.

이유는 덱으로 스택을 구현할 수 있기 때문에 굳이 스택을 사용안했고 덱을 공부하고 있기 때문에 덱을 사용하였다.

문제에 나온 것 처럼 막대기를 오른쪽 방향에서 봤을 때 막대기가 몇 개 보이는지 구하는 문제이다.

예를 들어 6 6 9 7 6 4 6 을 오른쪽에서 본다면 제일 앞에 나와있는 6길이의 막대기보다 작은 길이의 막대기는 보이지 않는다. 따라서 6보다 큰 7과 9길이의 막대기만 보인다.

나는 deque에 막대길의 길이를 다 넣고 가장 긴 길이의 막대기와 비교하면서 answer값을 1씩 증가시켰다.

최장길이 : 6 -> 4 -> 6 -> 7 -> 9 -> 6 -> 6 answer : 1 -> 1 -> 1 -> 2 -> 3 -> 3 -> 3

-> 이 문제의 포인트는 최장길이를 업데이트 해주어야한다.

5 5 4 3 2 1을 보자 deque에서 가장 먼저 pop된 1은 현재 가장 최장길이이다.

하지만 pop을 한 번 더 하면 최장길이는 2로 바뀌어야 한다. (이 때 answer값을 1증가시킨다)

최장길이 : 1 -> 2 -> 3 -> 4 -> 5 answer : 1 -> 2 -> 3 -> 4 -> 5

[Idea]

먼저, 출력이 풍선 안에 숫자가 아닌 Index의 번호가 나와야 하기 때문에 입력받은 숫자와 함께 Index를 함께 저장해주었다.

예를 들면, 예제 입력에 3 2 1 -3 1을 (3,1) (2,2) (1,3) (-3,4) (-1,5) 처럼 저장하는 것이다.

그리고 pop을 하면 먼저 첫번째 요소가 양수인지 음수인지 판별을 해준다.

만약 양수라면 pop을 하고 음수라면 popleft를 한다

먼저 첫번째 풍선을 pop하면 (3,1)이 나오고 3은 양수이므로 (3,1)을 제외하고 pop을 풍선안에 적혀있는 숫자(k) 만큼 pop을 하면서 k-1만큼 append해준다

이러면 (3,1) // (2,2) (1,3) (-3,4) (-1,5) 에서 (-3,4) (-1,5) (2,2) (1,3) 처럼 k-1만큼 append하고 마지막(k번째) 으로 pop을 하면 (-3,4)가 나온다.

(-3,4)를 보며 -3이므로 음수이다. 이때는 3과 다르게 pop이 아닌 popleft를 한다.

현재 (-3,4)는 pop이 되어 나갔고 (-1,5) (2,2) (1,3)이 현재 deque의 상태이다.

앞서 말했던 바와 같이, -3의 절댓값이 3(k)만큼 popleft를 하고 2(k-1)만큼 append가 아닌 appnedleft를 해준다.

위 과정을 거치면 (-1,5) (2,2) (1,3) 이 (1,3) (2,2) (-1,5)에서 마지막(k)에서 popleft를 하면 (-1,5)가 나온다.

마지막으로 (2,2) (1,3)에서 -1의 절댓값인 1만큼 popleft를 하면 (1,3)이 나오고 마지막으로 남은 (2,2)를 pop하면 된다 .

각 풍선을 pop할 때마다, 두번째 요소인 index를 ans배열에 저장한다.

일단은 요로코롬 생각해보았다.

근데 이 방법보다는

[출처] https://excelsior-cjh.tistory.com/96

deque에 있는 rotate메소드를 쓰면 된다.

하..

rotate를 이용하여 문제를 해결한 방법

[출처] https://computer-science-student.tistory.com/582

알고리즘

해당 알고리즘을 클릭하시면 알고리즘 시리즈로 이동합니다. !

• 배열 / 연결리스트


• 스택


• queue / deque / heapq


• map / set


• 브루트 포스 : 완전탐색


• 순열 / 조합


• 그리디 알고리즘


• DFS / BFS


• 백트랙킹


• 선형탐색 / 이분탐색


• 매개변수 탐색 : 파라메트릭 서치


• DP - 동적계획법

문자열은 변경 불가능한 자료형이다 !

 1  2  3  4  5  6
 s  t  r  i  n  g
-6 -5 -4 -3 -2 -1

문자열을 앞에서 셀 때는 index가 0부터 시작하며, 뒤에서 셀 때는 index가 -1부터 시작한다.

str = "good"
for goodChar in str :
    print(goodChar,end=",")

> g,o,o,d

str="good"
for goodChar in range(len(str)) :  # 문자열의 길이만큼 반복
    print(goodChar,end=",")

> g,o,o,d

슬라이싱

[시작 : 끝 : 증감값]

(시작 값) 부터 (끝 값 - 1)의 index에 해당하는 문자만을 가져온다

str="good"
print(str[1:3])

> oo

문자열 관련 함수

str = "press is fun"

print(len(str)) #문자열의 길이 12 

print(str.find('s')) #s의 처음 위치 3

print(str.rfind('s')) #s의 마지막 위치 7 = 뒤에서 부터 찾기

print(str.index('i')) #i의 처음 index

print(str.count('s')) #s의 개수 3

print("push" in str) #False : str에 push가 있는지 

print("push" not in str) #True : str에 push가 없는지 

• 분리, 결합,대체

print(str.strip()) # pressisfun 양 쪽 공백 제거 

print(str.split()) # ['press', 'is', 'fun'] split()의 인수로 문자열을 분리

print(" ".join()) # press is fun 문자열 중간에 "~"이 삽입됨 

print(str.replace("press","push")) # push is fun press를 push로 replace

• 포맷팅

print(str + "and good " + str(333)) # press is fun and good 333 '+'로 문자열들을 연결

print("%d월 %d일 %s" %(month,day,str)) #month월은 day일 str

print(".2f",0.3333333) #0.33 소수점 이하 2자리

for 변수 in 반복가능한 컬렉션 : 
    반복할 명령

• range(시작, 끝, 증가값) 시작값 default : 0 증가값 default : 1

for i in range(1,10) : #10번반복 

for i in range(10) : #10번반복 
# for in in range(0,10,1)

• 변수 생략 가능

  for _ in range(10) : #10번반복 
    변수와 상관없이 반복되는 명령문이 실행

  while

  while True : 
    반복할 명령
    if 탈출 조건 : break

무한루프 사용 시, 탈출조건을 꼭 명시해주어야 한다.

for i in range(1,10) : #10번반복 

for i in range(10) : #10번반복 
# for in in range(0,10,1)

+, -, *, / 이 4가지 연산자, 기본적인 사칙 연산자 외에도

고급 산술 연산자가 있다.

** : 거듭제곱

// : 정수 나누기

% : 나머지 연산자 ---> 짝수와 홀수를 판별할 때 많이 사용

print(11**2) ## 11 x 11 

print(125//4) ## 125 / 4 의 몫 부분

print(125%4) ## 125 / 4 의 나머지 부분

121
31
1

i=3
if i%2 == 0 :
    print("짝수입니다")
elif i%2 == 1 :
    print("홀수입니다")

홀수입니다

2로 나누었을 때, 나머지가 0이면 짝수이고 1이면 홀수임을 이용한다.

형변환

• 문자열 연산

앞서 소개했던 기본적인 연산자 중 +,* 를 수학적 연산 뿐만이 아닌 문자열에도 사용할 수 있다.

str1 = "벤치 증량에는"
str2 = " 해머컬 !"
print(str1 + str2)

벤치 증량에는 해머컬 !

+로 문자열끼리 이어주기 위해서는 피연산자가 문자열이어야한다.

str1 = "해머컬좋아 "
print(str1 * 3)

해머컬좋아 해머컬좋아 해머컬좋아 

*로 문자열을 반복해주기 위해서는 연산자의 좌측은 문자열, 우측은 정수형이어야한다.

• str()과 int()

  문자열 변환 str() 그리고 정수형 변환 int()

  int()

1. 오직 아라비아 숫자와 부호만이 존재해야한다 !

• int("333%") ## 오류 !! % <- 문자
• int("3333.2222") ## 오류 !! . <- 문자

2. 두 번째 인수로 진법을 지정가능하다.

• int("1a",16) ## 26
• int("15",8) ## 13

str()

print("문자열" + 333)

문자열과 정수형을 + 연산할 수 없다 !!

print("문자열" + str(333)) # 문자열333

이처럼 정수형을 str()을 이용해서 문자열로 변환하고 +연산해야한다. return 문자열

int()

print(333 + "444")

마찬가지로 문자열과 정수형을 + 연산할 수 없다 !!

print(333 + int(444)) #777

이처럼 문자열을 int()로 정수형으로 변환하고 +연산해야한다. return 정수형

실수형 변환 float()

print( 1 + float("2,3")) #3.3
print( 1 + float("23e-1")) #3.3

이 처럼 x.x 형식처럼 고정소수점 방식이나 xe-y처럼 부동소수점 방식으로 되어있어야 float()를 사용할 수 있다. 따라서 문자열로 되어있는 실수를 정수형으로 사용하기 위해서는 먼저 float()로 형변환 int()로 형변환해 사용하여야 한다.

print( 10 + int(float("22.5")) # 32
#"22.5" -> 22.5 -> 22

실수를 반올림 , round()

print( round(2.54 , 1)) # 2.5
print( round(123456 , -3)) #123000

한꺼번에 같은 값 대입하기

a = b = c = 5

오늘 코테 보면서 처음 알았던 ord() 와 chr()

ord()는 인수로 받은 문자의 아스키코드 값을 반환한다. chr()는 인수로 받은 아스키코드 값의 문자를 반환한다.

A의 아스키코드 값 :  65
아스키코드 65의 문자 값 :  A

##반복문
for i in range(ord("a"),ord('z')+1) :
    print(chr(i), end=" ")

ord와 chr()을 이용해서 a부터 z를 출력해보았다.

a b c d e f g h i j k l m n o p q r s t u v w x y z 

오늘 푼 백준 문제에서 ord()를 활용 가능하다.

백준문제 : 1935

print("출력내용" , sep= "~" , end = "~")

sep -> 출력할 요소들의 사이 사이의 들어감 default : 띄어쓰기 end -> 모두 출력하고 난 뒤 들어감 default : 줄바꿈(\n)

a=1
b=2
print("결과 :",a,b)

때문에 print(a,b)는 print(a,b, sep=" ", end="\n") 이다

결과 : 1 2
(커서위치)

코테에서 자주쓰는 출력문

print("".join(반복가능한 문자열))

배열이나 스택 등 반복가능한 문자열을 출력할 때 사용했다.

보통 print를 통해서 배열이나 스택같은 리스트형을 출력하면 [ '요소1' , '요소2' , ~ ] 이렇게 출력이 되지만 join을 이용하여 출력을 한다면 -> 요소1 요소2 <- 이런 형식으로 출력이 가능하다.

print("\n" or " " or " , " .join(반복가능한 문자열))

위와 같이 여러 방식으로 응용 가능하다.

입력

파이썬에서 입력은 간단하게 받을 수 있다

input()

input을 통해서 사용자로부터 입력을 받을 수 있다. input()은 사용자의 입력을 문자열로 리턴한다.

따라서 사용자가 숫자를 입력했다면 int()나 계산하고 싶은 형으로 형변환 해주어야 한다.

user_num_int = int(input())
uesr_num_float = float(input())

코테 입력문

코딩 테스트에서는 시간이 제한되어있으므로 한 줄 씩 입력받는 형태에서는 input()보다 다른 입력 방식을 선호한다.

import sys

user_input = sys.stdline.readline()

readline()은 input()과 다르게 사용자가 입력을 다하고 입력하는 엔터키(줄바꿈문자)까지 문자열로 인식하고 리턴하기 때문에 이 줄바꿈문자를 제거해주어야 한다

import sys

user_input = sys.stdline.readline().strip()

또한, 한번에 여러 개의 입력을 받고 싶을 때는 map을 사용하면 된다.

a, b = map(int,sys.stdline.readline().split())

입력된 각 값들이 int로 형변화하여 공백을 기준으로 a,b에 들어가게 된다.

추후 공부하면서 알게된게 있다면 추가하겠습니다

1-2학년 때인가 자료구조 수업시간에 배웠던 기억이 난다.

보자마자 이 문제는 스택을 사용해야겠다고 생각했다. Vv

백준 문제 바로가기

import sys

k = int(input())
exp = input()
expLen = len(exp)
num = []
exp_stk = []
i, j = 0,0
for _ in range(k) :
    a =int(sys.stdin.readline().strip())
    if(a<100) :
        num.append(a)
if k>=1 and k<=26 and expLen <100:
    for i in range(expLen) :
        if 'A' <= exp[i] <= 'Z' :
            exp_stk.append(num[ord(exp[i])-ord('A')])
            j+=1
            if(j>=k) : j = k-1
        else :
            a = exp_stk.pop()
            b = exp_stk.pop()
            if exp[i] == '+':
                res = float(b) + float(a)
                exp_stk.append(res)
            elif exp[i] == '-':
                res = float(b) - float(a)
                exp_stk.append(res)
            elif exp[i] == '*':
                res = float(b) * float(a)
                exp_stk.append(res)
            elif exp[i] == '/':
                res = float(b) / float(a)
                exp_stk.append(res)

    print("{:.2f}".format(exp_stk.pop()),end="")

문제 구현은 앞 키로거보다 쉬웠다.

하지만 틀렸습니다가 계속 떴다...?

어이가없네...

틀린 코드는

  if 'A' <= exp[i] <= 'Z' :
            exp_stk.append(num[ord(exp[i])-ord('A')])

피연산자를 만났을 때 스택에 append하는 부분이었다,

나는 이 부분을

 if exp[i] >= "A" and exp[i] <="Z" :
               exp_stk.append(num[j])
            j+=1
            if(j>=k) : j = k-1

피연자와 상관없이 강제로 잡았다. 즉 A나 B,C와 상관없이 피연산자의 순서대로 입력받은 수가 저장된 배열의 인덱스를 옮겼다.

하지만 이 문제가 원하는 것은 피연사자에 따라서 인덱스가 자동으로 결정되는 것이었다.

충격 쓰발

ord() -> 입력받은 문자를 아스키코드로 바꿔주는 함수이다.

즉, 피연산자의 아스키코드값을 인덱스로 변환해주는 것인데, 이를 위해서는 0부터 시작하는 배열 인덱스 특성상 A(65) - A(65)를 해주어야 0부터 시작할 수 있다,

따라서 A(65)를 빼주어야 원활하게 피연사자에 따라서 입력받은 수가 저장된 배열의 인덱스를 결정할 수 있다.

백준 5397번 바로가기

처음에는 배열로 접근하여 문제를 해결하고자 하였다.

이거말고도 두 페이지 더 있음

하지만 시간초과<- 욘 석이 계속 나왔다

이유는 배열로 구현하고자 했을 때, insert와 dle() 할 때 배열의 요소들이 한 자리씩 밀리거나 당겨지거나 할때 시간이 O(1)이 아닌 O(N)으로 들기 때문이다.

따라서 이 문제는 자료구조 중에서 배열이 아닌 다른 자료구조를 사용하여야 했다.

맨 처음에는 스택과 연결리스트를 생각해서 풀려고했지만, 배열로도 충분히 할 수 있을 것 같다는 생각이 들어 배열로 길을 잡고 시작했다.

3-4시간 동안 머가리를 박아보니 느껴지는 점이 있다.

코딩테스트는 "시간", 즉 결과만이 아닌 효율 또한 중요하게 생각해야할 요소라는 것이다. 이 문제는 배열로도 구현 가능했지만 스택과 연결리스트를 사용해서 문제를 해결하는 것이 더 빠른 시간안에 결과를 도출할 수 있었다.

고작 별 2개짜리에 이렇게 박아대니 큰일났다 증말

또한, 중요한 요소가 "조건" 이다.

스택을 이용하여 구현을 다하고 파이참으로 반례까지 찾아보면서 틀린 것이 없나 찾아보았지만 결과가 모두 잘 나왔다. 하지만 백준에서는 "틀렸습니다"가 계속 나왔다.

내가 조건을 잘못썼나? 생각하고 조건을 다시 보았지만 전혀 감이 잡히는게 없었다.

혹시나 하고 대문자, 소문자, 숫자 (비밀번호에 해당하는 부분)을 스택에 append하는 코드를 유심히 보았다.

   if ((pw[i] <= "Z" and pw[i] >= 'A') or 
           (pw[i] <= 'z' and pw[i] >= 'a') 
           or (pw[i] >= "1" and pw[i] <="9")):
                ans.append(pw[i])

사실 지금도 뭐가 다른지 모르겠다.

입력한 비밀번호는 문자열이니까 숫자도 당연히 문자 취급하는 것이 아닌가??

라고 생각했지만 그냥 한번 else로 빼볼까 하고 돌려보니까 잘됐다...?

조건과 사용할 자료구조 잘 정하기