전체 글

리눅스 기본 개념

기본 개념 가상 콘솔 가상 콘솔이란 가상의 모니터로, 우분투는 총 6개의 가상 콘솔(2번~7번)을 제공한다. 즉, 컴퓨터 1대에 모니터가 7개 연결된 효과를 낼 수 있다. 가상머신을 부팅하면 X 윈도가 자동으로 실행되는데, X 윈도가 가동된 화면은 6개의 가상 콘솔 중 2번째이다. 나머지 가상 콘솔은 텍스트 모드로 제공되며, 각각의 가상 콘솔로 이동하는 단축키는 Ctrl+Alt+(F2~F7) 런레벨 init 명령어 뒤에 붙는 숫자를 런레벨이라고 부르며, 리눅스는 시스템이 가동되는 방법을 7가지 런레벨로 나눈다. 런레벨 영문 모드 설명 0 Power Off 종료 모드 1 Rescue 시스템 복구 모드 2 Multi-User 사용 X 3 Multi-User 텍스트 모드의 다중 사용자 모드 4 Multi-Us..

VMware와 Ubuntu

가상머신 가상머신 소프트웨어란 컴퓨터에 설치된 운영체제(호스트 OS) 안에 가상의 컴퓨터를 만들고, 그 가상의 컴퓨터 안에 또 다른 운영체제(게스트 OS)를 설치/운영할 수 있도록 제작된 소프트웨어를 말한다. 호스트 OS: 진짜 컴퓨터에 설치된 운영체제 게스트 OS: 가상머신 소프트웨어로 생성한 가상머신 안에 설치된 운영체제 가상머신 소프트웨어로는 VMware사의 VMware vShpere, Microsoft사의 Hyper-V, Oracle사의 Virture Box 등이 있다. 가상머신은 가상의 CPU, RAM, 하드디스크, 랜카드, CD/DVD 등의 가상의 하드웨어 장치들을 가진다. VMware 특징 1대의 컴퓨터 만으로 실무 환경과 거의 비슷한 네트워크 환경을 구성할 수 있다. 운영체제의 특정 시점을..

트리의 종류와 트리 순회

트리 (Tree) 트리는 사이클을 갖지 않는 하나의 연결 그래프로, 부모-자식의 계층적 관계를 표현하는 자료구조이다. 하나의 루트 노드는 0개 이상의 자식 노드를 가지고, 또 그 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 즉, 트리는 재귀로 정의된 자기 참조 자료구조로 서브트리로 구성된다. 트리는 특수한 형태의 그래프의 일종으로 그래프에 포함되지만, 그래프와 달리 두 노드 간의 경로는 유일하다. 그래프와 트리 모두 비선형 자료구조로 그래프는 단방향과 양방향 모두 표현 가능하지만 트리는 부모 노드에서 자식 노드로의 단방향만 표현 가능하다. 이진 트리 각 노드가 최대 두 개의 자식 노드를 갖는 트리로, 대표적으로 다음과 같은 3가지 유형이 있다. 정 이진 트리 (Full Binary Tree) 모든 ..

1863 스카이라인 쉬운거

문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 접근 건물 겉넓이, 빗물 트래핑, 주식 매매 같은 문제랑 비슷한 거 같아서 스택으로 풀이했다. 풀이 입력받은 y에 대해 스택에는 y보다 낮은 높이의 건물만 있도록 pop하면서 ans에 1씩 더한다. y가 스택에 있는 마지막 요소랑 같거나 0인 경우에는 스킵하고, 더 작은 경우 append한다. 모든 입력을 처리한 후 스택에 남아있는 원소들..

최단 경로 알고리즘

