record_01.log

[백준 19238][python] 스타트 택시

Sat, 16 Oct 2021 08:26:55 GMT

문제

스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다.

택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다.

M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을 태워 목적지로 이동시키는 일을 M번 반복해야 한다. 각 승객은 스스로 움직이지 않으며, 출발지에서만 택시에 탈 수 있고, 목적지에서만 택시에서 내릴 수 있다.

백준이 태울 승객을 고를 때는 현재 위치에서 최단거리가 가장 짧은 승객을 고른다. 그런 승객이 여러 명이면 그중 행 번호가 가장 작은 승객을, 그런 승객도 여러 명이면 그중 열 번호가 가장 작은 승객을 고른다. 택시와 승객이 같은 위치에 서 있으면 그 승객까지의 최단거리는 0이다. 연료는 한 칸 이동할 때마다 1만큼 소모된다. 한 승객을 목적지로 성공적으로 이동시키면, 그 승객을 태워 이동하면서 소모한 연료 양의 두 배가 충전된다. 이동하는 도중에 연료가 바닥나면 이동에 실패하고, 그 날의 업무가 끝난다. 승객을 목적지로 이동시킨 동시에 연료가 바닥나는 경우는 실패한 것으로 간주하지 않는다.

입력

첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다.

다음 줄부터 N개의 줄에 걸쳐 백준이 활동할 영역의 지도가 주어진다. 0은 빈칸, 1은 벽을 나타낸다.

다음 줄에는 백준이 운전을 시작하는 칸의 행 번호와 열 번호가 주어진다. 행과 열 번호는 1 이상 N 이하의 자연수이고, 운전을 시작하는 칸은 빈칸이다.

그다음 줄부터 M개의 줄에 걸쳐 각 승객의 출발지의 행과 열 번호, 그리고 목적지의 행과 열 번호가 주어진다. 모든 출발지와 목적지는 빈칸이고, 모든 출발지는 서로 다르며, 각 손님의 출발지와 목적지는 다르다.

출력

모든 손님을 이동시키고 연료를 충전했을 때 남은 연료의 양을 출력한다. 단, 이동 도중에 연료가 바닥나서 다음 출발지나 목적지로 이동할 수 없으면 -1을 출력한다. 모든 손님을 이동시킬 수 없는 경우에도 -1을 출력한다.

해결방법

가장 가까운 승객을 찾는 함수 find를 생성한다

*현재 택시 위치로부터 모든 위치까지의 거리를 측정하고 출발점에 있는 승객의 위치 중 가장 가까운 위치를 찾는다 2. 목적지까지 이동한다 3. 도착한 승객을 저장하는 suc 배열을 수정한다.

코드

from collections import deque

n, m, gas = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

taxi_i, taxi_j = map(int, input().split())
taxi_i -= 1
taxi_j -= 1

start = []
end = []
for _ in range(m):
    a, b, c, d = map(int, input().split())
    start.append((a-1, b-1))
    end.append((c-1, d-1))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

#도착한 고객을 확인하는 배열
suc = [0]*m

#가장 가까운 승객을 찾는 함수
def find():
    visit = [[-1]*n for _ in range(n)]
    queue = deque([(taxi_i, taxi_j)])
    visit[taxi_i][taxi_j] = 1

    while queue:
        r, c = queue.popleft()

        for k in range(4):
            nx = r + dx[k]
            ny = c + dy[k]

            if 0<=nx



[백준 2615][python] 오목
Sat, 16 Oct 2021 07:36:11 GMT
문제
같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.
입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.
입력
19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.
출력
첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.
해결방법

연속된 바둑알을 확인하기 위해서는 현재 위치의 오른쪽, 아래 왼쪽, 아래, 아래 오른쪽 네 방향을 확인하면 된다.
만일 바둑알이 있다면 네 방향을 탐색하고 같은 색이 있다면 다른 색이 있을때까지 탐색한다.
같은 색의 바둑알이 다섯개 있다면 육목을 확인하기 위해 처음 탐색을 시작한 부분의 이전 바둑알의 색을 찾는다.

유의할 점
다섯개의 바둑알 중에서 가장 왼쪽에 있는 바둑알을 찾기 위해 위치를 저장하는 Loc 배열을 추가했다.
코드

board = []

for _ in range(19):
    board.append(list(map(int, input().split())))

#검은 바둑알은 1, 흰 바둑알은 2

dx = [0, 1, 1, 1]
dy = [1, 1, 0, -1]

def check():
    for i in range(19):
        for j in range(19):
            visit = [[0]*19 for _ in range(19)]
            if board[i][j] > 0: #아직 확인해보지 않은 칸이라면
                #print(i, j)
                visit[i][j] = 1
                result = [(i, j)]

                for k in range(4):
                    cnt = 1 # 연속되는 바둑알을 세기 위한 변수
                    nx = i + dx[k]
                    ny = j + dy[k]

                    while 0<=nx<19 and 0<=ny<19 and visit[nx][ny] == 0 and board[i][j] == board[nx][ny] : #다음칸에 색이 같은 알이 있다면
                        cnt += 1
                        visit[nx][ny] = 1
                        result.append((nx, ny))
                        nx += dx[k]
                        ny += dy[k]

                    if cnt == 5:
                        bx = i - dx[k]
                        by = j - dy[k]
                        if 0<=bx<19 and 0<=by<19 and board[bx][by] == board[i][j]: #육목이 되는 경우
                            continue
                        else:
                            return board[i][j], result, k
    return 0, 0, 0

a, b, k= check()
if a > 0:
    if k == 2:
        print(a)
        print(b[0][0]+1, b[0][1]+1)
    else:
        loc = sorted(b, key = lambda x: (x[1], -x[0]))
        print(a)
        print(loc[0][0]+1, loc[0][1]+1)
else:
    print(a)



[백준 21609][python] 상어중학교
Tue, 12 Oct 2021 15:19:26 GMT
문제
상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록이 있다. 일반 블록은 M가지 색상이 있고, 색은 M이하의 자연수로 표현한다. 검은색 블록은 -1, 무지개 블록은 0으로 표현한다. (i, j)는 격자의 i번 행, j번 열을 의미하고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸 (r1, c1)과 (r2, c2)를 인접한 칸이라고 한다.
블록 그룹은 연결된 블록의 집합이다. 그룹에는 일반 블록이 적어도 하나 있어야 하며, 일반 블록의 색은 모두 같아야 한다. 검은색 블록은 포함되면 안 되고, 무지개 블록은 얼마나 들어있든 상관없다. 그룹에 속한 블록의 개수는 2보다 크거나 같아야 하며, 임의의 한 블록에서 그룹에 속한 인접한 칸으로 이동해서 그룹에 속한 다른 모든 칸으로 이동할 수 있어야 한다. 블록 그룹의 기준 블록은 무지개 블록이 아닌 블록 중에서 행의 번호가 가장 작은 블록, 그러한 블록이 여러개면 열의 번호가 가장 작은 블록이다.
오늘은 이 게임에 오토 플레이 기능을 만드려고 한다. 오토 플레이는 다음과 같은 과정이 블록 그룹이 존재하는 동안 계속해서 반복되어야 한다.

