본문 바로가기

분류 전체보기214

[백준] 20055 컨베이어 벨트 위의 로봇 (Python/파이썬) https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 1. 주어진 조건대로 구현하면 되는 구현 문제이다. 2. 크게 복잡한 알고리즘이나 구현은 필요 없고 문제 읽고 단계별로 각 동작을 꼼꼼히 구현하면 무난하게 통과 된다. 3. 벨트 회전은 deque의 rotate() 메서드를 이용하면 편하고 로봇의 배열 같은 경우는 데크보다 그냥 리스트가 편하고 빠르다. from collections import deque import sys,.. 2022. 9. 30.

UDP Multiplexing - Demultiplexing 과정에서 Source port#의 역할은 무엇일까? UDP Multiplexing - Demultiplexing 과정에서 Source port#의 역할과 IP address 어제 네트워크 스터디를 진행하다 문득 생긴 의문점.... ✔ UDP 방식에서 Demux를 수행할 때 Destination port#와 Destination IP addreess 정보를 이용한다. 그런데 사진을 보면... ✔ 그런데 세그먼트를 보면 헤더 정보를 잘 보면 두 가지 의문점이 생긴다. 쓰지도 않는 src port#는 왜 있는가? 정작 필요한 dest IP는 어디 있는가? ✔ 두 질문에 대한 답은 교재(Computer Networking A Top-Down ApproachKurose. James, Ross, Keith)에 있었다. 1. Source Port number ✔ 우선.. 2022. 9. 30.

[백준] 2212 센서 (Python/파이썬) https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 그리디 알고리즘으로 분류되는 문제인데 대부분의 그리디 문제가 그렇듯이 그리디인 걸 알고 나면 쉽다. 그리디인 걸 알고 확신하기까지가 어려워서 그렇지... 센서와 집중국 간의 거리를 최소화 해야되기 때문에 센서 간 거리가 가장 큰 지역이 집중국 수신 영역 내에 포함되지 않도록 해야된다. 따라서 센서 간 거리를 구해서 가장 거리가 큰 지역 K - 1개를 총 지역에서 빼주면 된.. 2022. 9. 29.

[알고리즘] 최소 신장 트리 (MST) 최소 신장 트리 (MST) 신장 트리 (Spanning Tree) ✔ 그래프 내의 모든 정점을 포함하는 트리 ✔ 그래프의 최소 연결 부분 그래프 (N - 1)개의 간선 -> 트리 형태 최소 신장 트리 (Minimum spanning Tree) ✔ Spanning Tree 중에서 간선의 가중치 합이 최소(Minimun)인 트리 ✔ 최소 신장 트리는 여러 개 일 수 있다. MST 구현 - 크루스칼 알고리즘 ✔ Greedy를 이용해 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 동작 순서 간선을 오름차순으로 정렬한다. (최소 비용) 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. (Union - Find 이용: Union-Find 알고리즘이란?!) 선택한 간선을 현재 .. 2022. 9. 29.

[알고리즘] Union-Find 유니온파인드 알고리즘이란 ✔ 서로소 집합(Disjoint Set) ✔ 여러 개의 노드가 존재할 때 , 임의의 두 노드가 같은 그래프에 속해있는지 판별 Union & Find Find 노드 x가 포함된 집합을 찾는 연산 def find_parent(parent, current): if parent[current] != current: return find_parent(parent, parent[current]) return current Union 노드 x가 포함된 집합과 노드 y가 포함된 두 집합을 통합하는 연산 def union_parent(parent, x, y): x = find_parent(parent, x) y = find_parent(parent, y) # 단순한 형태에서는 작은 쪽으로 합친다.. 2022. 9. 28.

[백준] 3190 뱀 (Python/파이썬) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 큐의 선입선출 구조를 활용한 구현 문제이다. 구현해야할 사항들은 간략하게 나눠보면 다음과 같다. 뱀의 이동 게임 종료 조건 벽에 부딪혔을 때(= 범위를 벗어났을 때) 뱀의 몸통에 부딪혔을 때 사과가 있을 때 뱀의 크기를 사과가 있는 영역 한 칸만큼 늘려준다. 사과가 없을 때 뱀의 크기를 유지한 채 사과가 있는 영역으로 한 칸 이동 시켜준다.(꼬리 -1) 뱀의 몸통은 뱀이 이동하는 경로를 표시해주는 방식으.. 2022. 9. 28.

이전 1 ··· 31 32 33 34 35 36 다음

티스토리툴바