분류 전체보기 (78) 썸네일형 리스트형 [이것이 파이썬 코딩테스트다 - 구현] 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하.. [이것이 파이썬 코딩테스트다 - 구현] 청소년 상어 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net import copy # 입력받을 배열 초기화 graph = [[None]*4 for _ in range(4)] for i in range(4): data = list(map(int, input().split())) # 데이터 각각 집어넣기 for j in range(4): # 중요: 여기서 -1 해주는 이유? dx, dy 값 8개만 쓸 것이라서 graph[i][j] = [dat.. [이것이 코딩 테스트다 - 구현+bfs] 아기상어 https://www.acmicpc.net/problem/16236 from collections import deque INF = int(1e9) n = int(input()) graph = [list(map(int,input().split())) for _ in range(n)] # 아기상어 위치 찾기 s_x = 0 s_y = 0 for i in range(n): for j in range(n): if graph[i][j] == 9: s_x = i s_y = j # 상어 위치 0으로 변경 graph[s_x][s_y] = 0 # 상어 초기 크기 size = 2 # 먹은 놈 구하기 count = 0 # 버틴 시간 time = 0 # 모든 위치에서의 최단 거리 구하기 def bfs(): # 이동할 수 없는.. (이것이 코딩테스트다 - 그리디) 볼링공 고르기 무지성과 지성의 대결... 조합을 써야 하는 문제면 그냥 아무 생각 없이 combinations을 갈겨버리는 나... from itertools import combinations n,m = map(int,input().split()) k = list(map(int,input().split())) count = [0] * m # print(count) for i in k: idx = i-1 # print(idx) count[idx] += 1 c_zero = 0 minus = 0 for i in count: if i == 0: c_zero += 1 elif i >1: minus += len(list(combinations(range(i),2))) result = len(list(combinations(ra.. [운영체제] 시험 대비 - 8강 ~ 10강 (Locality and Caching, Paging Scheme Design, Memory Management Policy) Locality and Caching TLB : 주소 변환 시 메모리에 접근하는 일을 줄여줌 CPU의 cache에 위치 → VPN과 PFN 쌍으로 존재 TLB miss → memory에 존재하는 page table 따라가서 PFN 주소 확인 누가 TLB miss 처리? OS TLB miss → 현재 명령 중지 → kernal mode로 변환 → trap page table 조회 → TLB update → 다시 명령 실행 없으면? TLB miss handler HW page table 메모리 위치, page table 존재하는 정보 알아야 TLB VPN, PFN, 다른 비트들로 entry 구성 fully-associative(캐시 내 아무 장소에 mapping 가능) 문제 서로 다른 process에 대해 .. [운영체제] 시험대비 - 6~7강 (Memory Segmentation, Paging) 6강. Memory Segmentation Base-and-Bound 접근의 한계 32 bit 주소공간의 낭비가 심했음: heap stack 사이 공간 낭비 Segmentation base, bound를 segment마다 부여 → bound를 size로 개명 code segment에 base, size // stack segment에 base, size // heap segment에 base, size Segmentation fault의 발생 요건 Segment의 size를 초과할 때 OS에서 감지 → trap → 해당 프로세스 종료 Segment offset 참조 : 가상 주소의 상위 n개 bit를 segment bit로 두어서 segment 식별 후, 하위 비트들로 offset 판별 offset 이용.. [운영체제] 시험대비 - 2강~5강 (Process, Scheduling Basics, Advanced Scheduling Scheme, Memory And Address Space) 2강. Process process 구성 요소 register → program counter, stack pointer memory → (address space) context switch kernel starck에 중요한 register 값을 저장 General purpose of registers PC kernel stack pointer 곧 실행될 프로세스를 kernel stack에 담음 곧 실행될 kernel stack으로 switch Direct execution → Limited Direct Execution interrupt : OS는 concurrency 보장 위해 interrupt 차단하는 기능을 수행해줌 user-kernel mode 분리: OS에게 precvilege 부여 3강. .. [운영체제] 11강 - 16강 Concurrency; Concepts and Case Studies, Locks, Conditional Variables, Semaphore, Concurrent Data Structures, Deadlock 11강 Concurrency, Concepts and Case Studies Thread : 여러개의 PC + 자체 레지스터로 구성 → 스택에 보관 Thread들은 서로 같은 주소 공간을 공유 Thread를 쓰는 이유 병렬 처리 간단 → 하나의 작업 여러 스레드가 작업 → 시간 줄일 수 잇음 느린 I/O로 프로그램 수행되는 것이 차단되는 것을 방지 TCD: thread register 상태 기록 (PCB와 유사) Race Condition : 자원 사용하기 위해 두 스레드가 레이스를 하듯 경쟁; 예상과 다른 결과 Critical Section: 공유 변수에 접근하는 코드 부분 → Lock 함수 내 지역 변수를 리턴값으로 쓰면 dealloc 될 수 있으므로, 함수의 인자를 통한 리턴값 전달 모든 lock은.. 이전 1 2 3 4 5 6 7 ··· 10 다음