크기가 가장 큰 블록 그룹을 찾는다. 그러한 블록 그룹이 여러 개라면 포함된 무지개 블록의 수가 가장 많은 블록 그룹, 그러한 블록도 여러개라면 기준 블록의 행이 가장 큰 것을, 그 것도 여러개이면 열이 가장 큰 것을 찾는다.
1에서 찾은 블록 그룹의 모든 블록을 제거한다. 블록 그룹에 포함된 블록의 수를 B라고 했을 때, B2점을 획득한다.
격자에 중력이 작용한다.
격자가 90도 반시계 방향으로 회전한다.
다시 격자에 중력이 작용한다.
격자에 중력이 작용하면 검은색 블록을 제외한 모든 블록이 행의 번호가 큰 칸으로 이동한다. 이동은 다른 블록이나 격자의 경계를 만나기 전까지 계속 된다.

입력
첫째 줄에 격자 한 변의 크기 N, 색상의 개수 M이 주어진다.
둘째 줄부터 N개의 줄에 격자의 칸에 들어있는 블록의 정보가 1번 행부터 N번 행까지 순서대로 주어진다. 각 행에 대한 정보는 1열부터 N열까지 순서대로 주어진다. 입력으로 주어지는 칸의 정보는 -1, 0, M이하의 자연수로만 이루어져 있다.
출력
첫째 줄에 획득한 점수의 합을 출력한다
해결방법

크기가 가장 큰 블록 그룹을 찾는 함수 find()를 작성한다. 여기서 가장 큰 블록 그룹이 여러개이고, 무지개 블록의 수가 같은 경우를 꼼꼼히 따져 코드를 작성한다 ( 이 부분에서 실수가 가장 많이 나왔다.) 나의 경우, 각 변수에 비교대상이 되는 값들을 매번 저장했고, 가장 큰 블록 그룹이 바뀌는 경우 변수를 바로바로 갱신해줬다.
중력이 작용하는 함수를 작성한다.
90도 반시계 방향으로 회전하는 함수를 작성한다.

코드
from collections import deque
# 게임은 크기가 N×N인 격자에서 진행
n, m = map(int, input().split())

board = []
for _ in range(n):
    board.append(list(map(int, input().split())))

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]


# 1. 크기가 가장 큰 블록 그룹을 찾는다. 
def find(board):
    # 여러 블록 그룹 중 가장 큰 블록 그룹의 크기
    max_size = 0
    # 가장 큰 블록 그룹의 번호
    max_group = -1
    # 가장 큰 블록 그룹이 가지고 있는 무지개 블록의 수
    max_rainbow = 0
    # 블록 그룹의 번호
    count = 0
    # bfs를 위한 큐
    queue = deque([])
    # 각 그룹 블록에 포함되는 좌표 저장
    his = {} 
    #레인보우 블록의 좌표 저장
    rainbow_loc = {}
    #일반 블록의 좌표 저장
    block_loc = {}
    # 방문 배열 초기화
    visit = [list(0 for _ in range(n)) for _ in range(n)]

    for i in range(n):
        for j in range(n):
            # 블록 그룹의 크기
            size = 1
            # 블록 그룹에 포함된 레인보우 블록
            rainbow = 0

            # 일반 블록이라면
            if 0 < board[i][j] <= m and visit[i][j] == 0: 
                visit[i][j] = 1
                count += 1
                queue.append([i, j])
                color = board[i][j] # 시작하는 일반 블록의 색상 저장
                his[count] = [[i, j]]
                block_loc[count] = [[i, j]]
                rainbow_loc[count] = []

                while queue:
                    #print(queue)
                    r, c = queue.popleft()
                    #visit[r][c] = 1
                    # print("start", color, r, c, count)

                    for k in range(4):
                        nx = r + dx[k]
                        ny = c + dy[k]

                        if 0<=nx




[백준 21610][python] 마법사 상어와 비바라기
Tue, 12 Oct 2021 15:07:26 GMT
문제
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기를 크기가 N×N인 격자에서 연습하려고 한다. 격자의 각 칸에는 바구니가 하나 있고, 바구니는 칸 전체를 차지한다. 바구니에 저장할 수 있는 물의 양에는 제한이 없다. (r, c)는 격자의 r행 c열에 있는 바구니를 의미하고, A[r][c]는 (r, c)에 있는 바구니에 저장되어 있는 물의 양을 의미한다.
격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다. 마법사 상어는 연습을 위해 1번 행과 N번 행을 연결했고, 1번 열과 N번 열도 연결했다. 즉, N번 행의 아래에는 1번 행이, 1번 행의 위에는 N번 행이 있고, 1번 열의 왼쪽에는 N번 열이, N번 열의 오른쪽에는 1번 열이 있다.
비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다. 구름은 칸 전체를 차지한다. 이제 구름에 이동을 M번 명령하려고 한다. i번째 이동 명령은 방향 di과 거리 si로 이루어져 있다. 방향은 총 8개의 방향이 있으며, 8개의 정수로 표현한다. 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 이동을 명령하면 다음이 순서대로 진행된다.
모든 구름이 di 방향으로 si칸 이동한다.
각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
구름이 모두 사라진다.
2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다. 물복사버그 마법을 사용하면, 대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 (r, c)에 있는 바구니의 물이 양이 증가한다.
이때는 이동과 다르게 경계를 넘어가는 칸은 대각선 방향으로 거리가 1인 칸이 아니다.
예를 들어, (N, 2)에서 인접한 대각선 칸은 (N-1, 1), (N-1, 3)이고, (N, N)에서 인접한 대각선 칸은 (N-1, N-1)뿐이다.
바구니에 저장된 물의 양이 2 이상인 모든 칸에 구름이 생기고, 물의 양이 2 줄어든다. 이때 구름이 생기는 칸은 3에서 구름이 사라진 칸이 아니어야 한다.
M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 구해보자.
입력
첫째 줄에 N, M이 주어진다.
둘째 줄부터 N개의 줄에는 N개의 정수가 주어진다. r번째 행의 c번째 정수는 A[r][c]를 의미한다.
다음 M개의 줄에는 이동의 정보 di, si가 순서대로 한 줄에 하나씩 주어진다.
출력
첫째 줄에 M번의 이동이 모두 끝난 후 바구니에 들어있는 물의 양의 합을 출력한다.
해결방법

구름의 위치가 이동하고 비를 내린 후, 구름이 사라지고 새로운 구름이 만들어지는 move 함수를 만든다. 큐를 만들어 구름의 위치를 저장하도록 코드를 작성했다

여기서 유의할 점!! 새로운 구름은 new_cloud라는 matrix에 위치를 저장한다. queue에 담아서 in 함수로 확인을 하면 시간초과가 발생하기 때문에 matrix로 바로 위치를 확인하는 것이 좋다.

바구니에 들어있는 물의 양의 합을 계산하는 cal()함수를 구현한다.

코드
from copy import deepcopy
from collections import deque

n, m = map(int, input().split())

#바구니에 있는 물의 양을 입력받는다
board = []
for _ in range(n):
    temp = list(map(int, input().split()))
    board.append(temp)

#비바라기를 시전하면 (N, 1), (N, 2), (N-1, 1), (N-1, 2)에 비구름이 생긴다.
# 현재 구름의 위치를 저장하는 큐
cqueue = deque([(n-1, 0), (n-1, 1), (n-2, 0), (n-2, 1)])

#방향은 총 8개의 방향으로 1번부터 순서대로 다음과 같다 (1부터 시작)
dx = [0, 0, -1, -1, -1, 0, 1, 1, 1]
dy = [0, -1, -1, 0, 1, 1, 1, 0, -1]

