아스

Application(앱)이란

django-admin startproject myproject

이 커맨드로 장고 프로젝트(project)를 처음 만들면 기본 디렉토리에 asgi, wsgi, settings 등의 파일이 생성된다.

이 파일들은 프로젝트 전역에서 사용되는 파일로, 하나의 앱(application)에 소속되어 있지 않다. 

django-admin startapp myapp

여기서 이 커맨드로 myproject에 소속된 myapp 앱을 만들면 프로젝트 디렉토리 기준으로 /myapp 이라는 디렉토리가 생기고, 이 디렉토리 안에는 apps, models, views, tests 등 여러 파일이 생긴다. 이 파일들은 해당 myapp 앱 안에 소속되어 있다. 

장고 앱은 하나의 프로젝트 안에서도 여러 역할이나 기능이 나누어질 수 있기 때문에, 그 기능이나 역할별로 코드를 효율적으로 작성하는 데 도움이 된다. 

App 선언하고 사용하기

startapp 커맨드로 앱을 만든 뒤에는 이 앱을 장고가 인식할 수 있게 해야 한다. 

프로젝트 디렉토리의 settings.py의 INSTALLED_APPS라는 리스트 형식의 변수에다가 해당 앱 디렉토리 까지의 경로를 추가해 준다. 

이때 앱 디렉토리까지의 경로만 입력해도 장고가 앱을 인식할 수 있는 이유는, 앱 안의 apps.py에 기본적으로 AppConfig 클래스가 정의되어 있기 때문이다. 

이 클래스는 AppConfig라는 클래스를 상속하여야 하고, 한 앱당 최소 1개 이상은 있어야 한다. 

다만 꼭 apps.py 파일 안에 있을 필요는 없다. AppConfig 클래스는 해당 앱의 바깥에다가 정의해도 상관없다. 대신에 이 경우 INSTALLED_APPS에는 해당 AppConfig 클래스까지의 경로를 정확히 명시해 주어야 한다. 

AppConfig는 각 장고 앱에 관련된 메타 데이터를 저장하는 클래스이다. 장고에서는 각 앱마다 있는 AppConfig 클래스를 상속한 이 AppConfig 객체에 메타 데이터를 저장한다. 

반면 Application 객체는 없다. 그냥 AppConfig 객체에 각 앱의 실행과 관리에 필요한 여러 정보를 저장할 뿐이다. 

AppConfig class

name: 프로젝트 디렉토리에서 해당 앱까지의 경로이며, 모든 앱은 이 경로가 서로 달라야 한다. 

label: 각 앱을 구분하는 이름이고, 이 이름도 서로 달라야 한다. 

verbose_name: human-readable 이름이다. 이 이름은 서로 겹칠 수도 있다. 

path: 파일 시스템에서 해당 앱까지의 경로이다. 

default: 하나의 앱에 여러 AppConfig 클래스가 있을 때, 어떤 것을 기본으로 사용할지 지정하는 boolean 필드이다. 

default_auto_field: 만약 앱 내에서 모델을 생성한다면, 그 모델의 AutoField를 어떤 타입으로 할지를 지정한다. 기본값은 BigAutoField이다. 

앱이 로딩되는 순서

1. 맨 처음 장고가 시작된다. (즉 django.setup() 이 실행된다.)

2. settings.py 파일에 선언된 변수들을 import 한다. 

3. 이때 INSTALLED_APPS 안에 선언된 앱들을 위에서 아래로 차례대로 import 한다. 이 과정에서 각 앱의 AppConfig 인스턴스가 생성된다. 

4. 각 앱에 있는 모델이 있다면 그 모델들을 import 한다. 

5. 각 앱의 AppConfig의 메소드인 ready()를 호출한다. 이 ready()가 호출되면 비로소 앱은 실행을 위해 준비된 상태가 된다. ready() 메소드는 override해서 각 AppConfig 클래스마다 새로 정의할 수 있다. 이 메소드가 실행 중일 때는 앱이 아직 준비되지 않은 상태이기 때문에, DB에 접근하는 코드 등은 지양해야 한다. 이 경우 AppRegistryNotReady 에러가 발생할 수 있다. 

식의 값을 최소로 만드는 방법은 처음으로 -가 나왔을 때, 그 - 뒤의 값은 모두 빼는 것이다. 

따라서 입력을 받은 수식에서 첫 번째 -가 몇 번째 인덱스에 존재하는지를 찾고, 그 인덱스를 기준으로 앞의 값은 A, 뒤의 값은 B라고 하자. 

그러면 A-B가 수식에서 나올 수 있는 최소 값이 된다. 만약 -이 없다면 식에서 숫자 값들만 추출해준 뒤 그 값들을 모두 더해주면 된다. 

풀이

import sys
input = sys.stdin.readline

commands = input()
if commands.find("-") == -1:
    nums = list(map(int, commands.split("+")))
    print(sum(nums))
