정렬 알고리즘이란?

어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 방법들을 정렬 알고리즘이라고 한다.      

문제풀이

이번 주는 강의실 배정(골드 5), 버블 정렬(골드 1)이라는 문제들을 풀어보았다.

강의실 배정(골드 5)

해당 문제는 아래 링크에서 풀어볼 수 있다. https://www.acmicpc.net/problem/11000

전체코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
times = sorted([list(map(int, input().split())) for _ in range(N)])

rooms = list()
heappush(rooms, times[0][1])

for i in range(1, N):
    if times[i][0] >= rooms[0]:
        heappop(rooms)
    heappush(rooms, times[i][1])

print(len(rooms))

S와 T를 입력받을 때마다 둘을 리스트에 담아, 모든 S와 T로 이루어진 리스트들을 다시 times 라는 리스트 안에 담고 sorted()를 이용해 정렬했다. rooms라는 최소값을 쉽게 얻을 수 있는 heap트리를 이용해 rooms의 최상단 노드와 times[i]의 시작 시간(times[i][0])을 비교했다.

만약 times[i][0]이 rooms[0]보다 크거나 같으면 해당 rooms[0]의 수업이 끝난 후 times[i]의 수업을 시작할 수 있는 것이므로, rooms[0]를 삭제해주고 times[i][1]을 추가해준다.

만약 times[i][0]이 rooms[0]보다 작으면 위 상황과 달리 rooms[0]를 삭제하지 않고 그냥 rooms에 times[i][1]를 추가해준다.

위 방법대로 하면 rooms의 길이가 강의실의 최소 개수를 뜻한다.      

버블 정렬(골드 1)

해당 문제는 아래 링크에서 풀어볼 수 있다. https://www.acmicpc.net/problem/1838

전체 코드

import sys

input = sys.stdin.readline

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

not_sort = {}
sort = {}
answer = 0

for i in range(N):
    not_sort[A[i]] = i

A.sort()

for i in range(N):
    sort[A[i]] = i

for i in A:
    answer = max(answer, not_sort[i] - sort[i])

print(answer)

i는 리스트 A의 정렬 전과 후를 비교하여 가장 많이 이동한 요소의 인덱스 값 차이가 정답이 되는 문제다.

따라서 리스트 A를 정렬하기 전의 인덱스 값이 필요하다. 키로 리스트 A의 값을 전달하면 정렬하기 전의 인덱스가 값으로 나오는 not_sort라는 딕셔너리를 만들었다.

그 다음, 리스트 A를 sort()를 이용해 정렬했다. not_sort와 마찬가지로 키로 배열 A의 값을 전달하면 정렬한 후의 인덱스가 값으로 나오는 sort라는 딕셔너리도 만들었다.

for문을 통해 리스트 A의 값을 하나씩 꺼내어 인덱스 차이를 max()를 통해 기존 최대값과 계속 비교해 나가며 정답을 찾는다.

DFS와 BFS란?

DFS와 BFS는 그래프를 탐색하는 방법이다. DFS는 Depth First Search, BFS는 Breadth First Search의 약자로서 말그대로 각각 깊이와 너비를 우선으로 그래프를 탐색하는 방법이다.      

문제풀이

이번 주는 안전영역(실버 1), 미로탐색(실버 1), DFS와 BFS(실버 2)라는 문제들을 풀어보았다.

안전 영역(실버 1)

해당 문제는 아래 링크에서 풀어볼 수 있다. https://www.acmicpc.net/problem/2468

입력받은 graph에서 가장 높은 높이를 찾아 mostHigh에 저장한다. 그리고 0(비가 아예 안오는 경우)부터 mostHigh-1(가장 높은 높이빼고 다 잠기는 경우)의 범위에서 for문을 통해 각 높이를 한 번씩 제공하며 해당 높이에 대해 안전 영역의 수를 찾는다.

전체코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
graph = [list(map(int, input().split())) for _ in range(N)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
mostHigh = 0

for i in range(N):
    for j in range(N):
        if graph[i][j] > mostHigh:
            mostHigh = graph[i][j]

def bfs(mostHigh):
    answer = 0
    for level in range(0, mostHigh):
        visited = [[0] * N for _ in range(N)]
        safearea = 0
        for i in range(N):
            for j in range(N):
                if graph[i][j] > level and visited[i][j]==0:
                    queue = deque()
                    queue.append((i, j))
                    visited[i][j] = 1

                    while queue:
                        x, y = queue.popleft()

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

                            if 0<=nx<N and 0<=ny<N and graph[nx][ny] > level and visited[nx][ny]==0:
                                visited[nx][ny] = 1
                                queue.append((nx, ny))
                    safearea += 1

        if safearea > answer:
            answer = safearea
    return answer

print(bfs(mostHigh))

미로탐색(실버 1)

해당 문제는 아래 링크에서 풀어볼 수 있다. https://www.acmicpc.net/problem/2178       현재 위치에서 상하좌우를 탐색한다. 이동할 수 있는 위치(graph[nx][ny]==1 이고 맵 밖을 벗어나지 않는 좌표)면 현재 위치에 저장되어 있는 값에 1을 더한 값을 이동할 위치에 저장하는 방식으로 해결했다.

전체 코드

import sys
from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]

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

