기록

문제 보기 [사용한 알고리즘] 구현 [문제 접근] 주어진 시뮬레이션을 수행하면서 충돌이 발생하면 어떻게 충돌이 발생했는지 출력해야 합니다. 따라서 로봇들의 정보를 딕셔너리로 관리하였고 이외의 시뮬레이션은 특별한 알고리즘을 사용하지 않고 문제에서 주어진대로 구현하였습니다. [알고리즘] 1. 입력받은 로봇들의 정보를 딕셔너리에 저장합니다. 2. 각 명령을 반복 횟수만큼 수행합니다. 3. 충돌이 일어났다면 충돌이 일어난 상황을 출력하고 충돌이 일어나지 않으면 OK를 출력합니다. [코드] import sys def rotation_left(d): # 왼쪽으로 90도 회전 if d == "N": return "W" elif d == "W": return "S" elif d == "S": return "E" eli..

목표 장기, 중기, 단기 스케줄러를 설명할 수 있다. 스케줄링의 비교 척도를 이해할 수 있다. 선점 스케줄링과 비선점 스케줄링의 차이점을 설명할 수 있다. 다양한 스케줄링의 장단점을 설명할 수 있다. 스케줄링이란? 스케줄링의 넓은 의미는 자원을 효율적으로 사용하기 위해 자원을 사용하는 순서를 결정짓는 작업입니다. 대부분 스케줄링이라고 하면 프로세스의 순서를 결정짓는 작업이라고 생각하는데 이는 스케줄링 중 단기 스케줄링에 해당하는 설명이다. 그렇다면 장기, 중기 스케줄링은 무엇인지 알아보도록 하겠습니다. 장기 스케줄러(Long-Term) 메모리와 디스크 사이의 스케줄링을 담당합니다. 실행할 작업을 준비 큐에서 꺼내 메인 메모리에 적재합니다. 메인 메모리에 적재된 프로세스의 양을 판단하여 조절하는 역할을 합..

문제 보기 [사용한 알고리즘] DP(동적 프로그래밍) [문제 접근] 현재 위치의 최고점은 현재 위치 - 1 행의 다른 열 중 최댓값과 현재 위치의 칸의 값을 합치면 됩니다. [알고리즘] 1. dp 배열 첫 행에 입력받은 land 첫 행 값을 대입합니다. 2. 1행부터 위에서 언급한 문제 접근 방식을 구현합니다. 3. 마지막행까지 2번 과정을 수행한 후 마지막행의 최고점을 출력합니다. [코드] def solution(land): dp = [[0] * 4 for _ in range(len(land))] for i in range(4): dp[0][i] = land[0][i] for i in range(1, len(land)): for j in range(4): if j == 0: dp[i][j] = land..

목표 식사하는 철학자 문제를 해결할 수 있다. 식사하는 철학자 문제란? 철학자 다섯 명이 원형 식탁에 앉아 밥을 먹으려고 합니다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여 있고, 밥을 먹으려 할 땐 다음의 과정을 따릅니다. 왼쪽 젓가락부터 집어 듭니다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때까지 대기합니다. 왼쪽을 들었으면 오른쪽 젓가락을 듭니다. 들 수 없다면 대기합니다. 두 젓가락을 모두 들었다면 일정 시간 동안 식사를 합니다. 식사를 마쳤으면 오른쪽 젓가락을 내려 놓은 후 왼쪽 젓가락을 내려놓습니다. 다시 배고프면 1번부터 진행합니다. 철학자는 프로세스 젓가락은 자원으로 가정한 후 모든 철학자가 왼쪽 젓가락을 들은 상황을 가정해봅시다. 그렇다면 모든 철학자는 오른쪽 젓가락을..

문제 보기 [사용한 알고리즘] 플로이드-워셜 [문제 접근] 물건을 정점, 물건의 무게 비교 결과를 선분으로 표시하여 그래프를 구현합니다. 그래프를 구현하고 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 최단 거리를 계산합니다. 이후 서로 다른 물건이 도달할 수 있으면 비교 결과를 알 수 있고, 도달할 수 없으면 비교 결과를 확인할 수 없다고 생각하였습니다. [알고리즘] 1. 물건의 비교 결과를 이용해서 그래프를 구현합니다. 2. 플로이드-워셜 알고리즘을 사용하여 모든 정점 간의 도달 가능 여부를 계산합니다. 3. 도달할 수 없는 물건의 개수를 출력합니다. [코드] import sys INF = 1E9 if __name__ == "__main__": n = int(sys.stdin.readline())..