def move(d, s):

    #모든 구름이 d방향으로 s칸 이동한다.
    #처음 구름의 수 확인
    cloud_cnt = len(cqueue)
    for _ in range(cloud_cnt):
        r, c = cqueue.popleft() 
        # for _ in range(s): #s 칸 만큼 방향 증가

        for _ in range(s): #s 칸 만큼 방향 증가
            r += dx[d]
            c += dy[d]

            #왼쪽으로 넘어갈 때
            if c < 0:
                c = n-1
            #오른쪽으로 넘어갈 때
            if c >= n:
                c = 0
            #위로 넘어갈 때
            if r < 0:
                r = n-1
            #아래로 넘어갈때
            if r >= n:
                r = 0

        cqueue.append((r, c)) #새로운 구름의 위치 저장

        #각 구름에서 비가 내려 구름이 있는 칸의 바구니에 저장된 물의 양이 1 증가한다.
        board[r][c] += 1

    #구름이 모두 사라지고, 2에서 물이 증가한 칸 (r, c)에 물복사버그 마법을 시전한다.
    #물이 있는 바구니를 new_board에서 확인하고 board를 갱신한다
    new_board = deepcopy(board)

    #대각선을 확인할 k
    k_list = [2, 4, 6, 8]
    #구름의 위치를 확인할 배열
    new_cloud = [[0]*n for _ in range(n)]
    for r, c in cqueue:
        cnt = 0

        for k in k_list:
            nr = r + dx[k]
            nc = c + dy[k]

            if 0<=nr 0:
                cnt += 1

        new_cloud[r][c] = 1
        #대각선 방향으로 거리가 1인 칸에 물이 있는 바구니의 수만큼 물의 양이 증가한다
        board[r][c] += cnt

    #바구니에 저장된 물의 양이 2이상인 모든 칸에 구름이 생기고 물의 양이 2 줄어든다
    #새로운 구름의 위치는 new_cqueue에 저장한다
    new_cqueue = deque([])
    for i in range(n):
        for j in range(n):
            if board[i][j] >= 2 and not new_cloud[i][j]:
                new_cqueue.append((i, j))
                board[i][j] -= 2

    return new_cqueue

#m번의 이동이 끝난 후 바구니에 들어있는 물의 양의 합
def cal():
    ans = 0
    for i in range(n):
        for j in range(n):
            ans += board[i][j]
    return ans


for _ in range(m):
    d, s = map(int, input().split())
    cqueue = move(d, s)

    # print(cqueue)
    # for b in board:
    #     print(b)
    # print("")

print(cal())




[백준 20061][python] 모노미노도미노 2
Tue, 12 Oct 2021 15:00:23 GMT
문제 이해
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.


이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.



블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다.

초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다.

초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다.

행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.


블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력
첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며, t x y와 같은 형태이다.
t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우
블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.
출력
첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.
해결방법

주어진 위치에 블록을 놓는 move 함수를 만든다.
행 또는 열에 모든 블록이 있어 점수를 얻게되는 함수 remove를 만든다.
연한 부분에 블록이 있는 경우를 확인하고 아래 블록을 삭제하는 remove2 함수를 만든다.
남은 블록을 계산한다

코드
from copy import deepcopy

board = [[0]*10 for _ in range(4)]
for i in range(6):
    board.append([0,0,0,0])


#빨간색 칸에 놓인 블록이 이동하는 함수
def move(t, r, c):
    # t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
    if t == 1:
        #초록색으로 떨어지는 코드
        # 1을 더해도 좌표안에 들어가고, 다음 칸이 0이라면
        x, y = r, c
        while x + 1 < 10 and board[x+1][y] == 0:
            x += 1
        board[x][y] = 1

        #좌표 초기화
        x, y = r, c
        #파란색으로 떨어지는 코드
        while y + 1 < 10 and board[x][y+1] == 0:
            y += 1
        board[x][y] = 1

    # t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
    if t == 2:
        x, y = r, c
        #초록색으로 떨어지는 코드
        while x + 1 < 10 and board[x+1][y] == 0 and board[x+1][y+1] == 0:
            x += 1
        board[x][y] = 1
        board[x][y+1] = 1

        x, y = r, c
        #파란색으로 떨어지는 코드
        while y + 2 < 10 and board[x][y+1] == 0 and board[x][y+2] == 0:
            y += 1
        board[x][y] = 1
        board[x][y+1] = 1

    #t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우
    if t == 3:
        x, y = r, c
        #초록색으로 떨어지는 코드
        while x + 2 < 10 and board[x+1][y] == 0 and board[x+2][y] == 0:
            x += 1
        board[x+1][y] = 1
        board[x][y] = 1

        x, y = r, c
        #파란색으로 떨어지는 코드
        while y + 1 < 10 and board[x][y+1] == 0 and board[x+1][y+1] == 0:
            y += 1
        board[x][y] = 1
        board[x+1][y] = 1

#행, 열이 차면 삭제하는 함수
def remove():
    score = 0
    #초록색 부분 확인
    for i in range(6, 10):
        green_cnt = 0
        for j in range(0, 4):
            if board[i][j] == 1:
                green_cnt += 1
        if green_cnt == 4:
            score += 1
            board[i] = [0, 0, 0, 0]

    #위에 있는 블록들 내리기
    for k in range(9, 3, -1):

        temp = k
        while temp+1 < 10 and board[temp+1] == [0, 0, 0, 0] :
            temp += 1

        #이동할 공간이 남아있었다면
        if temp != k:
            #위에 있는 행을 아래로 복사
            board[temp] = board[k]
            #위에 있는 행은 초기화
            board[k] = [0, 0, 0, 0]

    #파란색 부분 확인
    for i in range(6, 10):
        blue_cnt = 0
        for j in range(0, 4):
            if board[j][i] == 1:
                blue_cnt += 1
        if blue_cnt == 4:
            score += 1
            for k in range(4):
                board[k][i] = 0

    #왼쪽에 있는 블록들 오른쪽으로 넘기기
    for k in range(9, 3, -1):
        temp = k
        while temp + 1 < 10:
            #각 열 마다 0의 수를 확인하는 check 변수 생성
            check = 0
            for c in range(4):
                if board[c][temp+1] == 0:
                    check += 1
            #print(k, temp, check)
            #만일 모든 열이 비어있다면
            if check == 4:
                #다음 열로 이동한다
                temp += 1
            #열이 비어있지 않다면
            else:
                break
        if temp != k:
            #열을 이동시킨다
            #print(k, "->", temp)
            for c in range(4):
                board[c][temp] = board[c][k]
                board[c][k] = 0
    return score

#연한색 구간의 칸만큼 삭제하는 함수
def remove2():
    #초록 연한 구간 확인
    cnt = 0
    for i in range(4, 6):
        if board[i] != [0, 0, 0, 0]:
            cnt += 1

    #연한 구간 행의 수 만큼 아래 삭제
    for c in range(cnt):
        for k in range(9, 4, -1):
            board[k] = board[k-1]

    #위에 새롭게 0을 추가해야함
    for c in range(1, cnt+1):
        board[3+c] = [0, 0, 0, 0]

    #파란 연한 구간 확인
    cnt = 0
    for i in range(4, 6):
        chk = 0
        for c in range(4):
            if board[c][i] == 0:
                chk += 1
        if chk != 4:
            cnt += 1

    #연한 구간 열의 수 만큼 오른쪽 삭제
    for c in range(cnt):
        for k in range(9, 4, -1):
            for j in range(4):
                board[j][k] = board[j][k-1]

    #왼쪽에 새롭게 0을 추가해야함
    for c in range(1, cnt+1):
        for j in range(4):
            board[j][3+c] = 0


