본문 바로가기

분류 전체보기

 (386)
[boj] 백준 16637 괄호 추가하기 (c++) - dfs, 브루트포스 [문제] https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net [풀이] dfs를 이용해서 풀 수 있다. 괄호를 묶는 경우, 현재 idx와 idx+2 가 피연산자가 되고, idx+1이 연산자가 된다. 따라서 이들의 계산 값과 현재 값을 계산해준 결과를 curr에 담아 dfs를 호출하는데, 이때 idx는 idx+4가 된다. 괄호를 묶지 않는 경우의 idx는 idx+2가 되며 curr에는 현재 idx와 이전 curr을 계산한 결과를 넘겨준다...
[boj] 백준 17779 게리맨더링2 (c++) - 브루트포스, 구현 [문제] https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net [풀이] 브루트포스 문제로 전부 탐색을 해줘야 한다. 선거구를 나누는 기준인 4개의 꼭짓점에 대해 미리 저장해놓고 풀면 조금 덜 헷갈린다. 선거구 채울 때 조건이 어긋나지 않도록 주의해야 하는 문제였다.. [코드] #include #include #include #include #include #include #include #define INF 987654321 using namespace ..
[운영체제] 2. System Structure & Program Execution (2) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. 동기식 입출력과 비동기식 입출력 - 동기식 입출력 (Synchronous I/O) I/O 요청 후 입출력 작업이 완료된 후에야 제어가 사용자 프로그램에 넘어감 구현 방법 1 I/O가 끝날 때까지 CPU를 낭비시킴 매시점 하나의 I/O만 일어날 수 있음 구현 방법 2 I/O가 완료될 때까지 해당 프로그램에게서 CPU를 빼앗음 I/O처리를 기다리는 줄에 그 프로그램을 줄 세움 다른 프로그램에게 CPU를 줌 동기식 입출력에서는 입출력 연산이 끝날 때까지 CPU는 아무 일을 수행할 수 없다. 기본적으로 CPU의 명령 수행 속도는 외부 장치에서 데이터를 읽어오는 등의 입출력 연산보다 상대적으로 빠르기 때문에 CPU가 입출력 연산을 기..
[운영체제] 2. System Structrue & Program Execution (1) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. 컴퓨터 시스템 구조 - CPU CPU는 연산을 수행하는 산술논리장치(ALU), 제어 명령을 전달하는 컨트롤 장치(CU), 결과 값을 일시적으로 기억하는 레지스터(Register)로 이루어져 있다. - Memory CPU의 Register 용량은 매우 작기 때문에 정보를 저장해서 읽어 들여올 주 기억 장치가 필요하다. 주 기억장치로는 ROM, RAM 등이 있으며 컴퓨터가 켜지면 운영체제, 사용자 프로그램 등이 메모리 공간에 올라간다. CPU는 주기억장치에서 프로그램들의 명령어 등을 읽음으로써 작업을 수행한다. - I/O Device 입출력 장치란 사용자가 원하는 문자나 그림 데이터를 컴퓨터로 전달하여 입력하거나 출력하는 장치이..
[운영체제] 1. Introduction to Operating Systems 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. 운영 체제란 무엇인가? - 운영체제(Operating System) : 컴퓨터 하드웨어 바로 위에 설치되어 사용자 및 다른 모든 소프트웨어와 하드웨어를 연결하는 소프트웨어 계층 - 좁은 의미에서는 커널, 운영체제의 핵심 부분으로 메모리에 상주하는 부분을 가리키며, 넓은의미로는 커널 뿐 아니라 각종 주변 시스템 유틸리티를 포함한 개념이다. 2. 운영 체제의 목적 - 인터페이스 제공 하드웨어를 직접 다루는 복잡한 부분을 운영체제가 대행하며, 동시 사용자/프로그램들이 각각 독자적 컴퓨터에서 수행되는 듯한 환상을 제공한다. - 자원 관리 & 보호 프로세서, 기억장치, 입출력 장치 등 컴퓨터 시스템 자원을 효율적으로 관리해준다. (사..
[boj] 백준 2812 크게 만들기 (c++) - deque [문제] https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [풀이] deque을 이용해서 풀 수 있다. [코드] #include #include #include #include #include #include #include #define INF 987654321 using namespace std; int n, k; string s; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> k; cin >> s; deque dq; for(i..
[boj] 백준 11437 LCA (c++) - LCA [문제] https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net [풀이] LCA(Lowest Common Ancestor) 최소 공통 조상을 구하는 문제이다. 부모 노드가 같아질 때까지 u = parent[u] 로 이동시키면 된다. 주의할 점은 u, v를 부모노드로 이동시키기 전 깊이(depth, level)을 맞춰야 한다. 깊이가 다르다면 동시에 거슬러 올라갈 때 가르키는 노드가 같아질 수가 없으므로 깊이를 맞춘 후 이동시키도록 한다. [코드]..
[알고리즘] 소수 판별 알고리즘 - 에라토스테네스의 체 1. 에라토스테네스의 체란? 제목 그대로 소수를 판별하는 알고리즘으로서 소수들을 대량으로 빠르게 구할 수 있는 방법이다. O(N^1/2)의 시간복잡도를 갖는다. 원리 소수란 1과 자기자신만을 약수로 갖는 수를 의미한다. 즉, 1을 제외한 어떤 수의 배수가 되는 수들은 모두 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 특성을 이용한다. 임의의 수 n 까지의 소수를 구하고자 할 때, 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제거시키는 방식으로 동작한다. ※ 왜 n의 제곱근까지만 확인해도 되는지? 2. 구현 (c++) using namespace std; int n; int prime[1001]; void primeNum(){ // prime 배열 초기화 for (int i = 2; i

티스토리툴바