분류 전체보기

누적합 (Prefix sum) 누적합은 나열된 수의 누적된 합을 나타낸다. Sn은 An[0,0] 합, An[0,1]합, An[0,2]합 An[0,-1]합 을 나타낸다. 누적합의 점화식은 Sn = Sn-1 + An 이다. 위 그림은 인덱스가 0부터 4까지의 수열과 해당 수열의 누적합을 나타낸 이미지 이다. 누적합을 이용해서 인덱스가 2부터 4까지의 구간을 구하려면 [0부터 4까지의 누적합](녹색) - [0부터 1까지의 누적합](빨강색) 을 계산하면 된다. 즉, 구하고 싶은 구간은 보라색이며 누적합 0부터 4까지의 구간에서 빨강색 구간을 빼면 구할 수 있다. 누적합15-누적합3 = 12 (2부터 4까지의 구간) 인덱스가 2부터 4까지의 구간을 구하려면 2부터 4까지 인덱스를 돌면서 카운트 할 수 있겠지만 이..

문제 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 풀이 본인이 시도한 풀이는 다음과 같습니다. 먼저 순차적으로 위치별로 기둥의 높이를 리스트에 저장함 (info = [0] * 1001) 리스트에 저장하면서 가장 큰 기둥의 값과 인덱스를 다른 변수에 저장함 처음 기둥부터 가장 큰 기둥까지 좌에서 우로 기둥의 높이가 담긴 리스트들을 탐색한다 리스트를 탐색하면서 높이를 stack에 저장하고 stack의 마지막에 담긴 값을 area..

문제 https://www.acmicpc.net/problem/2491 2491번: 수열 0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함), 혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾 www.acmicpc.net 제출한 풀이 n = int(input()) num_list = list(map(int,input().split())) result = 1 increase_temp = 1 decrease_temp = 1 for i in range(0, n-1): if num_list[i] result: result = increase_temp else: result else: increase_temp = 1 fo..

File Protection File에 대한 부적절한 접근 방지: 다중 사용자 시스템에서 더욱 필요 접근 제어가 필요한 연산들 : Read(R), Write(W), Execute(X), Append(A) File Protection Mechanism 파일 보호 기법은 system size 및 응용 분야에 따라 다를 수 있음 1. Password 기법 각 file들에 PW부여 비 현실적인 방법 사용자들이 파일 각각에 대한 PW를 기억해야 함 접근 권한 별로 서로 다른 PW를 부여 해야 함 2. Access Matrix 기법 Access Matrix (접근 행렬) 접근 권한을 표에 기록하겠다 라는 의미 정확한 의미로는 범위(domain)와 개체(object)사이의 접근 권한을 명시 (object: 파일, d..

이진 탐색 이진탐색은 정렬되어 있는 데이터에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 시작점, 끝점, 중간점의 위치 변수 3개를 이용한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 단계마다 탐색범위를 2로 나누어 시간복잡도는 O(logN) 이다. (log₂에 비례함) 이진탐색을 구현하는 방법은 재귀함수를 이용하거나, 반복문을 이용한다 이진탐색 문제는 탐색 범위가 큰 상황에서 탐색을 가정하는 문제가 많으므로 탐색범위가 2천만을 넘어가면 사용하는 것을 권장 이미지 출처 재귀함수로 구현 def binary_search(array, target, start, end): if start > end: return None mid = (s..

정렬(sorting) 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 선택정렬(Selection sort) 가장작은 데이터를 찾은 후에 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 가장 작은 데이터를 찾은 후 두번째 데이터와 바꾼다. 가장 낮은 값이 맨 앞부터 정렬되며 전체 배열들이 정렬 될 때까지 이 과정을 계속 반복하여 정렬하는 과정을 선택정렬이라고 한다. 선택정렬은 구현이 간단하지만, 시간 복잡도가 (N^2 + N) / 2 이다. 즉 빅오표기법으로 O(N^2) 이다. 선택정렬은 기본 정렬 라이브러리를 포함해 다른 알고리즘과 비교했을 때 매우 비효율적이다. 선택 정렬 소스코드.py array = [22, 50, 17, 25, 18, 32, 33, 44, 29, 8] for i in range(le..

overview Logical directory structure Flat(single-level) directory structure 2-level directory structure Hierarchical (tree-structure) directory structure Acyclic graph directory structure General graph directory structure Flat Directory Strucutre FS내에 하나의 Directory만 존재함: Single-level directory structure 큰 directory 하나에 모든 파일이 그 안에 들어가 있고 문제점이 발생함 문제점 File naming File protection File management 다..

더보기 Outline Disk System File System Partition Directory File Directory Structure File Protection Allocation Methods Free Space Management Disk System Disk pack - 데이터 영구 저장 장치 (비 휘발성) 구성 Sector: 데이터 저장/판독의 물리적 단위 Track: Platter 한 면에서 중심으로 같은 거리에 있는 sector들의 집합 Cylinder: 같은 반지름을 갖는 track의 집합 Platter: 양면에 자성 물질을 입힌 원형 금속판, 데이터의 기록/판독이 가능한 기록 매체 Surface: Platter의 윗면과 아랫면 Disk drive - Disk pack에 데이터를..

가상메모리를 관리할때 신경써야 할 것들이 있다. Other Considerations page size program restructuring TLB reach Page Size 메모리는 page frame단위로 나누어져있다. 페이지 크기가 시스템 성능에 많은 영향을 미칠 것을 예상하고 있음. page 크기는 적당한 것이 좋다. page는 시스템의 특성에 따라 적절한 크기가 다르다 일반적인 page size는 2^7(128) bytes ~ 2^ 22(4M) bytes 이다. 4GB의 메모리를 가졌다고 했을 때 페이지 크기가 작은 경우 페이지 수가 많다. 페이지를 관리하기 위한 테이블이 크다. 커널이 이를 관리하는 오버헤드가 크다. 반면 페이지가 크면 페이지 수가 적다. 페이지를 관리하기 위한 테이블도 작..

문제 문제링크 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 T = int(input()) for test_case in range(1, T + 1): s=input() for j in range(1,10): if s[:j]==s[j:2*j]: print(f'#{test_case} {j}') break 회문 문제랑 비슷한 유형의 느낌 문자열의 최대 길이는 30, 마디 최대의 길이는 10이므로 반복문을 0부터 9까지 반복후 문자열을 한 문자씩 리스트로 저장하여 처음 저장된 인덱스부터 j번 전까지 리스트 항목들과 j번 이후부터 2*j번까지 리스트 항목들을 비교하여 조건문이 같으면 같은 문자이므로 해당 문자열..