목표 교착 상태 개념을 설명할 수 있다. 교착 상태가 발생하기 위한 필요충분조건을 이해할 수 있다. 교착 상태 해결 방법을 설명할 수 있다. 교착 상태란? 교착 상태란 두 개 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미합니다. 결과적으로 아무것도 완료되지 못하는 상태를 가리킵니다. 교착 상태 필요충분조건 상호배제(Mutual Exclustion) 한번에 한개의 프로세스만 공유 자원을 사용할 수 있어야 한다. 점유와 대기(Hold and Wait) 최소한 하나의 자원을 점유한 상태에서 이미 다른 프로세스에 할당되어 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야합니다. 비선점(Non-preemption) 다른 프로세..

문제 보기 [사용한 알고리즘] 브루트 포스, 구현, 부분 집합 [접근 방식] 입력받은 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이 아니라면 입력 문자열 S를 뒤집어서 부분 팰린드롬의 길이를 찾은 후 최종 팰린드롬의 길이를 출력합니다. 이 과정은 아래 알고리즘에서 자세히 설명하도록 하겠습니다. [알고리즘] 1. 문자열 S가 팰린드롬인지 확인합니다. 만약 팰린드롬이라면 문자열 S의 길이를 출력합니다. 2. 문자열 S가 팰린드롬이 아니라면 reversed(S)에서 인덱스 0부터 시작하는 부분 팰린드롬의 문자열의 길이를 구합니다. 3. 문자열(S)의 길이 * 2 - 부분 팰린드롬 문자열의 길이를 출력합니다. abab를 예로 들어 설명하겠습니다. abab가 팰린드롬인지 확인합니다. 팰린드롬이 아니므로 2..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [문제 접근] 지도 상의 최단 거리를 구하는 문제는 대부분 DFS보다 BFS가 효율적이라 BFS로 접근하였습니다. DFS는 모든 경우를 탐색해야지 최단 경로인지 알 수 있기 때문입니다. [알고리즘] 1. 현재 위치를 기준으로 상, 하, 좌, 우 이동합니다. (말의 형태로 이동이 가능한 상황이라면 말의 이동도 수행합니다) 2. 이동하려는 공간에 이전에 더 적은 말의 이동으로 도달한 적이 있다면 이동을 하지 않습니다. 3. 큐가 빌 때까지 혹은 도착지점에 도달할 때까지 위 과정을 반복합니다. 4. 도착지에 도달했으면 이동 횟수, 만약에 도달하지 못했으면 -1을 출력합니다. [코드] from collections import deque import sys..

목표 API 개념을 설명할 수 있다. Library 개념을 설명할 수 있다. Framework 개념을 설명할 수 있다. API와 Library 차이점을 이해할 수 있다. Library와 Framework 차이점을 이해할 수 있다. API(Application Programming Library) API는 응용 프로그램에서 운영 체제나 프로그래밍 언어가 제공하는 기능을 제어할 수 있게 만든 인터페이스입니다. 아래의 그림을 통해 API를 조금 더 쉽게 설명해보겠습니다. 손님은 웨이터에게 음식을 주문합니다. 웨이터는 손님이 주문한 음식을 셰프에게 요청합니다. 셰프는 완성된 요리를 웨이터에게 전달합니다. 웨이터는 손님에게 음식을 제공합니다. 여기서 웨이터의 역할이 API입니다. 손님은 응용 프로그램, 셰프는 운..

문제 보기 [사용한 알고리즘] dijkstra(다익스트라), BFS(넓이 우선 탐색) [문제 접근] 출발점과 도착점을 알고 있고 음의 가중치가 없는 최단 경로를 구해야 하기 때문에 다익스트라를 사용하였습니다. [알고리즘] 1. 다익스트라 알고리즘을 사용하여 최단 경로의 값을 구합니다. 2. BFS 알고리즘을 사용하여 최단 경로의 경로를 구합니다. 3. BFS 알고리즘으로로 구한 경로를 삭제합니다. 4. 다시 한번 다익스트라 알고리즘을 사용해서 거의 최단 경로를 구합니다. [코드] from collections import deque import sys import heapq INF = 1e9 def dijkstra(): q = [] heapq.heappush(q, (0, s)) distance[s] = ..