def bfs(x, y):
    loc_queue = deque()
    loc_queue.append((x, y))

    while loc_queue:
        x, y = loc_queue.popleft()

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

            if 0<=nx<N and 0<=ny<M and graph[nx][ny]==1:

                loc_queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1

    return graph[N-1][M-1]


print(bfs(0, 0))
print(*graph, sep='\n')

DFS와 BFS(실버 2)

해당 문제는 아래 링크에서 풀어볼 수 있다. https://www.acmicpc.net/problem/1260       각각 DFS와 BFS를 이용해 방문기록을 저장하는 배열을 통해 쉽게 해결할 수 있다.

전체 코드

import sys
from collections import deque

input = sys.stdin.readline

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

visited_dfs = [0]*(N+1)
visited_bfs = [0]*(N+1)

def dfs(graph, V, visited_dfs):
    visited_dfs[V] = 1
    print(V, end=' ')

    for next in graph[V]:
        if visited_dfs[next] == 0:
            dfs(graph, next, visited_dfs)

def bfs(graph, V, visited_bfs):
    queue = deque([V])
    visited_bfs[V] = 1

    while queue:
        now = queue.popleft()
        print(now, end=' ')

        for next in graph[now]:
            if visited_bfs[next] == 0:
                queue.append(next)
                visited_bfs[next] = 1

for i in range(M):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
    graph[a].sort()
    graph[b].sort()

dfs(graph, V, visited_dfs)
print()
bfs(graph, V, visited_bfs)

Implementation이란?

구현은 머릿속으로 어찌저찌 해결하는 방법을 떠올릴 수 있으나 코드로 표현하는 것이 어려운 문제 유형을 칭한다.      

문제풀이

이번 주는 컨베이어 벨트 위의 로봇(골드 4), 연구소(골드 4)라는 문제들을 풀어보았다.

컨베이어 벨트 위의 로봇(골드 4)

문제 설명은 다음과 같다. https://www.acmicpc.net/problem/20055 rotate()는 배열을 시계 방향(default)으로 회전시켜 저장하는 기능을 가지고 있다. 벨트의 내구도와 로봇의 위치를 나타내는 배열인 durability와 robots를 회전하는 벨트에 맞춰 rotate()를 사용하면 쉽게 풀 수 있다.

전체코드

import sys

from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())
durability = deque(list(map(int, input().split())))
robots = deque([False]*N)

level = 0

while 1:
    level += 1

    # 과정 1
    durability.rotate()
    robots.rotate()

    robots[N-1] = False

    # 과정 2
    for i in range(N-2, 0, -1):
        if robots[i] == True:
            if robots[i+1] == False and durability[i+1] > 0:
                robots[i+1] = True
                robots[i] = False
                durability[i+1] -= 1

    robots[N-1] = False

    # 과정 3
    if durability[0] != 0:
        robots[0] = True
        durability[0] -= 1

    # 과정 4
    if durability.count(0) >= K:
        break


print(level)

연구소(골드 4)

문제 설명은 다음과 같다. https://www.acmicpc.net/problem/14502       빈 공간에 대해서 empth_rooms에 좌표를 저장하고, empty_rooms에서 combinations를 통해 3개씩 뽑는 모든 경우에 대해서 벽을 세우고 바이러스를 퍼뜨려 보았다. 바이러스를 퍼뜨린 방법은 아래와 같다.

3개의 벽을 세운 해당 경우에 대해 BFS를 통해 바이러스를 퍼뜨리고 안전 영역의 수를 세어 임시로 저장했다. 그리고 combinations를 통한 모든 경우에 대해서 answer에 저장된 값보다 현재 임시로 저장한 값이 크면 임시값을 answer에 저장하는 방식을 사용했다.

전체 코드

from itertools import combinations
from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
answer = 0
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]


def virus(graph):
    tmp_graph = [row[:] for row in graph]

    virus_loc_queue = deque()

    for i in range(N):
        for j in range(M):
            if tmp_graph[i][j]==2:
                virus_loc_queue.append((i, j))

    while virus_loc_queue:
        x, y = virus_loc_queue.popleft()
        for i in range(4):
            new_x, new_y = x + dx[i], y + dy[i]

            if 0<=new_x<N and 0<=new_y<M and tmp_graph[new_x][new_y]==0:
                tmp_graph[new_x][new_y] = 2
                virus_loc_queue.append((new_x, new_y))

    return sum(row.count(0) for row in tmp_graph)


