전체 글

[파이썬으로 배우는 알고리즘] 버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 비교하고, 순서가 맞지 않으면 교체하는 방식으로 정렬하는 정렬 알고리즘입니다. 원소가 마치 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다고 합니다. 버블 정렬 과정 위와 같이 정렬되어 있지 않은 배열을 버블 정렬 알고리즘을 사용하여 정렬해보겠습니다. 먼저 배열의 맨 앞부터 인접한 원소를 비교합니다. 11은 10보다 크므로 대소 관계를 만족합니다. 따라서 교체하지 않습니다. 그다음으로 인접한 11과 2를 비교합니다. 2는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 원소의 자리를 교체합니다. 그다음으로 인접한 11과 4를 비교합니다. 4는 11보다 작으므로 대소 관계를 만족하지 않습니다. 따라서 위와 같이 두 ..

[백준(BOJ)] #1525- 퍼즐 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 풀이 BFS 알고리즘 적용하여 해결 1) 입력받은 board를 문자열로 변환 2) 완성된 퍼즐 모양이 나올 때까지 문자열의 인덱스를 조정해가면서 탐색. 퍼즐 모양이 나오면 움직인 횟수를 출력하고 퍼즐 모양을 만들 수 없으면 -1 출력 위와 같은 모양의 board에서 빈칸(0)을 움직이면서 퍼즐을 완성시키는 것이 목적입니다. BFS 알고리즘을 적용하여 퍼즐을 완성시키기 위해 2차원 모양의 board를 문자열로 변환시킵니다. 순서에 맞게 문자열로 변환시키면 문자열은 ..

[운영체제] 운영체제(OS)

운영체제란? 운영체제(Operating System)는 컴퓨터 하드웨어의 바로 위에 설치되어 사용자의 하드웨어, 시스템 자원을 관리 및 제어하고, 사용자와 하드웨어 간의 인터페이스의 역할로 동작을 하여 다른 응용프로그램이 유용한 작업을 할 수 있는 환경을 제공해주는 시스템 프로그램입니다. 우리가 사용하고 있는 대표적인 운영체제로는 Window, macOS, UNIX 등이 있습니다. 운영체제의 역할 1) 사용자 관점에서의 역할 사용자 관점에서 운영체제는 사용자가 컴퓨터를 쉽고 편리하게 사용하도록 인터페이스를 제공합니다. *GUI나 *CLI가 대표적인 예시로 컴퓨터 자원을 공평하게 사용할 수 있도록 해주고, 사용자가 자원에 대해 신경 쓰지 않도록 해줍니다. *GUI - Graphic User Interfac..

[백준(BOJ)] #1103- 게임 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 문제 풀이 처음에 DFS 알고리즘을 적용하여 풀었는데 시간 초과가 발생했습니다. 다른 풀이를 참고하여 DP를 함께 적용하여 풀 수 있다는 것을 알았습니다. 문제 풀이는 다음 이 블로그의 풀이를 참고하여 풀었습니다. 2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) DFS란? DFS(..

[백준(BOJ)] #1194- 달이 차오른다, 가자. (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 BFS와 비트마스크 활용 2022.07.14 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) [파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색) BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인접한 노드부..

[네트워크] OSI 7계층, TCP/IP 4계층

OSI 7계층이란? OSI(Open System Interconnection)는 국제표준화기구(ISO)에서 개발한 네트워크 표준 모델로 세계적으로 사용되고 있습니다. 네트워크 프로토콜과 통신이 7계층으로 구성되어 있어 OSI 7계층이라 불립니다. 7계층으로 나눈 이유 1) 통신이 일어나는 과정을 단계적으로 파악하기 위해 2) 통신 중에 특정한 곳에 문제가 발생했을 때 다른 단계를 건드리지 않고 문제가 발생한 단계에서 해결하기 위해 OSI 7계층 단계 네트워크 장비 허브(Hub) - 여러 대의 컴퓨터를 연결해서 네트워크를 만들어주는 장치로 데이터 패킷을 받으면 연결된 모든 장치들에게 모두 전송. 스위치(Switch) - 연결된 장치들의 IP와 MAC 주소를 모두 테이블 형태로 가지고, 원하는 목적지에 데이..

[백준(BOJ)] #1655- 가운데를 말해요 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제 풀이 우선순위 큐 사용 2022.07.19 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) [파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap) 우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIFO 구조라는 것을 배웠습니다. 큐 배우기 -..

[네트워크] 네트워크 토폴로지(Network Topology)

네트워크 토폴로지란? 네트워크의 요소들(링크, 노드 등)이 어떻게 배치되어 있는지에 대한 연결 방식 네트워크 토폴로지(Network Topology)라고 합니다. 병목 현상이 발생했을 때 네트워크가 어떤 토폴로지를 갖는지가 문제점을 찾는데 중요한 키가 될 수 있습니다. 병목 현상: 전체 시스템의 성능이나 용량이 하나의 구성 요소로 인해 제한을 받는 현상 토폴로지의 종류 버스(Bus) 중앙 통신 회선 하나에 여러 노드가 연결되어 공유하는 네트워크 구조 근거리 통신망 LAN에서 사용 설치 비용이 적고 신뢰성이 우수 간단한 구조로 노드를 추가하고 삭제하기 쉬움 스푸핑 공격을 받을 위험이 있음 트리(Tree) 트리의 형식으로 네트워크가 구성되어 있으며 계층형 토폴로지라고도 불림 노드를 추가하는 것은 쉽지만, 삭..

[백준(BOJ)] #1300- K번째 수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 풀이 배열의 크기 N이 10^5보다 작거나 같은 자연수이기 때문에 일차원 배열로 변환하고 정렬해서 구하기는 불가능합니다. 이분 탐색을 사용하여 이 문제를 해결할 수 있습니다. 2022.08.11 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search) [파이썬으로 배우는 알고리즘] 이분 탐색(Binary Search..

[백준(BOJ)] #2436- 공약수 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 문제 풀이 최대공약수와 최소공배수의 성질을 이용해 풀이 2022.07.01 - [PS/프로그래머스] - [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3) [프로그래머스(Programmers)/ Level2] N개의 최소공배수 (파이썬, Python3) 문제 https://school.programmers.co.kr/learn/courses/30..