본문 바로가기

분류 전체보기

 (136)
시스템 콜(System Call) 시스템 콜(System Call) 개념 사용자가 직접 커널 접근x => 응용프로그램에서 시스템 커널에 어떠한 기능을 수행해 달라고 요청 명령어 fork, exec: 새로운 프로세스 생성 wait: 프로세스가 만든 자식 프로세스가 끝날 때까지 기다리는 명령어 fork() 함수를 통해 부모 프로세스를 복사하면 주소 공간을 Binary 통째로 복사 Program Counter까지 모두 복사되니 자식 프로세스는 부모와 똑같이 동작 자식은 main()의 시작부터 실행하는 것이 아니라 fork() 다음 코드부터 실행 Q. 그러면 어떻게 자식과 부모를 구분? A. 리턴값의 차이 => 부모는 양수 자식은 0 exec()라는 System Call을 통해 프로그램을 덮어 씌우기 그 다음 코드 실행x wait()의 경우 자..
DFS & BFS DFS(Depth-First Search) 개념 루트노드에서 시작해 다음 분기로 넘어가기 전 해당 분기를 완벽하게 탐색 스택 or 재귀함수로 구현 특징 장점 최단 경로 빠르게 찾을 수 있다. 단점 경로가 매우 길 경우 많은 기억 공간 필요 비연결 그래프일 경우, 모든 그래프 탐색 후 실패 BFS(Breadth First Search) 개념 루트 노드에서 시작해 인접한 노드를 먼저 탐색하는 방식으로 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문 큐를 이용해 구현 특징 장점 적은 메모리 사용 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠름 단점 경로가 존재하지 않아도 끝날 때까지 탐색 최단 경로 찾기 힘듬
이분 탐색(Binary Search) 이분 탐색 개념 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터 탐색 배열 내부의 데이터가 정렬되어 있어야만 사용 가능 과정 데이터를 오름차순으로 정렬 자료의 중간값(mid)가 찾고자 하는 값(target)인지 비교 mid 값이 target과 다르다면 대소관계를 비교해 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 2, 3번 반복 target이 mid보다 작으면 end를 mid 왼쪽 값으로 바꿈 target이 mid보다 크면 start를 mid 오른쪽 값으로 바꿈 코드 def binary_search(target, data): data.sort() start = 0 # 맨 처음 위치 end = len(data) - 1 # 맨 마지막 위치 while start ..
계수정렬(Counting Sort) 계수정렬(Counting Sort) 개념 각 숫자가 몇 개 있는지 개수를 세어 저장한 후에 정렬 기수정렬과 마찬가지로 비교를 하지 않는 알고리즘 양수만 가능, 값의 범위가 제한적 과정 1. 정렬되지 않은 배열의 수들이 각각 몇 번 나왔는지 count 배열에 기록 # 정렬을 수행할 배열 arr = [4, 7, 9, 1, 3, 5, 2, 3, 4] count = [0] * (max(arr) + 1) for num in arr: count[num] += 1 print(count) # [0, 1, 1, 2, 2, 1, 0, 1, 0, 1] 2. count 배열을 앞에서 순회하여 자신이 정렬된 배열에서 몇 번째에 나와야 하는지 기록하기 위해 누적합으로 갱신 for i in range(1, len(count)): ..
기수정렬(Radix Sort) 기수정렬(Radix Sort) 개념 자릿수를 기준으로 정렬하는 알고리즘 비교를 하지 않는 알고리즘 양수만 가능 과정 특징 Least Significant Digit(LSD) 안정정렬 추가적인 메모리 공간 필요 정렬 대상의 모든 길이가 동일해야 효율적 시간 복잡도 O(dN) => N은 데이터의 개수, d는 데이터들의 최대 자리 수 Q. 왜 주로 낮은 자리 수부터 정렬? A. LSD의 경우 10000와 1을 비교할 때, Digit의 갯수만큼 확인 but MSD의 경우 중간에 정렬이 완료되면 더 살펴볼 필요가 없음 LSD의 코드 구현이 MSD에 비해 간결
[프로그래머스]Lv3. 미로 탈출 명령어(Python) https://school.programmers.co.kr/learn/courses/30/lessons/150365 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 (x, y)에서 (r, c)까지 이동하는 거리가 총 k인 경로 중 사전 순으로 가장 빠른 경로 구하기 격자의 바깥으로는 나갈 수 x 같은 격자를 두 번 이상 방문 가능함 S, E는 다름 해당하는 경로가 없다면 impossible 반환 여러 풀이 중에서 해당 문제를 그리디로 접근한 풀이를 참고해서 정리해 보았다. ('d') + ('l') + ('rl') + ('r') + ('u') 1...
[프로그래머스]Lv2. 무인도 여행(Python) https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 무인도에서 상하좌우 이동을 하여 인접한 무인도를 모두 탐색(BFS) 인접한 모든 무인도 방문 후 무인도의 합을 period에 추가 1. 상하 좌우의 이동을 체크할 델타 리스트 dx, dy 선언 2. 방문 여부를 나타내는 visited 리스트 생성 코드 dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def solution(maps): # 맵의 세로 길이와 가로 길이..
[프로그래머스]Lv2. 거리두기 확인하기(Python) https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 함수를 별도로 선언해 places 배열을 돌며 각 대기실 별로 체크 1. 같은 좌표 or 거리가 2 이상이면 pass 2. 거리가 1이면 위반 3. 거리가 2이면1. PXP => 가능 2. P => 가능 X P 3. PX PO PO => 불가능 OP OP XP 코드 def check(place): # x는 열 y는 행 p_list = [] for y in range(5): for x i..

티스토리툴바