최단 경로 문제 최단 경로 문제는 각 간선의 가중치 합이 최소가 되는 두 정점 사이의 경로를 찾는 문제이다. 이때 가중치는 거리나 시간과 같은 이동 비용에 해당한다. BFS 간선의 가중치가 모두 1인 두 노드 사이의 최단 경로를 찾는데 사용한다. 인접 리스트로 구현 시 시간 복잡도는 O(V+E)이고, 인접 행렬로 구현 시 시간 복잡도는 O(V^2)이다. 구현 (경로 추적 포함) from collections import deque import sys sys.setrecursionlimit(200000) n, k = map(int, input().split()) time = [-1] * 200001 time[n] = 0 path = [-1] * 200001 path[n] = n q = deque() q.a..

그래프와 그래프 탐색

그래프 (Graph) 노드와 그 노드를 연결하는 간선의 집합으로, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 그래프를 표현하는 방법에는 크게 인접 행렬과 인접 리스트 2가지 방법이 있다. 인접 행렬 이차원 배열로 그래프의 연결 관계를 표현하는 방식으로, 모든 관계를 저장하므로 노드 개수가 많을수록 메모리 낭비가 심하다. 어떤 노드에 인접한 노드를 찾기 위해서는 모든 노드를 전부 순회해야 알 수 있으므로 효율성이 떨어진다. 인접 리스트 리스트로 그래프의 연결 관계를 표현하는 방식으로, 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용할 수 있다. 인접 행렬에 비해 특정한 두 노드의 연결 정보를 얻는 속도가 느리다. n, m = map(int,input().split()) # 인접 행렬..

20182 골목 대장 호석 - 효율성 1

문제 https://www.acmicpc.net/problem/20182 20182번: 골목 대장 호석 - 효율성 1 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 접근 20168 골목 대장 호석 - 기능성 문제는 백트래킹으로 풀이했으나, 이 문제에서는 N과 M의 범위가 아래와 같으므로 시간초과 발생 1 ≤ N ≤ 100,000 1 ≤ M ≤ 500,000 솔직히 풀이 방법이 생각이 안나서 힌트를 참고해서 다익스트라를 써야한다는 것을 알았다. 그러나 문제는 출발지부터 목적지까지의 최단거리를 구하는 것이 아니라, 가지..

해시 테이블

해시 테이블 Key-Value로 데이터를 저장하는 자료구조 중 하나로, 해싱을 통해 정보를 빠르게 저장하고 검색할 수 있다. 해시 테이블을 인덱싱하기 위해 해시 함수를 사용하는 것을 해싱이라고 한다. 먼저 각각의 키에 해시 함수를 적용해 해시 코드를 계산하고, 계산한 해시 코드를 이용해 배열의 고유한 인덱스를 계산한다. 계산한 인덱스를 통해 값을 저장하거나 검색하며, 실제 값이 저장되는 장소를 버킷이라고 한다. 해시 함수 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는 데 사용할 수 있는 함수로, 충돌이 발생할 확률을 최대한 줄이는 것이 중요하다. 충돌은 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나, 서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 것을 말하며, 충돌이 자주 발..

21277 짠돌이 호석

문제 https://www.acmicpc.net/problem/21277 21277번: 짠돌이 호석 DIY(Do It Yourself)는 호석이가 제일 좋아하는 컨텐츠이다. 이번 DIY는 동네 친구 하늘이랑 각자 직소 퍼즐을 하나씩 맞춰보기로 했다. 두 개의 퍼즐은 각자 N1 행 M1 열과 N2 행 M2 열의 격자 형태 www.acmicpc.net 접근 카카오 기출 문제 중 자물쇠와 열쇠 문제에서 힌트를 얻어, 기준 퍼즐1의 범위를 확장 시켜서 전체 경우마다 퍼즐2와 맞춰보는 식으로 풀이했다. 퍼즐의 크기 제한이 50 이므로 상하좌우 50씩 확장할 경우, 최대로 확장될 수 있는 퍼즐의 한 변의 길이는 150이다. 따라서 회전까지 고려했을 때 최대 4 * 100 * 100 * 50 * 50 = 10 * 9..