answer = 0
n = int(input())
for _ in range(n):
    t, x, y = map(int, input().split())

    move(t, x, y)
    # print("move")
    # for b in board:
    #     print(b)
    # print("")

    answer += remove()
    # print("remove1")
    # for b in board:
    #     print(b)
    # print("")

    remove2()
    # print("remove2")
    # for b in board:
    #     print(b)
    # print("")

    # for b in board:
    #     print(b)
    # print("")

print(answer)

count = 0
for i in range(4):
    for j in range(10):
        if board[i][j]:
            count += 1
for i in range(6, 10):
    for j in range(4):
        if board[i][j]:
            count += 1
print(count)

유의할 점
연한 칸의 블록을 삭제하고 연한 칸은 0으로 초기화해줘야 한다. 이 부분에서 실수가 있었다.



[백준 21608][python] 상어초등학교
Wed, 29 Sep 2021 14:20:22 GMT
문제
상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호가 매겨져 있고, (r, c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (N, N)이다.
선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다. 이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다. 한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1을 만족하는 두 칸이 (r1, c1)과 (r2, c2)를 인접하다고 한다.

비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.

... 중간생략 ...
이제 학생의 만족도를 구해야 한다. 학생의 만족도는 자리 배치가 모두 끝난 후에 구할 수 있다. 학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
학생의 만족도의 총 합을 구해보자.
(https://www.acmicpc.net/problem/21608)
해결방법

비어있는 칸 중에서 좋아하는 학생이 인접한 칸을 세는 함수를 작성한다.
인접한 칸이 여러개라면 그 결과 중 인접한 빈칸이 제일 많은 칸을 고르는 함수를 작성한다.
점수를 계산하는 함수를 작성한다.

풀이 1
1, 2 조건을 만족하는 함수를 각각 만들어서 로직을 구성했다.
여기서 count라는 리스트를 만들어 인접한 곳의 정보를 저장하는데, 초기값을 -1이라고 정해야 chk 변수 결과와 겹치지 않기 때문에 유의해서 코드를 작성해야 한다.
n = int(input())

info = []
info_dic = {}
for _ in range(n**2):
  a, b, c, d, e = map(int, input().split())
  info.append([a, [b, c, d, e]])
  info_dic[a] = [b, c, d, e]

# print(info)

board = [ list(0 for _ in range(n)) for _ in range(n)]

# print(board)

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# 1. 좋아하는 학생이 많은 칸
def favorite(student, friend):
    # student가 좋아하는 학생 리스트 - friend
    #   print(student, friend)
  count = [ list(-1 for _ in range(n)) for _ in range(n)]
  max_chk = -1

  for i in range(n):
    for j in range(n):

      if board[i][j] == 0: #해당 칸에 자리가 있다면
        chk = 0
        for k in range(4):
          x = i + dx[k]
          y = j + dy[k]

          if 0<=x 0:
        ans += 10**(chk-1)
  return ans

for inf in info:
  rlt1 = favorite(inf[0], inf[1:][0])

  if len(rlt1) > 1:
    rlt2 = empty(rlt1)
    mx, my = rlt2[0][0], rlt2[0][1]
  else:
    mx, my = rlt1[0][0], rlt1[0][1]

  board[mx][my] = inf[0]

print(cal())
풀이 2
1, 2 조건에 따라 함수를 만들다 보면 겹치는 부분이 보인다. 한번에 인접한 곳에 좋아하는 친구가 있는지, 빈칸이 있는지 계산할 수 있다.
n = int(input())

member = {}
for _ in range(n**2):
    a, b, c, d, e = map(int, input().split())
    member[a] = [b, c, d, e]

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

arr = [list(0 for _ in range(n)) for _ in range(n)]
def main(a):

    max_count_friend = -1
    max_count_empty = -1
    fit_i, fit_j = 0, 0

    for i in range(n):
        for j in range(n):
            if arr[i][j] == 0:
                count_friend = 0
                count_empty = 0

                for k in range(4):
                    x = i + dx[k]
                    y = j + dy[k]

                    if 0<=x max_count_friend:
                    fit_i = i
                    fit_j = j
                    # 수정부분 : max friend의 count가 기준이 되어야 다른 칸에서 빈 칸이 제일 많은 곳 판단가능
                    max_count_friend = count_friend
                    max_count_empty = count_empty
                #2. 1을 만족하는 칸이 여러개인 경우
                if count_friend == max_count_friend:
                    if count_empty > max_count_empty:
                        fit_i = i
                        fit_j = j
                        # 수정부분
                        #max_count_friend = count_friend
                        max_count_empty = count_empty

    arr[fit_i][fit_j] = a

for key in member.keys():
    main(key)

    # print(key)
    # for a in arr:
    #     print(a)
    # print("")

answer = 0
for i in range(n):
    for j in range(n):
        cnt = 0
        for k in range(4):
            x = i + dx[k]
            y = j + dy[k]

            if 0<=x= 1:
            answer += 10**(cnt-1)

print(answer)



Union-find (disjoint-set) 알고리즘, [백준 1717] 집합의 표현
Tue, 28 Sep 2021 14:09:16 GMT
Union-find 알고리즘을 이해하고 예제 문제를 풀어본다
Union-find (disjoint-set) 알고리즘
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
즉, 다수의 노드들 중에 연결된 노드를 찾거나 합칠 때 사용하는 알고리즘

예시



Union-find 구현

초기화 : N개의 원소가 각각의 집합에 포함되어 있도록 초기화
union : 두 원소가 주어질 때,  이들이 속한 두 집합을 하나로 합친다 
find : 어떤 원소가 주어질 때,  원소가 속한 집합 반환 

유니온 파인드 구현 방식은 1. 배열 2. 트리 방식이 있다

배열 ( 시간복잡도 O(n) )
  원소의 크기만큼 배열을 초기화한다.
  union : 배열의 모든 원소를 순회하면서 하나의 번호를 나머지 하나로 교체한다.

  아래는 대략 코드의 흐름


    def init(n):
        data = list(range(n))

    def find(index):
        return data[index]

    def union(x, y):
        x = find(x)
        y = find(y)

        if x == y:
            return

        for i in range(n):
            if find(i) == y:
                data[i] = x
   하지만 배열 방식은 시간 복잡도가 크다는 단점이 있다.

트리 (log n)
트리 구조는 세 가지 형태로 나뉜다.


union-by-size : 원소의 수가 적은 집합을 많은 집합의 하위트리로 추가
union-by-height : 트리의 높이가 작은 집합을 큰 집합의 서브트리로 추가
path comprehension : find 연산 비용을 낮춘다.

대표적으로 unio-by-size 형태를 보자

주어진 원소의 개수만큼 사용하지 않는 값을 생성한다
data = [ -1 for _ in range(n) ]

루트 노드의 인덱스를 찾는다
def find(idx):
  value = data[idx]
  if value < 0:
      return idx
  return find(value) #최상위의 루트 노드 반환

루트 노드의 인덱스가 다르다면 리스트의 값이 더 낮은 것(size가 큰 것)을 찾아서 큰것을 더해준다

작은 걸 큰 것의 인덱스로 바꾼다
def union(x, y):
  x = find(x)
      y = find(y)

    if x== y:
        return
    if data[x] < data[y]:
        data[x] += data[y]
        data[y] = x
    else:
        data[y] += data[x]
        data[x] = y


즉, 루트 노드의 값은 계속해서 음수가 되고 나머지는 루트 노드의 값을 가리키게 된다.
그럼 예제 문제를 풀어보자
[백준 1717] 집합의 표현 (python)

문제
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.


입력
첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)


아이디어


index 번호를 가진 리스트 arr을 만든다.
find 함수로 해당 노드의 루트 노드를 찾아낸다
여기서 부모 노드를 갱신해주는 과정이 필요하다 (시간 단축을 위해!!!!)


union 함수로 루트 노드가 더 작은 집합에 큰 집합을 합치는 과정을 추가한다


코드import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline



n, m = map(int, input().split())
arr = [ i for i in range(n+1)]
def find(idx):
    global arr
    value = arr[idx]
if value == idx:
     return idx

#부모 노드 갱신
arr[idx] = find(value)
return arr[idx]
def union(a, b):
    global arr
    #루트 노드를 찾는다
    x = find(a)
    y = find(b)
if x == y:
    return

if x < y:
    arr[y] = x
else:
    arr[x] = y
for _ in range(m):
    a, b, c = map(int, input().split())
    if a == 0:
        union(b, c)
    if a == 1:
        if find(b) == find(c):
            print("YES")
        else:
            print("NO")
    #print(arr)
```

결과


참고자료 - https://brownbears.tistory.com/460



var, let, const 비교
Fri, 24 Sep 2021 00:59:35 GMT

var
변수 재선언이 가능하다
let, const
변수 재선언이 불가능하다

let은 변수에 재할당이 가능하지만, const는 변수의 재선언/재할당이 모두 불가능하다.
// let
    let name = 'bathingape'
    console.log(name) // bathingape

    let name = 'javascript'
    console.log(name) 
    // Uncaught SyntaxError: Identifier 'name' has already been declared

    name = 'react'
    console.log(name) //react

// const
    const name = 'bathingape'
    console.log(name) // bathingape

    const name = 'javascript'
    console.log(name) 
    // Uncaught SyntaxError: Identifier 'name' has already been declared

    name = 'react'
    console.log(name) 
    //Uncaught TypeError: Assignment to constant variable.

참고자료
https://velog.io/@bathingape/JavaScript-var-let-const-%EC%B0%A8%EC%9D%B4%EC%A0%90



REST API
Thu, 23 Sep 2021 07:44:55 GMT

REST : 웹 (HTTP) 의 장점을 활용한 아키텍쳐
(REpresentational State Transfer)

REST의 요소
1. Method : http 메소드
    post(create), get(select), put(update), delete(delete)
2. Resource : URI
    + URL과 URI의 차이
        URI : 특정 리소스를 식별하는 통합 자원 식별자
        URL : 컴푸터 네트워크 상에서 리소스가 어디 있는지 알려주기 위한 규약. URI의 서브셋
      _ URI는 식별하고, URL은 위치를 가리킨다_
   모든 것을 Resource(명사)로 표현하고, 세부 Resrouce에는 id를 붙인다.
3. Message : JSON, XML 형태의 메시지 포맷
REST 특징

Uniform ( 유니폼 인터페이스 )
URI로 지정한 리소스에 대한 조작을 통일되고 한정적인 인터페이스로 수행하는 아키텍처 스타일

Stateless ( 무상태성 )
작업을 위한 상태정보를 따로 저장하고 관리하지 않는다. API서버는 들어오는 요청만을 단순히 처리하면 되기 때문에, 서비스의 자유도가 높아지고 구현이 단순해진다.

Cacheable ( 캐시 가능 )
HTTP라는 기존 웹표준을 그대로 사용하기 때문에, 웹에서 사용하는 기존 인프라를 그대로 활용 가능. 따라서 HTTP가 가진 캐싱 기능을 적용 가능하다.
( 캐싱 - 이미 가져온 데이터나 계산된 결과값의 복사본을 저장함으로써 처리속도를 향상, 향후 요청을 더 빠르게 처리할 수 있다. )

Self-descriptiveness ( 자체 표현 구조 )
REST API 메시지만 보고도 쉽게 이해할 수 있다.

Client-Server 구조
서버 : API제공 / 클라이언트 : 사용자 인증이나 컨텍스트 관리 와 같이 각각의 역할이 구분되어 클라이언트와 서버에서 개발해야할 내용이 명확해지고 서로간 의존성이 줄어든다.

계층형 구조
REST 서버는 다중 계층으로 구성될 수 있으며 보안, 로드 밸런싱, 암호화 계층을 추가해 구조상의 유연성을 둘 수 있고 PROXY, 게이트웨이 같은 네트워크 기반의 중간매체를 사용할 수 있게 한다.


API (Application Programming Interface)
응용프로그램에서 사용할 수 있도록 운영체제나 프로그래밍 언어가 제공하는 기능을 제어할 수 있게 하는 것

참고자료

https://meetup.toast.com/posts/92
https://gyoogle.dev/blog/web-knowledge/REST%20API.html




쿠키와 세션
Thu, 23 Sep 2021 05:09:12 GMT
쿠키와 세션을 사용하는 이유
HTTP 프로토콜 환경의 약점을 보완하기 위해 사용한다.
HTTP 환경의 특징

Connectionless
클라이언트가 요청을 한 후 응답을 받으면 그 연결을 끊어버리는 특징
Stateless
통신이 끝나면 상태 정보를 유지하지 않는 특징
즉, 클라이언트와 첫번째 통신테서 데이터를 주고받았어도 두번째 통신에서는 이전 데이터를 유지하지 않는다.

위 두 특징에 따라 예를 들면 쇼핑몰에서 옷을 구매하려는 경우, 로그인을 했음에도 다른 페이지로 이동할때마다 다시 로그인을 해야하는 상황이 발생한다.
이를 해결하기 위해 쿠키와 세션이 사용된다.
쿠키와 세션

쿠키


클라이언트(브라우저) 로컬에 저장되는 키와 값이 들어있는 작은 데이터 파일

사용자가 따로 요청하지 않아도 request시에 자동으로 request header를 넣어서 자동으로 서버에 전송

사용 예시

방문 사이트에서 로그인 시, "아이디와 비밀번호를 저장하시겠습니까?"
쇼핑몰의 장바구니 기능
자동로그인, 팝업에서 "오늘 더 이상 이 창을 보지 않음" 체크




세션


쿠키를 기반하고 있지만, 사용자 정보 파일을 브라우저에 저장하는 쿠키와 달리 세션은 서버측에서 관리

사용자 정보를 서버에 저장하기 때문에 쿠키보다 보안에 좋지만, 사용자가 많아질수록 서버 메모리를 많이 차지하게 된다.

사용 예시
로그인 같이 보안상 중요한 작업을 수행할 때 사용


쿠키와 세션의 차이




Cookie
Session



저장위치
클라이언트
서버


저장형식
text
object


만료시점
쿠키 저장시 설정
정확한 시점을 모름


리소스
클라이언트의 리소스
서버의 리소스


용량제한
한 도메인 당 20개, 한 쿠키당 4KB
제한없음


속도
세션보다 빠르다
쿠키보다 느리다


보안
세션보다 안좋다
쿠키보다 좋다



세션의 만료시점
클라이언트가 로그아웃하거나, 설정한 시간동안 반응이 없을경우 무효화 되기 때문에 정확한 시점을 알 수 없다.


참고자료

https://interconnection.tistory.com/74
https://gyoogle.dev/blog/web-knowledge/Cookie%20&%20Session.html




브라우저
Thu, 23 Sep 2021 04:38:37 GMT
브라우저 주요 기능

사용자가 선택한 자원(html, pdf, image 등 다양한 형태)을 서버에 요청하고 브라우저에 표시

브라우저는 html, css 명세에 따라 html 파일을 해석해서 표시, 명세는 웹 표준화 기구인 W3C(World wide web Consortium)에서 정한다


브라우저의 기본 구조


사용자 인터페이스
주소표시줄, 이전/다음 버튼, 북마크 등 사용자가 활용하는 서비스들 ( 요청한 페이지를 보여주는 창을 제외한 나머지 부분 )

브라우저 엔진
사용자 인터페이스와 렌더링 엔진 사이의 동작 제어


3. 렌더링 엔진
요청한 콘텐츠 표시
(html 요청이 들어오면 html, css를 파싱해서 화면에 표시한다) 

통신
http 요청과 같은 네트워크 호출에 사용
(플랫폼의 독립적인 인터페이스로 구성)

UI 백엔드
플랫폼에서 명시하지 않은 일반적 인터페이스. 콤보 박스 창같은 기본적 장치를 그린다

자바스크립트 해석기
자바스크립트 코드를 해석하고 실행

자료 저장소
쿠키 등 모든 종류의 자원을 하드 디스크에 저장하는 계층


렌더링이란
렌더링 엔진은 요청 받은 내용을 브라우저 화면에 표시해준다 ( 기본적으로 html, xml 문서와 이미지를 표시한다 )
렌더링 엔진 종류

크롬, 사파리 : 웹킷 (Webkit) 엔진 사용
파이어폭스 : 게코 (Gecko) 엔진 사용

렌더링 동작 과정


html 파싱
콘텐츠 트리 내부에서 태그를 모두 DOM 노드로 변환
외부 css 파일과 함꼐 포함된 스타일 요소를 파싱

-> "렌더 트리"라고 부르는 또 다른 트리를 생성
렌더트리는 정해진 순서대로 화면에 표시된다.(배치) 이후에 UI 백엔드에서 렌더 트리의 각 노드를 가로지르며 형상을 만드는 그리기 과정 진행

좀 더 나은 사용자 경험을 위해 가능하면 빠르게 내용을 표시하는데, 모든 html을 파싱할 때까지 기다리지 않고 배치와 그리기 과정 시작. 즉, 네트워크로부터 나머지 내용이 전송되기를 기다리는 동시에 받은 내용의 일부를 먼저 화면에 표시한다.

DOM
Document Object Model (문서 객체 모델)
,  와 같은 태그를 자바스크립트가 활용할 수 있는 객체로 만들면 문서 객체가 된다.
즉, DOM은 웹 브라우저가 html페이지를 인식하는 방식을 말한다. (트리구조)
파싱(parsing)
브라우저가 코드를 이해하고 사용할 수 있는 구조로 변환하는 것. 문서를 가지고, 어휘 분석과 구문 분석 과정을 거쳐 파싱 트리를 구축한다.
( 어휘 분석기를 통해 구문 규칙에 따라 문서 구조를 분석하고, 이 과정에서 구문 규칙과 일치하는 노드만 파싱 트리에 추가시킨다.)
파싱 트리를 다시 기계코드 문서로 변환시키는 과정까지 완료되면 최종 결과물이 나오게 된다.
결국 파싱 과정을 거쳐 서버로부터 받은 무서를 브라우저가 이해하고 쉽게 사용할 수 있는 DOM 트리구조로 변환시켜 주는 것
요약


주소창에 url - enter -> 서버에 요청이 전송
페이지에 해당되는 자원들이 보내짐
브라우저는 html, css를 W3C 명세에 따라 해석
렌더링 엔진은 html 파싱해 DOM 트리 구축
다음으로 css 파싱으로 css 정보를 스타일 구조체로 생성
DOM 트리와 스타일 구조체를 연결해 렌더 트리를 만듦. 렌더 트리를 통해 문서가 시각적 요소를 포함한 형태로 구성된 상태
화면에 배치, UI 백엔드가 노드를 돌며 형상을 그림
이때, 빠른 화면 표시를 위해 전송받을 자원을 기다리는 동시에 일부분을 먼저 전송받은 자원의 일부를 화면에 표시한다.


참고자료

https://gyoogle.dev/blog/web-knowledge/%EB%B8%8C%EB%9D%BC%EC%9A%B0%EC%A0%80%20%EB%8F%99%EC%9E%91%20%EB%B0%A9%EB%B2%95.html
https://d2.naver.com/helloworld/59361




[2020 KAKAO BLIND RECRUITMENT]
자물쇠와 열쇠
Thu, 09 Sep 2021 11:54:20 GMT
문제 설명
고고학자인 "튜브"는 고대 유적지에서 보물과 유적이 가득할 것으로 추정되는 비밀의 문을 발견하였습니다. 그런데 문을 열려고 살펴보니 특이한 형태의 자물쇠로 잠겨 있었고 문 앞에는 특이한 형태의 열쇠와 함께 자물쇠를 푸는 방법에 대해 다음과 같이 설명해 주는 종이가 발견되었습니다.
잠겨있는 자물쇠는 격자 한 칸의 크기가 1 x 1인 N x N 크기의 정사각 격자 형태이고 특이한 모양의 열쇠는 M x M 크기인 정사각 격자 형태로 되어 있습니다.
자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있습니다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조입니다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안됩니다. 또한 자물쇠의 모든 홈을 채워 비어있는 곳이 없어야 자물쇠를 열 수 있습니다.
열쇠를 나타내는 2차원 배열 key와 자물쇠를 나타내는 2차원 배열 lock이 매개변수로 주어질 때, 열쇠로 자물쇠를 열수 있으면 true를, 열 수 없으면 false를 return 하도록 solution 함수를 완성해주세요.
제한사항

key는 M x M(3 ≤ M ≤ 20, M은 자연수)크기 2차원 배열입니다.
lock은 N x N(3 ≤ N ≤ 20, N은 자연수)크기 2차원 배열입니다.
M은 항상 N 이하입니다.
key와 lock의 원소는 0 또는 1로 이루어져 있습니다.
0은 홈 부분, 1은 돌기 부분을 나타냅니다.

아이디어

시계방향으로 90도 회전하는 함수 생성
M-1 만큼 상, 하, 좌, 우 셀이 추가된 2차원 배열 new_lock 생성
key를 new_lock에서 움직이면서 lock이 채워졌는지 아닌지 check함수로 비교
만일 채워졌다면 True 반환, 아니면 계속해서 탐색

코드
from copy import deepcopy

#회전함수
def rotation(key):
    #시계방향으로 90도 회전
    rlt = []
    for i in range(len(key)):
        tmp = []
        for j in range(len(key)-1, -1, -1):
            tmp.append(key[j][i])
        rlt.append(tmp)
    return rlt

#홈과 돌기가 모두 맞았는지 확인하는 함수
def check(lock, val, n): # val = m-1
    answer = False
    for i in range(val, n+val):
        for j in range(val, n+val):

            if lock[i][j] == 0 or lock[i][j] == 2: #홈이 안맞으면 false
                return answer
    else:
        answer = True
        return answer


#모든 경우 이동해보는 함수
def move(key, lock):
    #추가해야할 행, 열의 수
    m = len(key)
    n = len(lock)

    #상하좌우 공백 추가한 배열 만들기
    new_lock = []
    for _ in range(m-1):
        new_lock.append([0]*(n+(m-1)*2))

    row = [0]*(m-1)
    for i in range(n):
        new_lock.append(row+lock[i]+row)

    for _ in range(m-1):
        new_lock.append([0]*(n+(m-1)*2))

    #lock에 key 한칸씩 밀어서 비교하기
    for i in range(len(new_lock)-m+1):
        #가로
        #for j in range(len(new_lock)):
        for k in range(len(new_lock)-m+1):
            pan = deepcopy(new_lock)

            #기준 : k
            for a in range(len(key)):
                for b in range(len(key)):
                    pan[i+a][k+b] += key[a][b]

            if check(pan, m-1, n): #다 돌아서 홈이 맞으면
                return True

    return False

def solution(key, lock):
    answer = True
    for i in range(4):
        key = rotation(key)
        if move(key, lock): #홈이 맞으면
            return answer
    else:
        answer = False
    return answer


[2020 KAKAO BLIND RECRUITMENT] 괄호 변환
Tue, 07 Sep 2021 10:08:59 GMT
문제 설명
카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 "콘"은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.
용어의 정의
'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 "균형잡힌 괄호 문자열" 이지만 "올바른 괄호 문자열"은 아닙니다.
반면에 "(())()"와 같은 문자열은 "균형잡힌 괄호 문자열" 이면서 동시에 "올바른 괄호 문자열" 입니다.
'(' 와 ')' 로만 이루어진 문자열 w가 "균형잡힌 괄호 문자열" 이라면 다음과 같은 과정을 통해 "올바른 괄호 문자열"로 변환할 수 있습니다.
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.
"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.
매개변수 설명
p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
만약 p가 이미 "올바른 괄호 문자열"이라면 그대로 return 하면 됩니다.
아이디어

올바른 문자열을 판단하는 함수를 따로 작성한다.
변환 규칙에 따라 하나씩 코드를 작성한다.

코드 (Python)
from collections import deque

#올바른 괄호 문자열 판단
def collect(word):
    if word.count('(') != word.count(')'):
        return False
    queue = deque([word[0]])
    for w in range(1, len(word)):
        if word[w] == ')' and queue:
            if queue[-1] == '(':
                queue.pop()
            else:
                queue.append(word[w])
        elif word[w] == '(' and queue:
            queue.append(word[w])
        else:
            queue.append(word[w])
    if queue:
        #print("queue", queue)
        return False
    else:
        #print("queue", queue)
        return True


def solution(p):
    answer = ''

    # 1. 입력이 빈 문자열일 경우
    if p == '':
        return answer
    else:
        # 2. 두 균형잡힌 문자열 u, v
        u = ''
        v = ''
        for i in range(len(p)):
            u += p[i]
            if u.count('(') == u.count(')'):
                v = p[i+1:]
                break
        # 3. u가 올바른 괄호 문자열이라면
        if collect(u):
            return u + solution(v)
        # 4. u가 올바른 괄호 문자열이 아니라면
        if collect(u)==False:
            answer += '('
            answer += solution(v)
            answer += ')'
            if len(u)>=2:
                tmp = u[1:len(u)-1]
            else:
                tmp = ''

            tmprlt = ''
            for t in tmp:
                if t == '(':
                    tmprlt += ')'
                else:
                    tmprlt += '('
            answer += tmprlt
            return answer

    #return answer


HAE 08.08
Tue, 10 Aug 2021 12:19:01 GMT


오랜만에 서울 야경



[프로그래머스 level2] 소수 찾기
Sat, 07 Aug 2021 12:18:45 GMT
문제
한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.
제한사항
numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
"013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.
입출력 예
numbers    return
"17"    3
"011"    2
입출력 예 설명
예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.
예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.
11과 011은 같은 숫자로 취급합니다.
해결
itertools의 permutations 함수를 이용해서 해결
모든 경우의 수를 구한 후, 소수인지 아닌지 확인한다.
코드
from itertools import permutations

def isPrime(num):
    if num == 0 or num == 1:
        return False

    for i in range(2, num):
        if num%i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    nlist = list(numbers)
    num = []

    for i in range(1, len(numbers)+1):
        temp = list(map(''.join, permutations(nlist, i)))

        for t in temp:
            if int(t) not in num:
                num.append(int(t))

    for n in num:
        if isPrime(n) == True:
            answer += 1

    return answer

''.join(list) 는 리스트를 문자열로 변경




[프로그래머스 level2] 다리를 지나는 트럭
Sat, 07 Aug 2021 10:44:47 GMT
문제
트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다.
예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다.
경과 시간    다리를 지난 트럭    다리를 건너는 트럭    대기 트럭
0    []    []    [7,4,5,6]
12    []    [7]    [4,5,6]
3    [7]    [4]    [5,6]
4    [7]    [4,5]    [6]
5    [7,4]    [5]    [6]
67    [7,4,5]    [6]    []
8    [7,4,5,6]    []    []
따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다.
solution 함수의 매개변수로 다리에 올라갈 수 있는 트럭 수 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭 별 무게 truck_weights가 주어집니다. 이때 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 return 하도록 solution 함수를 완성하세요.
해결
기억 : 모든 다리가 다리를 "지나고 난 후"의 시간을 재야 한다
따라서 brdge를 만들어 이 큐가 빌 때 까지 반복문을 진행한다.
그리고 sum함수를 쓰면 연산 비용이 많아지기 때문에 다리 위 무게를 저장하는 변수를 생성해 계산하는 것이 효율적이다.
코드
from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0]*bridge_length)
    out_truck = []
    summation = 0

    while bridge:
        #print(bridge)
        temp = bridge.popleft()
        summation -= temp

        if truck_weights and truck_weights[0] + summation > weight:
            bridge.append(0)

        elif truck_weights:
            value = truck_weights.pop(0)
            bridge.append(value)
            summation += value

        answer += 1

    return answer
코드를 보면 큰 로직이 이해되기 때문에 자세한 설명은 하지 않았다.



[프로그래머스 level2] 프린터
Sat, 07 Aug 2021 05:26:58 GMT
문제
일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
그렇지 않으면 J를 인쇄합니다.
예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.
현재 대기목록에 있는 문서의 중요도가 순서대로 담긴 배열 priorities와 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지를 알려주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.
제한사항
현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.
인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.
(링크 - https://programmers.co.kr/learn/courses/30/lessons/42587)
해결
(중요도, location)의 형태로 새로운 큐에 값들을 넣는다.
왼쪽부터 하나씩 값을 뺀 후, 남은 값들의 중요도와 비교한다.
만일 더 중요한 값이 있다면 다시 큐에 값을 넣고 순회를 멈춘다.
모든 값이 중요도가 낮다면 location값을 비교해 답을 찾는다.
코드
from collections import deque

def solution(priorities, location):
    answer = 0
    queue = deque([])
    idx = 0

    for priority in priorities:
        queue.append((priority, idx))
        idx += 1

    while queue:
        number = queue.popleft()
        for i in range(len(queue)):
            compare = queue[i][0]
            if number[0] < compare:
                queue.append(number)
                break
        else:
            answer += 1
            if location == number[1]:
                break 

    return answer


[백준 1244][python] 스위치 켜고 끄기
Fri, 06 Aug 2021 07:57:33 GMT
문제
1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. <그림 1>에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.
남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. <그림 1>과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 <그림 2>와 같이 3번, 6번 스위치의 상태를 바꾼다.
여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.
스위치 번호    ①    ②    ③    ④    ⑤    ⑥    ⑦    ⑧
스위치 상태    0    1    0    1    0    0    0    1
<그림 1>
예를 들어 <그림 2>에서 여학생이 3을 받았다면, 3번 스위치를 중심으로 2번, 4번 스위치의 상태가 같고 1번, 5번 스위치의 상태가 같으므로, <그림 3>과 같이 1번부터 5번까지 스위치의 상태를 모두 바꾼다. 만약 <그림 2>에서 여학생이 4를 받았다면, 3번, 5번 스위치의 상태가 서로 다르므로 4번 스위치의 상태만 바꾼다.
스위치 번호    ①    ②    ③    ④    ⑤    ⑥    ⑦    ⑧
스위치 상태    0    1    1    1    0    1    0    1
<그림 2>
스위치 번호    ①    ②    ③    ④    ⑤    ⑥    ⑦    ⑧
스위치 상태    1    0    0    0    1    1    0    1
<그림 3>
입력으로 스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어진다. 학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램을 작성하시오
(링크 - https://www.acmicpc.net/problem/1244)
출력 check
스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다. 예를 들어 21번 스위치가 있다면 이 스위치의 상태는 둘째 줄 맨 앞에 출력한다. 켜진 스위치는 1, 꺼진 스위치는 0으로 표시하고, 스위치 상태 사이에 빈칸을 하나씩 둔다.
해결
단순 시뮬레이션이라 주어진 조건에 따라 해결했다.
여자 부분이 까다로울 수 있는데, left, right 변수를 지정해서 status의 두 위치가 같으면 스위치 상태를 바꾸고 다르면 바로 break해서 탐색을 중지하도록 코드를 작성했다.
코드
switch  = int(input())
status = list(map(int, input().split()))

student = int(input())
student_status = [(map(int, input().split())) for _ in range(student)]

def change(loc):
    if status[loc] == 0:
        status[loc] = 1
    else:
        status[loc] = 0

for s, num in student_status:
    if s == 1: #남자라면
        for i in range(switch):
            if (i+1)%num == 0:
                #print(i)
                change(i)

    if s == 2: #여자라면
        num -= 1
        change(num)

        left = num - 1
        right = num + 1
        while 0 <= left and right < switch:
            if status[left] == status[right]:
                change(left)
                change(right)
                left -= 1
                right += 1
            else:
                break

temp = 0
for stat in status:
    print(stat, end = ' ')
    temp += 1
    if temp == 20:
        print("")
        temp = 0
print("")
로직은 다 맞았는데 출력 방식을 실수해서 몇번 틀렸다.
문제를 꼼꼼히 보는 습관을 기르자!



[백준 2798][python] 블랙잭
Fri, 06 Aug 2021 07:28:22 GMT
문제
카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.
한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.
김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.
이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.
N장의 카드에 써져 있는 숫자가 주어졌을 때, M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 구해 출력하시오.
(링크 - https://www.acmicpc.net/problem/2798)
해결
중복되지 않는 카드 3개를 골라 합을 구하는 모든 경우의 수를 구한다.
isused - 해당 카드를 선택 했는지 안했는지 기록하는 배열
카드를 넣고 계산하고 빼면서 모든 경우의 수를 results에 저장한다.
마지막으로, m과 제일 가까운 수를 탐색하면서 찾아간다.
코드
N, M = map(int, input().split())
arr = list(map(int, input().split()))

#첫째 줄에 M을 넘지 않으면서 M에 최대한 가까운 카드 3장의 합을 출력한다.
results = []
isused = [0]*N
summation = 0

def sum(isused, summation, n):
    if n == 3:
        results.append(summation)
        return

    for i in range(N):
        if isused[i] == 0:
            isused[i] = 1
            summation += arr[i]
            sum(isused, summation, n+1)
            isused[i] = 0
            summation -= arr[i]

sum(isused, summation, 0)
ans = 0
before = 10000000000
for res in results:
    if abs(M-res) < before and res <= M:
        before = abs(M-res)
        ans = res
print(ans)
더 좋은 방법이 있을거 같은데, 백트래킹 문제를 풀고와서 비슷한 방식으로 풀었다.



HAE 08.05
Thu, 05 Aug 2021 15:10:24 GMT


8월 5일 기록
저녁을 먹고 소화 겸 걷자 해서 걷다보니 7시가 되었다.
나온김에 일몰도 보고 가자는 생각으로 30분 더 걸었다. 덕분에 더 많이 걷고 좋은 풍경을 많이 볼 수 있었다.

	Cookie	Session
저장위치	클라이언트	서버
저장형식	text	object
만료시점	쿠키 저장시 설정	정확한 시점을 모름
리소스	클라이언트의 리소스	서버의 리소스
용량제한	한 도메인 당 20개, 한 쿠키당 4KB	제한없음
속도	세션보다 빠르다	쿠키보다 느리다
보안	세션보다 안좋다	쿠키보다 좋다

record_01.log

[백준 19238][python] 스타트 택시

문제

입력

출력

해결방법

코드

[백준 2615][python] 오목

문제

입력

출력

해결방법

코드

[백준 21609][python] 상어중학교

문제

입력

출력

해결방법

코드

[백준 21610][python] 마법사 상어와 비바라기

문제

입력

출력

해결방법

코드

[백준 20061][python] 모노미노도미노 2

문제 이해

입력

출력

해결방법

코드

유의할 점

[백준 21608][python] 상어초등학교

문제

해결방법

풀이 1

풀이 2

Union-find (disjoint-set) 알고리즘, [백준 1717] 집합의 표현

Union-find 알고리즘을 이해하고 예제 문제를 풀어본다

Union-find (disjoint-set) 알고리즘

Union-find 구현

[백준 1717] 집합의 표현 (python)

var, let, const 비교

REST API

REST의 요소

REST 특징

API (Application Programming Interface)

쿠키와 세션

쿠키와 세션을 사용하는 이유

HTTP 환경의 특징

쿠키와 세션

쿠키와 세션의 차이

브라우저

브라우저 주요 기능

브라우저의 기본 구조

렌더링이란

렌더링 엔진 종류

렌더링 동작 과정

요약

[2020 KAKAO BLIND RECRUITMENT] 자물쇠와 열쇠

문제 설명

제한사항

아이디어

코드

[2020 KAKAO BLIND RECRUITMENT] 괄호 변환

문제 설명

용어의 정의

매개변수 설명

아이디어

코드 (Python)

HAE 08.08

[프로그래머스 level2] 소수 찾기

문제

해결

코드

[프로그래머스 level2] 다리를 지나는 트럭

문제

해결

코드

[프로그래머스 level2] 프린터