else:
    index = commands.find("-")
    a = commands[:index]
    b = commands[(index+1):]
    sum_a = sum(list(map(int, a.split("+"))))
    sum_b = sum(list(map(int, b.replace("+", "-").split("-"))))
    print(sum_a-sum_b)

그래프는 2차원 배열이나 collections 라이브러리의 defaultdict() 타입으로 선언해준다. 

bfs 방식으로 그래프를 탐색하되, 각 시작점마다 dist 배열을 선언해서 해당 노드를 탐색하기까지 몇 개의 노드를 거쳤는지를 표시해주고, sum()으로 그 거리들을 모두 더해준다. 

이때 sum() 0번째 노드를 제외하는 이유는 노드는 1번째 부터 N번째까지 있기 때문이다. 

마지막으로 각 노드마다 get_dist라는 bfs 탐색을 하는 함수를 호출하면서 값을 비교하고, 거리의 합이 더 작은 노드를 min_number 값으로 바꿔 주면서 for문을 1번 순회하면 된다. 

풀이

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

N, M = map(int, input().split())
graph = defaultdict(list)

for _ in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    
def get_dist(num):
    dist = [-1] * (N+1)
    dist[num] = 0
    Q = deque([num])
    while Q:
        elem = Q.popleft()
        for node in graph[elem]:
            if dist[node] == -1:
                Q.append(node)
                dist[node] = dist[elem] + 1
    return sum(dist[1:])

min_dist = sys.maxsize
min_number = 101

for i in range(1, N+1):
    bacon_dist = get_dist(i)
    if bacon_dist < min_dist:
        min_dist = bacon_dist
        min_number = i
    elif bacon_dist == min_dist:
        min_number = min(i, min_number)
        
print(min_number)

리스트의 매 원소마다 해당 원소보다 작은 고유한 원소들이 몇 개인지 세서 계산하는 방식을 쓰면 시간 초과가 나는 문제였다. 

prefix sum 방식과 유사하게, 해당 원소보다 작은 개수인 고유한 원소의 개수가 몇 개인지를 미리 unique_list 배열에 저장해 두고, 정답 배열에 이 값을 추가하는 방식으로 시간초과를 막을 수 있었다. 

import sys
from collections import defaultdict
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

unique_list = defaultdict(lambda: 0)
for index, a in enumerate(sorted(list(set(arr)))):
    unique_list[a] = index

ans = []
for a in arr:
    ans.append(str(unique_list[a]))
    
print(" ".join(ans))

bfs 또는 dfs 방식으로 그래프를 탐색하면 된다. 

만약 모든 노드가 이어져 있다면, 즉 연결 요소의 개수가 1개라면 그래프 탐색으로 모든 노드를 방문할 수 있을 것이다. 

그게 아니라면 연결 요소의 개수만큼 그래프를 탐색해야 모든 노드를 방문할 수 있을 것이다. 

u, v 노드 사이의 간선을 저장하는 방법은 2차원 배열도 있고 여러 가지가 있으나, 여기서는 collections.defaultdict()을 사용해서 딕셔너리에 노드 값 하나와 노드와 이어진 다른 노드들의 리스트를 키-값으로 맵핑하였다. 

또한 여기서는 그래프의 모든 노드를 순회하면서, 방문하지 않은 노드가 있을 경우 그 노드를 시작점으로 bfs 탐색을 진행하였다. 

한 번 탐색할 때마다 연결 요소의 개수도 증가하므로 ans 변수의 값을 1씩 증가시켰다. 

import sys
from collections import defaultdict, deque

input = sys.stdin.readline
N, M = map(int, input().split())
graph = defaultdict(list)
visited = [False] * (N+1)

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
    
def bfs(start):
    Q = deque([start])
    visited[start] = True
    while Q:
        node = Q.popleft()
        for n in graph[node]:
            if not visited[n]:
                visited[n] = True
                Q.append(n)

ans = 0
for i in range(1, N+1):
    if not visited[i]:
        bfs(i)
        ans += 1

print(ans)

그래프를 탐색하되, bfs나 dfs처럼 연쇄적으로 탐색하지 말고 한 번에 근처에 있는 주변 노드들만 탐색한다. 

연쇄적으로 한 번에 탐색하면 안 되는 이유는 총 탐색하는데 며칠이 걸리는지를 알아내야 하기 때문이다. 

따라서 데크(deque)를 선언하고 인접한 노드를 데크에 추가하는 bfs의 방식을 활용하되, 데크에 새로 인접한 노드들을 추가하지는 않았다. 

즉 한 번 bfs()를 실행할 때마다 익은 토마토 주변의 토마토만 익게 된다. bfs() 함수에서는 배열의 값이 0인 칸들만 1로 바꿔주는 것으로 이를 대신하였다. 

배열의 값이 -1인 경우는 토마토가 없는 것이므로 인접한 토마토가 익는 효과가 나타나지 않는다. 그러므로 배열의 값이 꼭 0일 때만 1로 만들어 주어야 한다. 