empty_rooms = []
for i in range(N):
    for j in range(M):
        if graph[i][j]==0:
            empty_rooms.append((i, j))

for walls in combinations(empty_rooms, 3):
    for x, y in walls:
        graph[x][y]=1

    answer = max(answer, virus(graph))

    for x, y in walls:
        graph[x][y]=0

print(answer)

유튜브로 리액트를 공부하다가 필수라고 생각되는 JS 문법을 보고! 공유하고 싶어 포스팅하려고 한다.

'코딩알려주는누나'라는 유튜브를 보고 참고했으며 항상 지식을 공유하려 노력해주시는 분들께 감사를 표하고 싶다.

1. Object Shorthand Assignment

2. Destructuring

3. Spread

...을 통해 주소값을 통한 참조가 아닌 아예 다른 객체를 생성 및 복사할 수 있다. person3은 객체의 주소값만 복사할 수 있다. 즉, person 객체를 참조하는 변수가 두 개가 되는 것이다.(person, person3) 하지만 person2는 값은 같지만 아예 다른 객체를 생성한다. 심지어 name: "noona" 처럼 복사해오는 객체의 일부를 변경할 수도 있다.

4. Ternary Operator

person이라는 사전 안에 내용이 있으면 name을 출력하고 내용이 없으면 특정 문자열을 출력해야하는 상황을 가정해보자.

삼항연산자를 알기 전에 생각할 수 있는 코드다. if-else문을 통해 각각의 상황을 기록해줘야 하는 수고로움이 생긴다.

대학교 동아리 지인들을 모아 알고리즘 스터디를 만들었다. 운영 방식은 다음과 같다. 알고리즘 스터디를 운영하고 싶은 사람들은 참고하면 좋을 것 같다.      

운영방식

주마다 아래 목차에 따라 한 목차씩 다룬다. 만약 해당 목차에 대해 더 공부할 필요성이 느껴지면, 스터디원이 다같이 협의에 따라 해당 목차 스터디를 한 주 더 연장하는 등의 조치를 취한다.

목차는 다음과 같다. ('이것이 코딩 테스트다' 라는 책을 참고했다.)

1. 그리디
2. 구현
3. DFS/BFS
4. 정렬
5. 이진탐색
6. 다이나믹 프로그래밍
7. 최단경로
8. 그래프
9. 그밖에 기출문제들... 10,11,12....

첫 번째, 이전 스터디에서 풀기로 정한 문제들을 풀어온다. 꼭 완전히 다 해결하지 않아도 된다. 최대한 할 수 있는 만큼만 해오자.

두 번째, 자신의 코드를 설명할 간단한 자료를 만들어 발표한다. 자료를 만든다는 건 자신의 코드를 리와인드할 수도 있고, 나의 포트폴리오를 쌓는 데에도 의의가 있으니 귀찮더라도 작성하는 것이 좋다. 당부하고 싶은건 개인사정으로 인해 미참석인원이 발생 시, 참석하지 못하는 인원은 본인의 코드설명 자료를 반드시 미리 제출하도록 한다.

세 번째, 한 스터디원의 발표가 끝나면 해당 스터디원의 코드를 리뷰하는 시간을 갖는다. 해당 스터디원의 코드를 개선해줄 수도 있고, "내가 푸는 방법 외에도 이런 식으로 풀 수도 있구나!"라는 깨달음의 시간을 가질 수도 있다. 만약 해결하지 못한 문제가 있을 시, 통과하지 못한 코드를 다른 스터디원들과 함께 검토하며 코드를 수정하는 시간을 갖는다. 필자는 다른 사람의 코드를 이해하고 수정해주는 과정이 알고리즘 스터디의 핵심이라고 생각한다.

네 번째, 스터디원 중 한 사람이 다음주에 다룰 목차를 주제로 발표를 진행한다. 알고리즘에 대한 지식이 전혀 없는 상태에서 문제 해결은 힘들다. 발표를 듣는 사람도, 발표자료를 준비하는 사람도 예습 및 복습의 기회가 될 수 있다.

마지막으로, 다음 스터디까지 풀어올 문제를 정한다. 문제는 3개 정도를 정한다. 이건 스터디마다 재량껏 정하면 된다. 스터디원의 평균적인 수준을 고려해 3개 정도의 문제를 각각 상, 중, 하 난이도로 정하면 좋을 것 같아서 그렇게 정해봤다. 문제 해결은 백준으로 진행했다. 이유는 문제 수도 많고, 유형별로 묶어서 해당 알고리즘을 연습해볼 수 있는 장점도 있으며, 티어 개념을 통해 나의 수준과 문제 수준을 쉽게 파악할 수 있기에 스터디에 적합하다고 생각했다.      

