CS
[Algorithm] 비트마스킹
비트마스킹(BitMasking) 비트마스킹(BitMasking)이란 비트를 활용해 집합을 표현하는 기법이라고 볼 수 있다. 빠른 연산속도와 적은 메모리 사용량, 그리고 배열을 정수로 표현할 수 있다는 장점이 있다. 비트는 컴퓨터에서 사용되는 데이터의 최소단위인데 0과 1로 표현한다. 따라서 2진법이라고 생각하면 편하다. 비트마스킹은 이런 특징을 이용한다. 예를 들어 {1, 4, 3}이라는 집합이 있다고 해보자. 각 원소의 포함 여부를 이용해 부분집합을 표현하면 다음과 같다. {1, 4} => 110 {3} => 001 {1, 3} => 101 또한 이를 10진수로 표현할 수도 있다. {1, 4} => 110 => 6 {3} => 001 => 1 {1, 3} => 101 => 5 이러한 특징을 이용해 비트..
[BaekJoon] 백준 2668번 숫자고르기
[BaekJoon] 백준 2668번 숫자고르기 문제: https://www.acmicpc.net/problem/2668 내코드 - 문제의 규칙을 찾아보면 다음과 같다. - 사이클을 이루는 값이면 결과에 포함된다. 따라서 다음과 같이 풀었다. - 1-N까지 반복을 돈다. - 각 i번에 대해 i번에서 시작해서 dfs를 돌았을 때 이미 처음에 방문했던 i번으로 다시 돌아오게 된다면 사이클을 이루는 경우고 결과에 포함된다. - 마지막에 sort를 해주지 않아 틀렸었다. # BaekJoon2668.py N = int(input()) arr = [[] for _ in range(N + 1)] result = set([]) for i in range(N): tmp = int(input()) arr[tmp].appen..
[BaekJoon] 백준 16234번 인구 이동
[BaekJoon] 백준 16234번 인구 이동 문제: https://www.acmicpc.net/problem/16234 내코드 - 우선 특정 조건을 만족하는 경우 인접한 모든 행을 탐색한다는 점에서 그래프의 탐색문제라고 생각했다. - dfs, bfs 어느것으로 풀어도 상관없지만 시간, 메모리 효율성이 dfs가 낫다는 말이 생각나 dfs를 선택했다. - 조건만 잘 따진다면 간단하게 풀리지만 python으로 채점하니 시간초과가 나서 pypy3로 채점했다. # Baekjoon16234.py import sys input = sys.stdin.readline N, L, R = map(int, input().split()) dx = [0, 1, 0, -1] dy = [-1, 0, 1, 0] arr = [0 f..
[DB] 데이터베이스, Index
데이터베이스 데이터베이스는 통합하여 관리되는 데이터의 집합체를 의미한다. 이는 중복된 데이터를 없애고, 자료를 구조화하여 효율적인 처리를 할 수 있도록 관리된다. 이런 데이터베이스는 응용 프로그램과는 다른 별도의 미들웨어에 의해 관리되며 이를 데이터베이스 관리 시스템 (DBMS)라고 한다. 데이터 베이스를 사용하는 이유 파일 시스템을 사용했을 때의 문제점 데이터의 중복과 비일관성 데이터 접근 시 필요한 데이터를 편리하고 효율적으로 검색하기 힘듬 데이터가 여러 파일에 흩어져 있고 파일 형식이 서로 다를 수 있음 데이터 동시 접근 시 데이터가 잘못 업데이트 될 수 있음 무결성 문제 보안 문제 데이터베이스의 장점 데이터의 논리적, 물리적 독립성, 일관성, 무결성, 보안성 보장 데이터의 중복 최소화 저장된 자료..
[Network] Top-down Approach 1장
What is the Internet? 인터넷이란 전세계에 퍼져 있는 수 억개의 디바이스들을 연결하는 컴퓨터 네트워크이다. 디바이스(PC, server, smartphone)을 host 또는 end system이라고 함 End System들은 여러 종류의 물리적 매체들로 이뤄진 통신링크(Communication Link)들에 의해서 네트워크로 연결이 됨 하나의 시스템에서 다른 시스템으로 데이터를 전달 할 때 패킷(packet)이라는 정보의 묶음으로 전달이 됨 인터넷 내에서 이 정보들의 이동은 프로토콜(protocol)로 제어가 됨 프로토콜은 2개 혹은 그 이상의 개체간 정보 교환이 이뤄질 때 교환하는 메세지의 형식과 순서를 정의해줌. 또한, 메세지가 전달 혹은 받아질 때 취해야 하는 행동들을 정의해줌 패..
[OS] Computer System Overview
Processor(CPU) program vs process vs processor Program: 일반적으로 하드 디스크 등에 저장되어 있는 실행 코드 Process: program을 구동하여 program 자체와 program의 상태가 메모리 상에서 실행되는 작업 단위 Processor(CPU): 제어장치, 연산장치, 레지스터 그리고 데이터 버스로 구성된 디지털 시스템의 핵심 부분. 프로그램을 기억장치로부터 읽어 데이터를 처리하고 각종 장치를 구동. ex) 하나의 프로그램을 여러 번 구동하면 여러 개의 프로세스가 메모리 상에서 실행됨 ex) 프로세서는 프로그램을 기억장치로부터 읽어와 구동시킴. 구동시킨 프로그램이 프로세스. 프로그램 실행 과정 1. 사용자가 단축 아이콘 혹은 명령행에서 프로그램을 실행..
[BaekJoon] 백준 1915번 가장 큰 정사각형
[BaekJoon] 백준 -번 문제이름 문제: https://www.acmicpc.net/problem/1915 내코드 - 점화식을 생각해내기 약간 까다로운 dp문제였다. - 점화식은 다음과 같다. - dp[i][j] = [i][j]칸을 정사각형의 가장 오른쪽 아래라고 했을 때 만들수 있는 가장 큰 정사각형의 한 변의 길이 - dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 - 왜 위의 점화식이 성립하는지는 그림을 그려보면 쉽게 알 수 있다. import java.io.*; import java.util.StringTokenizer; public class test { public static void main(String[] args) throws ..