ripe_list라는 변수를 선언해서 맨 처음에 익어 있는 토마토를 해당 변수에 추가한다. 

이후에는 bfs()를 실행하면서 맨 처음에 익어 있는 토마토에 의해 새로 익게 된 토마토만 ripe_list 변수에 추가해 준다. 

이런 방식으로 while 문을 실행하면서, 새로 익게 되는 토마토가 없는 경우 탐색을 종료한다. 

while 문에서는 day 값을 1씩 늘려가면서 탐색한다. 이때 day 값을 0으로 하면 0번째 값을 탐색할 때에도 day 값이 1씩 추가되기 때문에, day 값을 -1로 두고 시작한다. 

새로 익게 되는 토마토가 없는 경우, 즉 ripe_list의 값이 없는 경우 while 문을 빠져나오고 난 뒤에는 전체 배열을 순회하면서 값이 0인 칸을 탐색한다. 

만약 값이 0인 칸이 있다면 익지 않은 토마토가 있다는 뜻이므로 토마토가 모두 익지 못한 것이다. 이 경우에는 -1을 출력하고, 나머지 경우에는 while문으로 값을 증가시킨 day 값을 출력한다. 

import sys
from collections import deque
input = sys.stdin.readline

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

def bfs(ripe):
    Q = deque(ripe)
    new_ripe = []
    while Q:
        x, y = Q.popleft()
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            if nx >= N or nx < 0 or ny >= M or ny < 0:
                continue
            if arr[nx][ny] == 0:
                arr[nx][ny] = 1
                new_ripe.append([nx, ny])
    return new_ripe

M, N = map(int, input().split())
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))
    
ripe_list = []
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            ripe_list.append([i, j])

day = -1
while ripe_list:
    ripe_list = bfs(ripe_list)
    day += 1

ripe = True
for i in range(N):
    for j in range(M):
        if arr[i][j] == 0:
            ripe = False
            break
if not ripe:
    print(-1)
else:
    print(day)

문제의 원래 의도는 최소 힙(min heap)을 구현하는 것이나, 문제를 푼 방법을 설명하는 코테 등이 아니라면 파이썬에 구현되어 있는 heapq 라이브러리를 쓰면 쉽게 풀 수 있다. 

heap으로 사용하기 위해서 heap이라는 리스트 변수를 선언했다. 

heap에 원소를 넣기 위해서는 heapq.heappush(heap변수, 추가할 원소) 를 사용한다. 

반대로 heap에서 가장 작은 원소를 빼기 위해서는 heapq.heappop(heap변수)를 사용한다. 

heapq 라이브러리는 최소 힙으로 구현되어 있지만, 최대 힙으로도 사용할 수 있다. 

앞서 heappush 연산을 할 때 추가할 원소의 값을 음수로 넣어주면 양수로는 가장 큰 원소가 가장 작은 원소로 간주되어 맨 마지막에 나오게 된다. 

import heapq
import sys
input = sys.stdin.readline

N = int(input())
heap = []
for _ in range(N):
    command = int(input())
    if command == 0:
        if heap:
            elem = heapq.heappop(heap)
            print(elem)
        else:
            print(0)
    else:
        heapq.heappush(heap, command)

몇 번째로 출력되는지 알아야 할 원소의 초기 인덱스인 M을 사용해서 해당 원소가 현재 몇 번째 인덱스에 있는지를 관찰하였다.

M의 경우 매 시행마다 앞으로 한 칸씩 당겨지므로 1씩 값을 제거하면서 그 값을 배열의 길이로 나눈 나머지를 사용하였다. 그래야 M의 값이 원소의 인덱스 범위를 벗어나지 않고 정확히 원소의 위치를 가리킬 수 있다. 

또한 cnt 변수를 사용해서 원소를 Q에서 제거하고 출력할 때마다 cnt 값을 1씩 증가시켰다. 

매 시행마다 Q(데크)에서 맨 앞의 원소를 뺀 뒤, 해당 원소의 뒤에 있는 원소들 중에서 해당 원소보다 큰 원소가 없으면 해당 원소를 제거했다.

만약 해당 원소보다 큰 원소가 뒤에 있었다면, popleft()로 제거했던 맨 앞의 원소를 다시 append()를 사용해서 배열의 맨 뒤에 넣어주었다. 

import sys
from collections import deque
input = sys.stdin.readline

T = int(input())

for _ in range(T):

    N, M = map(int, input().split())
    Q = deque(list(map(int, input().split())))
    
    if N == 1:
        print(1)
    else:
        cnt = 0
        
        while Q:
            elem = Q.popleft()
            
            if Q and max(Q) > elem:
                Q.append(elem)
            else:
                cnt += 1
                if M == 0:
                    break
            M = (M-1) % len(Q)
                    
        print(cnt)