티스토리

검색하기내 프로필

블로그 홈

성장의 기록

구독자
0

구독하기 방명록
신고

인기글

  • [운영 체제] Deadlock공감수0댓글수0조회 1

주요 글 목록

  • [BOJ] 14502. 연구소 - java글 내용

    ⬛ [BOJ] 14502. 연구소 - java https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ⬛ 문제 정리 0은 빈칸, 1은 벽, 2는 바이러스 바이러스(2)는 벽을 통과할 수 없고 빈칸(0)으로만 확산된다. 꼭 3개의 벽을 세워야 하고 벽을 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 안전 영역 크기의 최댓값을 구하여라. ⬛ 풀이 방법 map을 채울 때 빈칸(0)의 개수를 센다. -> zeroCnt dfs를 이용하여 3개의 벽을 세우..

    좋아요0
    댓글7작성시간2022. 4. 11.
    게시글 이미지
  • [BOJ] 2458. 키 순서 - java (SWEA_5643)글 내용

    ⬛ [BOJ] 2458. 키 순서 - java https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net ⬛ 풀이 방법 인접 행렬을 만들고 방향있는 간선 사용 나보다 작은 학생들에 대한 정보와 나보다 큰 학생들에 대한 정보의 합이 N-1개면 나의 키가 몇번째인지 알 수 있다. BFS를 이용하여 주어진 정보에서 더 알아낼 수 있는 정보를 추가 학생별로 count 배열을 만들어 나보다 작은 학생들에 대한 정보나 큰 학생들에 대한 정보를 알 때마다 +1 ⬛ 소스..

    좋아요0
    댓글0작성시간2022. 4. 8.
    게시글 이미지
  • [자료 구조] Deque(Double-Ended Queue) - 자바글 내용

    Front와 Rear 양쪽에서 삽입(enQueue)과 삭제(deQueue)가 가능한 자료 구조 Deque의 앞쪽으로 삽입하고, 뒤쪽으로 삭제하면 Queue처럼 사용할 수 있다. Deque의 앞쪽에 삽입하고 다시 앞쪽으로만 삭제하면 Stack처럼 사용할 수 있다. ⬛ 연산 addFirst(x) : 데이터 x를 덱의 Front에 추가, 용량을 초과하면 exception 발생 push(x)와 동일 → 덱을 스택으로 사용하고자 할 때 사용됨 offerFirst(x) : 데이터 x를 덱의 Front에 추가, 용량을 초과하면 false를 리턴 removeFirst() : 덱의 Front에 있는 데이터 삭제, 비어있으면 Exception 발생 pop()과 동일 → 덱을 스택으로 사용하고자 할 때 사용됨 remove(..

    좋아요0
    댓글0작성시간2022. 4. 2.
    게시글 이미지
  • [운영 체제] 페이징과 세그멘테이션 기법글 내용

    ⬛ 단편화 메모리의 공간이 여러 조각으로 나뉘는 현상으로 합쳐보면 메모리 사용이 가능하지만 나누어져 있어 사용이 불가능한 상태 ◼ 내부 단편화 (Internal Fragmentation) 메모리를 분할하여 사용할 때 분할된 단위가 프로세스가 필요한 공간보다 더 커서 사용되지 못하고 남는 메모리가 발생하는 현상 ◼ 외부 단편화 (External Fragmentation) 메모리 할당 및 해제 작업의 반복으로 메모리와 사이에 사용하지 않는 메모리가 발생하고 이러한 메모리들을 합치면 프로세스 할당하기에 충분하지만 연속적인 공간이 아니기 때문에 사용하지 못하는 현상 ⬛ 연속 메모리 할당 방식 고정 분할 기법 : 메모리를 여러 개의 고정된 크기로 분할하고 하나의 메모리에 하나의 프로세스를 실행 → 내부 단편화 동..

    좋아요0
    댓글0작성시간2022. 4. 2.
    게시글 이미지
  • [Boj] 17070. 파이프 옮기기1 - java글 내용

    ⬛ 17070. 파이프 옮기기1 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net ⬛ 풀이 방법 현재 파이프의 상태가 가로일 때 세로로 가려는 시도는 제외, 현재 파이프의 상태가 세로일 때 가로로 가려는 시도는 제외 대각선으로 가려고 할 때는 현재 파이프의 위치에서 오른쪽, 아래쪽으로 갈 수 있는지 먼저 파악 -> isPossible 변수가 true라는 뜻은 대각선으로 갈 수 있는 가능성이 있다는 뜻이다. isPossib..

    좋아요0
    댓글0작성시간2022. 3. 22.
    게시글 이미지
  • [운영 체제] Deadlock글 내용

    Process1은 Resource1을 사용 중 Process2는 Resource2를 사용 중 Process1은 Resource2를 요청하고 Process2는 Resource1을 요청 서로 원하는 자원이 상대방에게 할당되어 있기 때문에 무한정 wait 상태에 들어감 → Deadlock 상태 데드락이란 교착상태라고도 불리며 상호 배제에 의해 나타나는 문제점이다. 2개 이상의 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우 ⬛ Starvation vs deadlock Starvation은 Ready 상태에서 발생하고 운이 없어 오래 기다릴 뿐 언젠가는 자원을 할당받을 확률이 있는 상태 deadlock은 Asleep 상태에서 발생하고 오래 기다려도 절때 발생할 확률이 없는 상태 ⬛ Deadlock 발생 필..

    좋아요0
    댓글0작성시간2022. 3. 19.
    게시글 이미지
  • [운영 체제] 프로세스와 관련된 System Call글 내용

    ⬛ 사전 지식 ◼ 커널 모드(Kernel Mode)와 사용자 모드(User Mode) 커널 모드 : 모든 자원(드라이버, 메모리, CPU)에 접근, 명령할 수 있다. 사용자 모드 : 프로그램의 자원에 함부로 접근하지 못하고 코드 작성, 프로세스 실행 등의 간단한 행동만 가능 ◼ System call ​ OS의 특정 기능을 쓸 수 있게 하는 인터페이스를 요청하는 함수 사용자 모드에서 System call함수를 이용하여 커널에 접근하고 커널 모드에서의 기능을 사용한다. ◼ PID 프로세스 식별 번호 ⬛ 프로세스 생성과 관련된 System call ◼ 프로세스의 생성 과정 부모 프로세스가 자식 프로세스를 복제 생성하여 트리 구조를 이룬다. 부모 프로세스의 주소공간 내용을 그대로 자식 프로세스의 주소 공간으로 ..

    좋아요0
    댓글0작성시간2022. 3. 19.
    게시글 이미지
  • [운영 체제] 운영체제 개요글 내용

    ⬛ 운영체제의 분류 ◼ 동시 사용자 수에 따라 단일 사용자(Single-user system) 다중 사용자(Multi-user system) ◼ 동시 실행 프로세스 수에 따라 단일 작업(Single-tasking system) : 시스템 내에 하나의 작업만 존재할 수 있기 때문에 하나의 프로그램 실행을 마친 뒤에 다른 프로그램을 실행할 수 있다. 다중 작업(Multi-tasking system) : 동시에 여러 작업을 수행할 수 있다. ◼ 작업 수행 방식에 따라 일괄처리 시스템(Batch processing system) 사용자의 요청 작업을 일정 시간 모아 두었다가 한번에 처리 시분할 시스템(Time-sharing system) CPU의 전체 사용시간을 나눠 여러 사용자들의 프로그램을 나눈 시간만큼 번..

    좋아요0
    댓글0작성시간2022. 3. 18.
    게시글 이미지
  • [운영 체제] 문맥 교환(Context Switching)글 내용

    ⬛ 문맥 교환(Context Switching) 실행중인 프로세스가 다른 프로세스에게 프로세서를 넘겨주는 과정 실행중인 프로세스의 context를 저장하고, 프로세서를 넘겨줄 프로세스의 context를 복구하는 일 프로세스에게 할당된 프로세서 사용 시간이 끝나거나 입출력 등을 해야할 때, 실행 중인 프로세스보다 우선 순위가 더 높은 프로세스가 프로세서를 요청할 때 인터럽트를 발생시켜 문맥 교환이 진행된다. Context Switching은 오버헤드를 발생시킨다. ◼ Context 프로세스를 실행시키기 위해 PCB에 저장되어 있는 프로세스와 관련된 정보들 ◼ Context Saving 실행중이였던 프로세스의 Context(레지스터 값)를 자신의 PCB에 저장 ◼ Context Restoring 예전에 PC..

    좋아요0
    댓글0작성시간2022. 3. 17.
  • [운영 체제] 프로세스와 프로세스의 상태글 내용

    ⬛ Process 프로그램이 메모리를 할당받으면 프로세스가 된다. → 프로세스는 실행 중인 프로그램을 의미 ⬛ Process Control Block(PCB) 프로세스가 생성되는 동시에 생성되며 각 프로세스들에 대한 정보를 저장하여 프로세스들을 관리하는 자료 구조 각 프로세스에 대한 PCB는 커널 공간에 존재한다. PCB가 관리하는 정보들 PID(Process Identification Number) : 프로세스 고유 식별 번호 스케줄링 정보 : 프로세스 우선 순위 등 프로세스 상태 : 생성, 준비, 실행, 대기, 완료 상태 메모리 관리 정보 : 프로세스의 주소 공간 등 입출력 상태 정보 : 프로세스에 할당된 입출력 장치, 파일 등에 대한 정보 등 문맥 저장 영역(context save area) : 프..

    좋아요0
    댓글0작성시간2022. 3. 17.
    게시글 이미지
  • [운영 체제] 메모리란?글 내용

    데이터를 저장하는 장치 ⬛ 메모리의 종류 ⬛ 레지스터 프로세서 내부에 있는 메모리로 명령을 빠르게 수행한다. 프로그램 카운터(Program Counter) : 다음에 수행될 명령어의 주소를 보관하는 레지스터 명령어 레지스터(Instruction Register) : 현재 실행중인 명령어를 보관하는 레지스터 누산기( ACCummulator) : 연산결과인 데이터를 일시적으로 저장하는 레지스터 이외에도 데이터 레지스터, 주소 레지스터, 메모리 주소 레지스터, 메모리 버퍼 레지스터가 있다. ⬛ 주기억 장치(Main Memory) CPU가 직접 접근할 수 있는 기억 장치로 프로세서가 수행할 프로그램과 데이터를 저장 CPU와 보조기억 장치와의 속도 차이로 인한 디스크 입출력 병목현상을 해소하기 위해 사용된다. ⬛..

    좋아요0
    댓글0작성시간2022. 3. 16.
    게시글 이미지
  • [자료 구조] Tree & Binary Tree의 개념 설명글 내용

    ⬛ Tree의 개념 원소들 간에 1 : n 관계, 계층 관계를 가지는 자료 구조 노드(Node)와 간선(Edge)으로 이루어진 자료구조 데이터를 순차적으로 저장하지 않기 때문에 비선형 자료 구조 Loop를 갖지 않는다. ⬛ Tree의 용어 노드(Node) : 트리의 기본 원소 간선(Edge) : 노드와 노드를 연결하는 선, 부모 노드와 자식 노드는 간선으로 연결되어 있다. 루트 노드(Root Node) : 트리의 시작 노드로 부모 노드가 없는 최상위 노드 부모 노드(Parent Node) : 자식 노드를 가진 노드 자식 노드(Child Node) : 부모 노드의 하위 노드 형제 노드(Sibling Node) : 같은 부모를 가지는 자식 노드들 서브 트리(Sub-tree) : 부모 노드와의 연결을 끊었을 ..

    좋아요0
    댓글0작성시간2022. 3. 2.
    게시글 이미지
  • [Boj] 2464. 비밀번호 - java글 내용

    ⬛ 2464. 비밀번호 https://www.acmicpc.net/problem/2464 2464번: 비밀번호 주어진 수 보다 작은 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수와, 주어진 수 보다 큰 수 중에서 이진수의 1의 개수가 같으며 가장 가까운 수를 한 줄에 빈칸을 사이에 두고 출력한다 www.acmicpc.net ⬛ 풀이 방법 1의 개수가 같으면서 가장 가까운 작은 수와 가장 가까운 큰 수를 찾기 입력받은 수를 이진수 리스트로 저장 (43 = 101011(2), list = [1, 1, 0, 1, 0, 1, 0]) 해당 수보다 더 작은 수를 찾기 위해서는 리스트를 인덱스 0부터 돌며 01이 되는 부분 찾아서 10로 swap ( [1, 1, 0, 1, 0, 1, 0] -> [1, 1, ..

    좋아요0
    댓글0작성시간2022. 2. 24.
    게시글 이미지
  • [SWEA] 1210. [S/W 문제해결 기본] 2일차 - Ladder1 - java글 내용

    ⬛ 1210. [S/W 문제해결 기본] 2일차 - Ladder1 - java https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14ABYKADACFAYh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ⬛ 풀이 방법 0으로 채워진 평면상에 사다리는 연속된 1로 표현되고, 도착 지점은 2로 표현된다. -> 2에서부터 거꾸로 올라가는 방법을 사용 현재 위치에서 왼쪽 또는 오른쪽에 1로 채워진 곳이 있다면 왼쪽 또는 오른쪽으로 이동 현재 위치에서 왼쪽 또는 오른쪽에 1로 채워진 곳이 없다면 위로 이동 맨 위에 도착할 때까지 반..

    좋아요0
    댓글0작성시간2022. 2. 23.
  • [자료 구조] Hash의 개념 설명글 내용

    매핑 : 하나의 값을 다른 값으로 대응시키는 것 해시 함수란 데이터를 효율적으로 관리하기 위해서 임의의 길이의 데이터(Key)를 고정된 길이의 데이터(Hash)로 매핑 ⬛ Hash Table 해시 테이블은 내부적으로 배열을 사용하여 저장하기 때문에 빠른 검색 속도를 가진다. 이때의 배열을 bucket이라고 한다. (key, value)를 저장하는 자료구조로 해시함수를 이용하여 key를 해시값으로 매핑하고, 이 해시값을 value를 저장하기 위한 인덱스로 사용 해시 테이블을 이용하여 데이터를 저장하면 key로 value를 찾을 때 해시 함수를 수행하여 value가 있는 위치를 찾을 수 있기 때문에 저장/삭제/조회 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가진다 전체 데이터의 양이 16이라고 하면 ..

    좋아요0
    댓글0작성시간2022. 2. 11.
    게시글 이미지
  • [SWEA] 1954. 달팽이 숫자 - java글 내용

    ⬛ 1954. 달팽이 숫자 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PobmqAPoDFAUq& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ⬛ 풀이 방법 배열이 채워지는 순서가 우->하->좌->상으로 반복 배열의 끝을 만나거나 이미 채워진 부분을 만났을 때 방향이 바뀐다. 채워지는 수인 num이 배열의 크기가 되었을 때까지 반복 ⬛ 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; ..

    좋아요0
    댓글0작성시간2022. 2. 8.
  • [SWEA] 1289. 원재의 메모리 복구하기 - java글 내용

    ⬛ 1289. 원재의 메모리 복구하기 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV19AcoKI9sCFAZN& SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com ⬛ 풀이 방법 0으로 초기화되어 있는 int orgBit 배열을 만들어 입력받은 String과 비교 해당 인덱스의 값이 다르다면 인덱스 이후의 배열값을 해당값으로 바꿈 값을 바꿀 때마다 count++ ⬛ 소스 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStr..

    좋아요0
    댓글0작성시간2022. 2. 4.
  • [자료 구조] Heap의 개념 설명과 구현글 내용

    ⬛ 사전 지식 1. 완전 이진 트리 각 노드가 최대 2개의 자식 노드를 갖는 이진 트리 중 왼쪽부터 차례대로 채워져 있는 트리 최하단 레벨의 노드는 좌측부터 채워져 있어야 한다. 2. 우선순위 큐 우선순위가 높은 데이터가 먼저 나가는 형태의 큐 모든 항목은 우선순위를 가지며 우선순위가 높은 요소가 우선순위가 낮은 요소보다 먼저 큐에서 삭제 우선순위 큐의 구현 방법 배열로 구현할 경우 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 연결리스트로 구현할 경우에도 노드간의 연결을 거쳐 우선순위를 비교하는 연산이 필요하기 때문에 최대 O(N)의 시간 복잡도를 가진다. 완전 이진트리인 힙으로 구현할 경우 최대 O(logN)의 시간 복잡도를 가진다. ⬛ Heap의 개념 우선순위 큐..

    좋아요0
    댓글0작성시간2022. 2. 3.
    게시글 이미지
  • [자료 구조] Queue 개념 설명과 구현글 내용

    ⬛ Queue 개념 한쪽 방향(Rear)에서는 자료의 삽입이, 다른 한 쪽 방향(Front)에서는 자료의 삭제가 이루어지는 FIFO(First In First Out) 형식의 자료 구조 Queue의 가장 먼저 들어온 요소를 Front, 가장 늦게 들어온 요소를 Rear라고 부르며 이 두가지 요소에 의해서만 접근이 가능 Rear에서 이루어지는 삽입 연산을 ‘enQueue’, Front에서 이루어지는 삭제 연산을 ‘deQueue’라고 한다. ⬛ Queue 연산 1. enQueue(int data) : Rear에 데이터를 추가 2. deQueue() : Front에 있는 데이터를 반환 후 삭제 3. peek() : Front에 있는 데이터를 반환 (삭제 x) ⬛ Queue 활용 프로세스 스케줄링 프린터 출력 ..

    좋아요0
    댓글0작성시간2022. 2. 2.
    게시글 이미지
  • [자료 구조] Stack 개념 설명과 구현(배열, 연결리스트)글 내용

    ⬛ Stack 개념 한 방향에서만 자료를 추가, 삭제할 수 있는 LIFO(Last In First Out) 형식의 자료 구조 가장 최근에 추가된 항목이 가장 먼저 삭제된다. 가장 최근에 추가된 데이터를 top이라고 부르고 추가와 삭제는 이 top에서만 이루어진다. 삽입하는 연산을 'push’라고 하며 삭제하는 연산을 ‘pop’이라고 한다. 만약 스택이 비어있을 때 자료를 꺼내려고 하면(pop) ‘Stack Underflow’가 발생 만약 스택이 꽉 차있을 때 자료를 넣으려고 하면(push) ‘Stack Overflow’가 발생 ⬛ Stack 연산 1. pop() : 스택에서 가장 위에 있는 항목(top)을 제거하며 반환 2. push(item) : item을 스택의 가장 윗 부분에 추가 3. peek()..

    좋아요0
    댓글0작성시간2022. 1. 31.
    게시글 이미지
문의안내
  • 티스토리
  • 로그인
  • 고객센터
© Kakao Corp.