문제 이해 단계 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 첫 번째 줄에 문장이 주어지고, 두 번째 줄에 폭발 문자열이라는 특정 키워드가 주어진다. 문장에서 폭발 키워드가 있으면 그 부분을 지운다. 그리고 문장을 이어 붙인다. 문장을 이어 붙였을 때, 또 키워드가 완성된다면 그 부분을 지운다. 이런 식으로 모든 폭발키워드를 지운 후, 남은 문장을 출력한다. 문제 접근 단계 제한사항부터 보자. 문장의 길이는 최대 1,000,0..

무선 랜의 구조 무선 랜이란? 무선 랜은 케이블을 사용하지 않고 전파를 이용하여 무선으로 컴퓨터를 연결 단점 유선보다 속도가 불안정하고 전파가 약하면 연결이 잘 안 됨 유선랜에 비해 통신 내용이 해킹될 위험이 높다 → 암호화나 인증 설정이 필요 무선 랜 구성 무선 액세스 포인트(WAP)와 무선 클라이언트(컴퓨터나 스마트폰)로 구성 무선 공유기에 무선 액세스 포인트 기능이 포함 컴퓨터가 무선 액세스 포인터와 통신하기 위해선 무선 랜 칩과 무선 랩 어댑터가 필요 최근에 나온 컴퓨터는 대부분 무선 랜 칩을 내장하고 있다. 무선 랜 어댑터 USB 메모리 방식 어댑터 컴퓨터 카드 방식 어댑터 인프라스트럭처 방식과 애드혹 방식이란? 인프라스트럭처(infrastructure) 방식 무선 액세스 포인터를 통해 통신하는..

문제 이해 단계 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 입력으로 정점의 개수 N과 간선의 개수 E가 주어진다. 여기서 간선은 양방향 그래프이다. 정점 1에서 정점 N까지 최단경로로 움직여야 하는데, 무조건 타깃으로 설정한 정점 A와 정점 B를 방문해야 한다. 여기서는 한번 이동했던 간선도 다시 이동하는 것을 허락한다. 이러한 조건일 때 두 정점을 반드시 거치면서 최단 경로로 이동할 때의 값을..

문제 이해 단계 https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 피보나치 수열이 존재한다. n이 입력으로 들어올 때, n번째 수열의 값을 구하는 것이 문제. 문제 접근 단계 이 문제가 골드 2인 데는 제한사항 때문이다. 입력으로 들어올 수 있는 n이 10^18까지 가능하다. 엄청나게 크다. int 자료형으로는 절대 받을 수 없고 가장 큰 자료형인 long long int를 써야지만 받을 수 있다. 기존에 풀던 DP방식으로 문제를 풀면 시간 복잡도가 O(n)이 나온다. 이는 결국 1초가 넘어 시간초과가 나오기 때문에 다른 ..

스케줄링 알고리즘 CPU 스케줄링은 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU 코어를 할당할 것인지를 결정 여러 가지 다른 CPU 스케줄링 알고리즘이 존재 여기서의 스케줄링 알고리즘은 처리 코어가 하나뿐이라고 가정하고 설명 → 즉 한 번의 하나의 프로세스만 실행할 수 있다는 뜻 선입 선처리 스케줄링(FCFS) 방식 : CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다. 가장 간단한 CPU 스케줄링 알고리즘 코드 작성과 이해가 쉽다. 선입 선처리 정책의 구현은 선입선출(FIFO) 큐로 쉽게 관리 가능 프로세스가 준비 큐에 진입하면, 이 프로세스의 프로세스 제어블록(PCB)을 큐의 끝에 연결 CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당 해당 프로세스(실행 상태의 프..

CPU 스케줄링 기본 개념 기본 가정 일반적인 스케줄링 개념을 논의하는 경우 → 프로세스 스케줄링 스레드에 국한된 개념을 가리키는 경우 → 스레드 스케줄링 “CPU에서 실행”이라는 용어를 사용하는 경우 → 프로세스가 CPU 코어에서 실행되고 있음을 의미 다중 프로그래밍 다중 프로그래밍의 목적 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데에 있음 대기 시간으로 인한 낭비를 줄여 시간을 생산적으로 활용하려고 시도한다. 대기 시간이 발생하는 이유 → 프로세스는 I/O 요청이 완료되기를 기다려야 함 다중 프로그래밍 개념 → 해당 개념은 모든 처리 코어로 확장됨 CPU를 항상 바쁘게 유지한다. → 다수의 프로세스를 메모리 내에 유지한다. 어떤 프로세스가 대기해야 하면, 운영체제는 CP..

문제 이해 단계 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 입력으로 A, B, C가 들어온다. 자연수 A를 B번 곱하고, C로 나눈 나머지를 출력해라. 문제 접근 단계 상당히 간단한 문제로 보인다. 하지만 그렇지 않다. 여기에는 2가지의 문제점이 존재한다. 첫 번째는, 수의 범위이다. 제한사항을 보면 입력이 2,147,483,647까지다. 입력부터 20억이 넘어가기 때문에 20억^20억 long long int 자료형을 아득히 넘어간다. 그렇기 때문에 지수를 한 번에 곱해서 구해서는 안된다. 자료형을 넘..

문제 이해 단계 https://www.acmicpc.net/problem/2263 이진트리의 정점이 1~n까지의 번호가 중복 없이 매겨져 있다. 이진트리의 중위 순회와 후위 순회가 입력으로 주어질 때, 전위 순회를 출력하는 문제 문제 접근 단계 전위, 중위, 후위 순회의 개념과 특성을 미리 알고 있어야 한다. 전위 순회 : 루트 → 왼쪽 → 오른쪽 중위 순회 : 왼쪽 → 루트 → 오른쪽 후위 순회 : 왼쪽 → 오른쪽 → 루트 그림을 보면서 하는 것이 가장 빠르다. 중위 순회 : 7 3 8 1 9 4 10 0 11 5 2 6 후위 순회 : 7 8 3 9 10 4 1 11 5 6 2 0 이 된다. 우리는 이 2가지 정보를 가지고 전위 순회를 구해야 한다. 일단 후위 순회는 루트 노드가 마지막에 오기 때문에,..