18427번: 함께 블록 쌓기 첫째 줄에 자연수 N, M, H가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 10, 1 ≤ H ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 각 학생이 가진 블록들의 높이가 공백을 기준으로 구 www.acmicpc.net 132ms DP, knapsack N명의 학생들이 가지고 있는 블록으로 H 높이를 만들 수 있는 경우의 수를 계산하는 문제이다. 이 문제의 핵심은 다음과 같다 한 학생당 최대 1개의 블록만 사용가능 블록을 사용하지 않아도 됨 3명의 학생이 다음과 같은 높이의 블록을 가지고 있을 때 높이 1부터 h=5까지 만들 수 있는 경우의수를 생각해보자 2 3 5 3 5 1 2 3 1 2 3 4 5 1 0 1 1 0 1 2 3 첫 번째 학..
find 명령어 find 명령은 시스템 내에 있는 파일 중 사용자가 원하는 파일을 찾을 때 사용한다. 찾은 파일에 특정 명령을 실행하도록 명령할 수 있다. find path [expression] [action] 검색할 경로는 최상위 루트 디렉터리 / 부터 시작하는 절대경로나 현재 디렉터리 . 부터 시작하는 상대경로를 지정할 수 있다. find / : 최상위 루트 디렉터리 모든 파일 검색 find /tmp : /tmp 디렉터리 이하 파일 검색 find . : 현재 디렉터리 이하 파일 검색 검색 조건(옵션)은 하나 이상 명시할 수 있으며 논리 연산이 가능하다. (논리 연산을 생략하면 AND 연산을 의미) -a : AND 연산 -o : OR 연산 ! : 부정 연산 기본 사용법 find . -type f -u..
9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1484ms # 접근방식 1부터 n까지 팀을 만들 수 있는지 판단한다 핵심은 1 → 2 → 3 → 4 → 5 → 2 가 되면 1은 팀이 될수 없고 2, 3, 4, 5 는 팀이 될 수 있다. 따라서 팀을 만들기 위해 함께 하고 싶은 학생들을 꼬리를 물고 탐색할 때, list에 추가하면서 탐색한다. 1. 다음 확인하는 학생이 list에 포함된다면 그 학생의 index부터는 팀을 만들 수 있다는 의미이다. 따라서 그 전 index 수만큼 팀을 못 만드는 학생이 추가된다. ..
파일의 종류 일반(정규)파일 : 텍스트나 바이너리 형태의 데이터를 저장하고 있는 파일 디렉터리 : 디렉터리에 포함된 파일명과 해당 파일의 inode number 정보를 목록으로 가지고 있는 특별한 파일 특수파일 : 프로세스 간 통신(IPC)목적의 특수파일(e.g. 파이프, 소켓) 또는 입출력 장치(e.g. 프린터, 키보드)를 사용하기 위한 장치파일 ls 명령어 ls 명령어는 list의 약자로 디렉터리에 있는 파일 목록을 보여주고 여러가지 정보(파일타입, 접근권한, 소유자, 소유그룹, 크기, 최종 수정일시 등) 확인할 때 사용한다. 디렉터리에는 파일명과 해당 파일의 inode number 정보만 가지고 있으며 ls 명령어로 파일의 상세정보를 볼 수 있는 것은 해당 inode number를 통해 inode ..
2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 725ms bfs dfs로는 시간초과가 나고 단순 bfs 로 해결할 수 없는 문제이다. 디버깅을 통해 벽을 부수고 이동했을 경우 방문체크와 벽을 부수지 않고 이동했을 경우의 방문체크를 다르게 해줘야 정답이 나온다는 것을 깨달았고 방문체크 배열을 3차원 배열로 선언하여 체크했다. 다음과 같이 벽을 부순 경우와 부수지 않은 경우를 나눠 방문체크 해준다. 벽을 부수지 않고 이동한 경로는 visited[][][0] 벽을 부수고 이동한 경로는 v..
파일시스템(File System) 파일시스템은 물리적인 저장장치(e.g.하드디스크)에 파일을 생성, 저장, 관리하기 위한 논리적인 자료구조이다. 물리적인 저장장치는 논리적인 파티션으로 나눠지며, 파티션별로 고유한 파일시스템(e.g. NTFS, EXT2, EXT3, EXT4)을 생성한다. mount : 특정 디렉터리와 파일시스템을 연결해주는 것 umount : 특정 디렉터리와 파일시스템 연결을 해제하는 것 파일시스템 구성 Boot block: 운영체제가 부팅하거나 초기화하기 위한 부트스트랩 코드를 담고 있는 블록 Super block: 파일시스템을 관리하기 위한 정보를 담고 있는 블록 inode list: 파일시스템 내 파일들에 대한 속성 정보를 담고 있는 리스트 Data block: 실제 파일의 내용(데..
프로세스 간 통신 (IPC, Inter-Process Communication) 프로세스들은 각자 독립적인 메모리 공간(가상 메모리 공간)을 사용하기 때문에 메모리 공간을 공유해서 통신하는 것은 불가능하다. 따라서 프로세스 간 통신을 위해서는 운영체제(커널)에서 지원하는 주요 프로세스 간 통신 기법을 이용해야 한다. Pipe, shared Memory, Message Queue, Semaphore, Socket, Signal 파이프(Pipe) 및 파이프라인(Pipeline) 파이프 또는 파이프라인은 프로세스(명령)의 표준 출력을 다른 프로세스(명령)의 표준 입력으로 전달해주는 기능을 한다. 2개의 프로세스 사이에서 단방향으로 통신할 수 있도록 지원하는 특수 파일이다. 명령어의 실행 결과를 다른 명령어의 ..
입출력 재지정 (I/O Redirection) 기능 명령에 의해 프로그램을 실행하면 커널(운영체제)에 의해 프로세스가 생성되고 프로세스는 기본적인 입출력(I/O)을 위한 3개의 파일을 오픈한다. 표준 입력(STDIN, FD:0) : 키보드로부터 입력받기 위한 파일 표준 출력(STDOUT, FD:1) : 수행 중에 발생한 정상 메시지를 모니터로 출력하기 위한 파일 표준 에러(STDERR, FD:2) : 수행 중에 발생한 에러 메시지를 모니터로 출력하기 위한 파일 유닉스/리눅스 시스템에서 프로세스별로 오픈한 파일을 식별하기 위해 부여한 파일 번호로, 프로세스가 실행되면 기본적으로 3개의 파일을 오픈한다. 이 때 오픈한 파일을 식별하기 위해 부여하는 FD가 0(표준입력), 1(표준출력), 2(표준에러)로 정해..
passwd 파일 사용자 계정 정보를 저장하고 있는 파일로 콜론 : 을 구분자로 7개의 필드로 구성되어 있다. 경로 : /etc/passwd * grep + 패턴, egrep + 패턴 여러개, ^ 행의 시작, $ 행의 끝 * ① root : ② x : ③ 0 : ④ 0 : ⑤ root : ⑥ /root : ⑦ /bin/bash ① 사용자 계정명 ② 사용자 패스워드 ③ UID ④ GID ⑤ comment ⑥ 홈 디렉터리 ⑦ 로그인 쉘 ⑤ 설명 : 사용자 관련 기타 정보(e.g. 이름) ⑥ 홈 디렉터리 : 사용자가 로그인에 성공한 후에 동작할 쉘 프로그램이 설정된다. ② 사용자 패스워드 사용자 패스워드②에 설정된 x 의 의미는 shadow 패스워드 정책을 사용한다는 의미이다. shadow 패스워드 정책이란 ..
252ms DP 동전은 쪼갤 수 없으므로 0/1 Knapsack 문제로 DP를 이용하여 해결할 수 있다. 입력받은 돈의 합(sum)을 구한 뒤, sum 이 홀수이면 반으로 나누지 못하므로 0 출력. 짝수이면 mid = sum / 2의 값을 동전들로 표현할 수 있는지 확인하면 된다. dp[i][x] : i번째 동전을 사용할 때, x원을 표현하기 위해 사용한 동전의 최소 개수 먼저 사용한 동전의 최소 개수를 구할 것으로 모든 값들을 INF 로 초기화 해준다. i번째 동전으로 x원을 만들 수 있을 때, 사용한 동전의 개수를 저장하고, i+1번째 동전으로 x원을 만드는 dp[i+1][x] 을 0으로 만들어준다. 그렇게 하면 dp 값이 INF 이면 pass , INF가 아니라면 이전 동전 index에서 x원을 만..
① 터미널 접속 프로그램을 이용하여 서버 접속 Telnet 클라이언트 프로그램 Telnet 프로토콜 23/tcp 은 통신 구간 보안(암호 통신)을 지원하지 않는다. 즉, 평문으로 통신하므로 네트워크 스니핑 공격에 취약 SSH 클라이언트 프로그램 SSH 프로토콜 22/tcp 은 통신 구간 보안(암호통신)을 지원한다. 💡보안 상 Telnet이 아닌 SSH 프로토콜 사용 권장 ② 사용자 인증을 처리하는 로그인 프로세스가 동작하여 사용자 인증을 처리한다. * 인증(Authentication) : 사용자의 신원확인 * 인가(Authorization) : 인증된 사용자에게 적절한 접근권한을 부여하는 것 ③ 사용자 환경설정 파일을 로드하고 로그인 쉘을 기동한 후 사용자 홈디렉터리에서 사용자 입력을 기다린다. ✨ 쉘 ..
윈도우 인증 구성 요소 ① LSA (Local Security Authority) 모든 계정의 로그인에 대한 검증 및 시스템 자원에 대한 접근 권한을 검사 계정명과 SID(Security ID)를 매칭하여 SRM이 생성한 감사 로그를 기록 ② SAM (Security Account Manager) 사용자, 그룹 계정 및 암호화된 패스워드 정보를 저장하고 있는 데이터베이스 ③ SRM (Security Reference Monitor) 인증된 사용자에게 SID(Security ID) 부여 SID를 기반으로 시스템 자원에 대한 접근을 허용할지 여부 결정 후 감사 메시지 생성 로컬 인증 Winlogon 화면(로그인 창)에서 아이디와 패스워드를 입력 ➜ LSA 서브시스템이 인증 정보를 받아 로컬 인증용이면 NTL..