그리디 알고리즘(Greedy Algorithm)이란?

그리디 알고리즘이란, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식을 말한다.

지금 당장 가질 수 있는 최고의 이익을 따라가는 알고리즘이기 때문에 탐욕 알고리즘이라고도 부른다.    

문제풀이

알고리즘 스터디 규칙에 따라 상, 중, 하 난이도로 다음 세 문제를 정해 풀어보았다.    

캠핑(브론즈 1)

여기서 핵심은 sys 모듈을 통한 빠른 입력. input은 prompt 메세지를 입력받고 맨 뒤 개행문자를 삭제하는 기능을 실행하기 때문에 상황에 따라 sys.stdin.readline을 사용 시 시간을 크게 단축할 수 있다.

전체 코드

import sys
input = sys.stdin.readline

count = 0
while 1:
    L, P, V = map(int, input().split())
    if L==P==V==0:
        break
    answer = (V//P)*L
    if (V-(V//P)*P) > L:
        answer += L
    else:
        answer += (V-(V//P)*P)
    count += 1
    print(f"Case {count}: {answer}")

설탕 배달(실버 4)

여기서 핵심은 함수 사용. 함수는 return을 사용하면 함수를 즉각 종료하기 때문에, 위 문제풀이 과정에서 for문을 벗어나는 부분과 -1을 반환해야 하는 부분에서 유용하게 쓸 수 있다.

전체 코드

import sys
input = sys.stdin.readline

N = int(input())

def min_bag(N):
    for i in range(N//5, -1, -1):
        tmp = N - 5*i
        if tmp%3==0:
            return i + tmp//3
    return -1


print(min_bag(N))

카드 정렬하기(골드 4)

여기서 핵심은 Heap 트리다. Heap 트리는 최댓값과 최솟값을 찾는 연산을 빠르게 할 수 있는 완전이진트리다.

Heap 트리 구조를 사용하기 위해서는 Heapq 모듈을 써야 한다. 이 문제를 해결하기 위해 필요한 함수는 다음과 같다.

Heapify(리스트) : 기존의 리스트를 넣으면 해당 리스트를 Heap 트리 구조로 바꿔준다.

Heappop(Heap 트리 구조의 리스트) : 해당 리스트의 트리 최상단 노드를 트리에서 제거하며 그 값을 반환한다.

Heappush(Heap 트리 구조의 리스트, 추가할 값) : 해당 리스트의 트리에 값을 추가한다.

전체 코드

from heapq import heapify, heappop, heappush
import sys
input = sys.stdin.readline

N = int(input())
cards = []
answer = 0

for _ in range(N):
    cards.append(int(input()))

heapify(cards)

for _ in range(N-1) :
    tmp1 = heappop(cards)
    tmp2 = heappop(cards)
    answer += tmp1 + tmp2
    heappush(cards, tmp1 + tmp2)

print(answer)

압박감이 들었다. 누군가는 내 나이를 얘기하며 "무슨 23살이 벌써 압박감을 느끼냐!" 라고 할 수 있다. 나는 "그때 그 시간에 이런 걸 더 했으면.." 하는 후회를 나중에 느끼고 싶지 않다는 것, 중학교 때부터 겪어온 진로로 인한 답답함에서 벗어나고 싶은 것, 내 가족들이 자랑할만한 존재가 되고 싶다는 것 등등.. 많은 이유로 매일 쉴 새 없이 압박감을 느끼고 있다. 그래서 나는 이 벨로그를 통해, 내가 써온 게시글들을 보며 잘하고 있다고 스스로를 위로하고 싶었다.

프로그래밍 분야는 넓고.. 나는 그중에서도 더 관심이 가는 분야를 찾기 위해 소위 말하는 '삽질'을 여기저기 하고 다녔다. 가슴이 턱 막히도록 답답한 상황이 자주 찾아오는 데 그럴 때마다 내가 찾는 건 구글링이었다. 구글링을 통해 해답을 찾다 보면 각 분야의 개발자분들께서 정성스럽게 적어놓은 글들을 마주하곤 한다. 그 글들을 읽으며 든 생각은 나도 저런 개발자가 되어 나 같은 이들을 도와주고 싶다는 생각이었다. 나도 나 같은 '프로 삽질러'들에게 힘이 되어주고 싶다.

마지막으로 나를 기록하고 싶다. 시간은 빠르게 지나가지만, 과거의 나를 챙겨줄 수 있는 사람은 나밖에 없다. 훗날 벨로그를 보며 지금 이 순간의 열정을 다시 떠올릴 수 있도록, 비록 이걸 보며 떠올린 기억이 기쁜 일이든 슬픈 일이든 훗날의 내가 만들어질 수 있는 자양분이라 생각하며 웃어넘길 수 있도록 열심히 기록할 것이다.