본문 바로가기

분류 전체보기

 (117)
백준 13549 숨바꼭질 3(python) 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 주어진 2가지 경우로 이동하면서 목표지점으로 가는 문제였습니다. 이렇게 간선의 가중치가 두 종류로만 이루어진 문제를 0,1 BFS라고 부르며 데크를 사용하여 구현할 수 있습니다. 구현 과정은 다음과 같습니다. 처음 시작지점을 데크에 넣어줍니다. 데크의 가장 앞쪽 값을 pop 해 주어서 갈 수 있는 조건에 따라 시간을 구해 줍니다. x-1, x+1 일때는 1초..
백준 2637 장난감 조립(python) 문제 https://www.acmicpc.net/problem/2637 2637번: 장난감 조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 위상 정렬과 dp개념을 사용하여 푼 문제입니다. 부품 간의 관계를 파악하여 우선순위를 따라가며 개수들을 계산하는 문제였습니다. 과정은 다음과 같습니다. 먼저 입력을 받아 장난감 부품중 기본 부품을 따로 구분해서 큐에 넣어주고 기본 부품부터 순회를 시작합니다. 연결된 상위 부품의 갯수를 계산하기 때문에 필요로 하는 하부 부품들의 개수를 하부 부품들을 만들 때 드는 개..
Chapter 1 컴퓨터 시스템으로의 여행(1.8 ~ 끝) 1.8 시스템은 네트워크를 사용하여 다른 시스템과 통신한다 개별 시스템의 관점에서 볼 때, 네트워크는 단지 또 다른 입출력 장치로 볼 수 있다. 시스템이 메인 메모리로부터 네트워크 어댑터로 일련의 바이트를 복사할 때, 데이터는 로컬 디스크 드라이브 대신에 네트워크를 통해서 다른 컴퓨터로 이동된다. 마찬가지로 시스템은 다른 컴퓨터로부터 받은 데이터를 읽어서 메인 메모리에 복사할 수 있다. hello 예제로 돌아가서 , telnet응용을 사용하여 hello프로그램을 다른 곳에 위치한 컴퓨터에서 실행할 수 있다. telnet 클라이언트를 사용하여 로컬 컴퓨터를 원격 컴퓨터의 telnet 서버와 연결하려 한다고 하자. 원격지 컴퓨터에 로그인하고 쉘을 실행시킨 후에 원격지 쉘은 입력 명령을 기다린다. 다음은 과정..
백준 2617 구슬 찾기(python) 문제 https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 그래프 탐색으로 접근할 수 있는 문제입니다. DFS, BFS 어떤 것을 사용해도 무방하지만 저는 플로이드-워샬이 먼저 떠올랐기 때문에 이 방식으로 풀어보았습니다. 출력해야 되는 값이 무게가 절대로 중간값이 될 수 없는 구슬의 개수를 세는 문제였습니다. 풀이 과정은 다음과 같습니다. 먼저 입력으로 들어오는 구슬 번호대로 무게 순서를 지켜 관계를 2차원 리스트에 1로 표시해 줍..
백준 3055 탈출(python) 문제 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS방식으로 문제에 접근했습니다. 물과 고슴도치 둘 다 움직이는데, 고슴도치는 물이 있는 곳으로 갈 수 없으니, 물을 먼저 움직여서 이차원 리스트에 표시해 두고, 그다음 고슴도치를 움직여 주었습니다. 물과 고슴도치 두 개의 큐를 사용하였습니다. 시작할 때 물의 위치와 고슴도치의 위치를 받아서 큐에 각각 넣어줍니다. 물은 여러 곳에 존재할 수 있습니다. 물이 갈 수 있는 곳을 찾아서 각 방향으로 움직여서..
Chapter 1 컴퓨터 시스템으로의 여행(1.5 캐시가 중요하다~1.7.4 파일) 1.5 캐시가 중요하다 프로그램을 실행하는 예제로부터 얻게 되는 교훈은 시스템이 정보를 한 곳에서 다른 곳으로 이동시키는 일에 많은 시간을 보낸다는 것이다. 프로그램의 기계어 인스트럭션들과 코드인 데이터 스트링들은 본래 하드 디스크에 저장되어 있었다. 프로그램이 로딩될 때 메인 메모리로 복사되고 데이터 스트링들은 디스플레이 장치로 복사된다. 프로그래머의 관점에서 보면, 이러한 과정들은 프로그램의 '실제 작업'을 느리게 하는 오버헤드다. 그래서 시스템 설계자들의 목적은 가능한 복사 과정들을 빠르게 동작하도록 하는 것이다. 마찬가지로 일반적인 레지스터 파일은 수백 바이트의 정보를 저장하는 반면, 메인 메모리의 경우는 십억 개의 바이트를 저장, 그러나 프로세서는 레지스터 파일의 데이터를 읽는 데 메모리의 경우..
백준 1918 후위 표기식(python) 문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net 스택에 좀 더 익숙해지기 위해 푼 문제, 생각보다 구현이 까다로워서 좀 걸린 것 같다. 조건에 맞게 경우를 좀 나눠 주어야 한다. 먼저 알파벳이나 여는 괄호 라면 그대로 스택에 넣어준다. 닫는 괄호일 때는 스택에서 여는 괄호가 나오기 전까지 pop 시켜주며 출력해준다. 연산자는 우선 순위에 따라 나눠 주는데, 우선순위가 높은 '*'와 '/'가 스택의 top 값에 있을 때 들어오는 값..
백준 13334 철로(python) 문제 https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 우선순위 큐를 활용하여 스위핑 방식으로 접근하였습니다. 집과 사무실 위치를 위치에 맞게 리스트에 저장해 준 다음 오른쪽을 기준으로 오름차순 정렬해주었습니다. 그 뒤 리스트에 주어진 값들을 차례로 순회하면서 주어진 철로 길이 안에 해당되면 큐에 넣어 주었습니다. 큐 최소 힙을 만들며 왼쪽 좌표만을 넣어 주었습니다. 큐에 있는 값들과 순회하면서..

티스토리툴바