본문 바로가기

분류 전체보기

 (65)
Solved.ac: 알고리즘 문제 풀이를 위한 필수 사이트 Solved.ac는 백준 온라인 저지(BOJ)를 기반으로 알고리즘 문제 풀이를 보다 효율적으로 할 수 있도록 도와주는 서비스이다. 백준은 국내에서 가장 많은 알고리즘 문제를 제공하는 사이트로 유명한데, Solved.ac는 이러한 문제들을 효율적으로 정리하고 난이도, 추천 문제 등을 제공해 사용자가 학습 목표를 체계적으로 세울 수 있도록 도와준다.그리고 재미있는 사실 하나! 이 훌륭한 서비스를 만든 사람이 바로 내 직속 선배이신 서강대 컴퓨터공학과 박수현님 이라는 점이다.처음에 베타 버전으로 시작했을 때만 해도 이렇게 커질 줄은 몰랐는데, 이제는 아예 회사를 차리고 대표님이 되셨다.Solved.ac의 주요 기능Solved.ac는 문제 풀이를 시작하는 초보자부터 고급 알고리즘 문제를 도전하는 상급자까지 모두..
알고리즘 시간 복잡도 계산하기: 효율성을 높이자! 시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간을 수학적으로 표현한 것으로, 입력의 크기에 따라 실행 시간이 어떻게 증가하는지 나타낸다. 이 시간 복잡도 계산은 효율적인 알고리즘을 설계하고, 문제의 제약 조건에 맞게 최적의 접근을 찾기 위한 핵심적인 과정이다.이번 글에서는 시간 복잡도를 계산하는 기본 개념과 방법을 설명하고자 한다.시간 복잡도를 왜 계산해야 할까?시간 복잡도를 계산하는 것은 알고리즘의 효율성을 예측하기 위해 중요하다. 시간 제한이 있는 프로그래밍 문제에서, 알고리즘이 제한 시간 내에 문제를 해결할 수 있을지 판단하려면 시간 복잡도를 알고 있어야 한다.시간 복잡도를 표현하기 위해 O 표기법(Big-O Notation), Θ 표기법(Theta Notat..
프로그래밍 문제 해결을 위한 가이드: 접근법, 자료 구조, 시간 복잡도 분석까지 프로그래밍 문제 해결을 위한 접근법프로그래밍 문제 해결 능력(PS, Problem Solving)은 여러 분야에서 유용하며, 특히 컴퓨터 과학과 관련된 학문이나 직무에서 필수적이다. 문제를 푸는 데 필요한 자료 구조와 알고리즘, 그리고 제한 조건을 이해하고 이를 코드로 구현하는 것이 중요한데, 여기에는 몇 가지 핵심 과정이 있다. 이번 글에서는 문제 해결에 필요한 다양한 접근 방식과 대회 및 학습 자료들을 소개한다.문제 해결 실력을 쌓아가는 5단계 비법프로그래밍 문제를 푸는 과정은 마치 보물찾기 같다. 처음에는 막막할 수 있지만 단계를 따라가다 보면 어느새 보물에 가까워진다. 하나하나 단계를 살펴보자.1. 문제를 정확히 이해하기문제를 마주하면 일단 목표부터 확실히 잡아야 한다. 입력과 출력 형식부터 제한..
[C] 백준 2268 수들의 합 7 https://www.acmicpc.net/problem/2268문제 분석 및 접근 방식문제에서 요구하는 것은 배열 A에 대해 두 가지 연산을 효율적으로 처리하는 것이다:Sum(i, j): 배열의 A[i]부터 A[j]까지의 합을 구하는 연산.Modify(i, k): 배열의 A[i]를 k로 업데이트하는 연산.제약 조건에 따르면 배열의 크기(N)와 연산 횟수(M) 모두 최대 1,000,000으로, 최악의 경우 Sum과 Modify 연산을 모두 포함하여 최대 백만 번의 연산을 수행해야 한다. 단순히 모든 구간을 반복하며 합을 구하거나, 각 Modify 연산에 대해 배열을 새로 갱신하면 시간 초과가 발생할 가능성이 높다.따라서 구간 합과 부분 배열 업데이트를 모두 빠르게 수행할 수 있는 자료 구조가 필요하다. ..
함수형 언어 F# 개요 F# 언어에 대한 소개F#는 함수형 프로그래밍 언어로, 특히 프로그래밍 언어를 다루는 작업에 매우 유용하다. 마이크로소프트가 개발한 F#는 .NET 플랫폼에서 실행되며, 다른 함수형 언어와 달리 생산성 높은 프로그래밍을 돕는 강력한 도구와 라이브러리를 제공한다. 다음에서는 F#의 주요 개념과 기본 문법을 소개하고, 이를 통해 F#이 제공하는 독특한 프로그래밍 방식과 장점을 살펴본다.F#의 특징과 환경함수형 프로그래밍 패러다임F#는 함수형 언어로, 명령형 프로그래밍이 아닌 표현 중심의 프로그래밍을 지향한다. 일반적인 명령형 언어(C/C++, Python 등)에서는 컴퓨터가 수행할 작업 순서를 명령하지만, F#는 수학적 표현과 같은 표현식을 통해 코드를 작성한다.예시: let x = 10 let y = ..
2-5. Virtualization: Multi-Level Feedback Queue 스케줄링(Scheduling)은 CPU를 어떤 프로세스에 할당할지 결정하는 중요한 기술이다.그중에서도 Multi-Level Feedback Queue(MLFQ)는 현대 운영체제에서 널리 사용되는 스케줄링 방식이다. "모두를 만족시키는 스케줄러를 만들 수는 없을까?"라는 물음에서 시작된, MLFQ의 여정을 함께 살펴보자.간단한 스케줄러들, 그리고 그들의 한계 🤔FIFO (First In, First Out)장점: 단순하다!단점: "convoy effect"가 발생.예를 들어, 앞에 있는 작업이 엄청 느리면 뒤의 작업이 전부 대기 상태로 전환된다.→ 결과적으로 CPU와 I/O 자원 이용률이 낮아짐.SJF (Shortest Job First)장점: 평균 대기 시간, 평균 완료 시간이 줄어든다.단점: "작업 ..
Callout test 보호되어 있는 글입니다.
2-4. Virtualization: Scheduler(FIFO, SJF, STCF, RR)와 성능 지표 운영체제에서 CPU 사용률(CPU Utilization)을 극대화하려면 멀티프로그래밍이 필수다.그러나, 하나의 CPU 코어는 동시에 하나의 프로세스만 실행할 수 있다.이 때문에 CPU 스케줄링이 필요하다. 스케줄링 알고리즘은 프로세스의 실행을 효율적으로 관리해 시스템 성능을 최적화하고,각종 성능 지표(CPU Utilization, Response Time 등)를 개선하는 데 초점이 맞춰져 있다.CPU 스케줄링과 프로세스 실행 과정CPU-I/O Burst Cycle프로세스 실행은 CPU 실행(CPU Execution)과 I/O 대기(I/O Wait)가 반복되는 사이클로 이루어진다.CPU burst는 일반적으로 짧은 CPU burst가 많은 I/O bound 작업과 긴 CPU burst가 적은 작업으로 구..
2-3. Virtualization: Limited Direct Execution OS는 프로그램 코드를 메모리에 Load한다. (process의 address space에)프로그램의 run-time Stack이 할당된다. (지역 변수, 함수 인자, return 주소)main(argc, argv)로 stack initHeap 설정 (Dynamically allocated area; malloc())I/O 설정 (STDIN, STDOUT, STDERR 등)main(): 프로그램 시작실행 중인 프로그램에 limit가 없다면, OS는 그 어떤 것에도 제어권을 갖지 않고, 그저 library가 될 것이다.Direct Execution의 문제프로세스가 해서는 안될 instruction (I/O to disk, CPU/Memory 접근)CPU로 제어권을 다시 가져오기 힘듦. (ex. 무한루프)#..
2-2. Virtualization: 파일 디스크립터와 입출력 관리 I/O redirection이란 file, command, program, script의 출력 결과를 다른 file, ...의 입력으로 전달하는 것을 말한다.shell이 fork()하고 exec("wc", "wc w3.c")를 수행한다.→ exec(...)하기 전, shell이 STDOUT(1)을 닫고 open("newfile.txt")한다.File Descriptor & File Descriptor TableFile Descriptor는 파일, 디렉토리, 또는 기기를 나타내는 정수값이다.각 프로세스는 File Descriptor Table을 가지고 있는데, STDIN(0), STDOUT(1), STDERR(2)는 기본으로 열려 있다.각 System Call 정리:open(): 새로운 file descr..
2-1. Virtualization: 프로세스 관리와 자료구조, Process API 프로세스 가상화Process(프로세스)는 실행 중인 프로그램으로 정의한다.Program이 디스크 상에 존재하는 명령어와 정적 데이터의 묶음이라면(Passive),Process는 program counter가 있는 동적인 존재이다(Active).실행 가능한 파일을 memory에 load하여 program이 process가 된다.→ 하나의 프로그램이 여러 프로세스를 생성할 수 있다.Process는 Code section / Data section / Stack / Heap / Program counter로 이루어진다.OS는 Virtualization으로 CPU가 여러 개인 듯한 illusion(착각;환영)을 만들어낸다. (Time Sharing; 시분할)Process의 Machine StateAddress ..
1. 운영체제 개요 프로그램은 매우 단순한 일을 한다:명령어를 메모리에서 Fetch하고,Decode하고 (무슨 명령어인지 파악),Data를 얻고 (연산),Execute한다.OS는 여러 프로그램을 쉽게 실행하게끔 하고, 프로그램 간의 메모리 공유, 장치와 상호작용할 수 있게 한다.System Call을 사용해 OS에 원하는 작업을 수행시킬 수 있다.OS는 Virtualization을 통해 다음을 가능하게끔 한다:CPU 공유Memory 공유Disk 공유CPU 가상화A program that loops and prints (cpu.c)#include #include #include #include #include #include "common.h" // Contains Spin() functionint main(int argc..

티스토리툴바