code-lab1의 등록된 링크

키자드에 등록된 총 302개의 포스트를 확인하실 수 있습니다.

Tistory

[프로그래밍 언어론] 객체 지향 프로그래밍(OOP : Object Oriented Programming)란? OOP의 장단점

객체 지향 프로그래밍(OOP)과 객체(Object) 객체 지향 프로그래밍은 컴퓨터 프로그램을 명령어의 목록으로 보는 시각에서 벗어나 여러 개의 독립된 단위, 즉 "객체"들의 모임으로 파악하고자 하는 컴퓨터 프로그래밍의 패러다임 중 하나이다 객체 지향 프로그래밍에서 객체(Object)란 실제 사물을 프로그래밍으로 옮겨와 모델링하는 것으로 자신의 속성(PROPERTY)과 행위(Method)를 가지고 있다. 객체의 속성은 객체의 상태, 성질, 데이터 등을 의미하고, 행위란 객체의 기능이나 데이터를 조작하는 연산 등을 의미한다. 객체의 데이터를 사용하기 위해서는 메시지 전송(message Sending)을 통해 간접적으로 데이터를 얻어와야 한다. 객체지향 프로그래밍은 아래와 같이 크게 4가지의 특징을 가지고 있..

원문보기 내부링크
Tistory

[백준] 16953번 A->B (자바 풀이)

문제 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 이 문제는 재귀 함수를 이용해 간단하게 해결 할 수 있다. 1. 2를 곱한다 -> A*2 2. 1을 수의 가장 오른쪽에 추가한다 -> A*10 +1 위의 두 연산을 DFS 형태로 재귀적으로 부르면 브루트포스 방식으로 해결 가능하다. 간단하게 풀렸을것 같지만, 처음 시도했을때 틀렸습니다를 받았다. 뭐가 문제일까 고민하다가, 변수의 타입을 int로 한게 문제였음을 깨달았다. dfs() 함수에서 if(num > B) return; 이라는 코드가 있는데, 만약 num*2를 계속해서 하다가 int의 범위를 벗어나면 이 부분이 문제가 발생할 수 있다. 따라서 int를 long 타입으로 바..

원문보기 내부링크
Tistory

[프로그래밍 언어론] 파라미터 전달 방식(pass by value, pass by reference, pass by result, pass by value-result, pass by name) 비교 | call by value와 call by reference

파라미터 전달 방식 프로그래밍을 공부한 사람은 다들 Call by value 혹은 Call by reference 등에 대해 들어본 적이 있을 것이다. 이는 함수 호출 방식을 값에 의한 호출, 참조에 의한 호출로 구분한 것이다. 함수 호출 방식에 따라 파라미터 전달 방식이 달라지는데, 이에 대해 알아보자. Pass by value (= Call by value) 1. Pass by value는 함수의 파라미터로 변수의 값을 복사해서 전달하는 방식이다. 2. 즉, 원래의 값에 영향을 주지 않고 함수 내로 복사된 값을 전달한다. 3. 값을 복사하기 때문에 변수의 크기가 클수록 비용이 증가하게 된다. 4. 따라서 크기가 큰 변수를 파라미터로 전달할 때 적절한 방법이 아니다. 5. 원래의 값이 변경되면 안 되는..

원문보기 내부링크
Tistory

[백준] 1051번 -숫자 정사각형 (자바 풀이)

문제 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 1. N, M이 50 이하로 작다. 2. 꼭짓점을 살펴보기 위해서는 기준점에서 3군데만 찾아보면 된다. 3. N과 M중 더 작은 수가 정사각형의 최대길이다. 4. 따라서 최대 50(N)*50(M)*3(꼭짓점 3개 비교)*50(정사각형의 최대 길이) 번의 연산이 필요하므로 브루트포스 방식이 가능하다! 풀이법은 간단하다. 정사각형의 최대 길이는 N과 M 중 더 작은 것일 것이다. 이것을 len이라고 하자. 매번 모든 원소를 조사할 필요 없이 세로는 N-l..

원문보기 내부링크
Tistory

[프로그래밍 언어론] 바인딩(Binding), 바인딩 타임(Binding Time)에 대하여

바인딩(Binding) Binding은 연관 짓는 것이다(association). 예를 들어 엔티티(Entity)와 속성(Attribute), 심벌(symbol)과 연산자(operation)를 연관 짓는 것 등을 binding이라고 한다. 바인딩 타임(Binding Time) 바인딩 타임은 결정되는 시점에 따른 분류로 구분지을 수 있다. 언어 디자인 시점(at language design time) - 대부분의 언어에서 제어 흐름 구조, 기본 유형 집합, 복잡한 유형을 만드는 데 사용할 수 있는 생성자 및 언어론의 많은 측면들이 언어를 디자인할 때 선택된다. 언어 구현 시점(at language implementation time) - 대부분의 언어 매뉴얼이 언어 구현자의 재량에 다양한 이슈를 남긴다. ..

원문보기 내부링크
Tistory

[프로그래밍 언어론] 댕글링 포인터(Dangling Pointer)란? 댕글링 포인터 해결법

댕글링 포인터(Dangling Pointer)란? 댕글링 포인터는 적절한 타입의 유효한 객체를 가리키고 있지 않은 포인터를 말한다. 예를 들어 이미 할당 해제된 메모리를 포인터가 계속 가리키고 있다면 해당 포인터는 댕글링 포인터이다. 예를 들어 메모리에 할당된 하나의 객체를 가리키는 두 개의 포인터 ptr1, ptr2가 있다고 하자. 이때 ptr1만을 free 하여 메모리를 해제해주면 ptr2는 Dangling Pointer가 돼버린다. 댕글링 포인터 해결법 1. Tombstone Approach 첫번째 방법은 tombstone(비석)이라고 불리는 특별한 cell을 설정해 포인터가 할당된 객체를 직접 가리키지 않고 비석을 통해 가리키도록 하는 방법이다. 예를 들어 [그림 3]처럼 ptr1을 free 한다..

원문보기 내부링크
Tistory

[프로그래밍 언어론] 단축 평가 계산(Short-circuit Evaluation)

단축 평가 계산 (Short-circuit Evaluation) 단축 평가 계산이란 첫 번째 인수가 값을 결정하기에 충분하지 않은 경우에만 두 번째 인수가 평가되는 일부 프로그래밍 언어(C, C++, JAVA 등)의 일부 논리 연산(AND, OR)의 계산이다. 예를 들어 C언어의 경우를 들어보자. int i=1; int j=2; if( ij가 거짓이므로 논리 연산 AND(&&)의 결과 값이 무조건 거짓이 되기 때문에 뒤의 연산을 진행하지 않는다. 따라서 i=3은 실행되지 않는다. 단축 평가 계산을 염두에 두고 프로그래밍한다면 시간 복잡도를 줄일 수 있다. 예를 들어 아래와 같은 경우를 살펴보자. // func1() - 1초 소요 // func2() - 100초 소요 /* 첫번째 방법 */ if( func..

원문보기 내부링크
Tistory

[운영체제] 페이지 교체 알고리즘 (FIFO/OPT/LRU/LFU/MFU)

페이지 교체 알고리즘 (Page Replacement Algorithm) 이전 포스팅으로 요구 페이징(Demand Paging)에 대해 알아보았다. 필요한 페이지가 메모리에 없을 때 page-falut가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다. 페이지 교체 알고리즘은 page-fault 발생 비율을 줄이는 것을 목표로 한다. +요구 페이징에 대한 내용은 다음을 참고하자. [운영체제] 가상메모리(Virtual Memory)와 요구 페이징(Demand Paging), Valid-Invalid Bit, 페이지 부재(Page Faul 가상 메모리(V..

원문보기 내부링크
Tistory

[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터

AVL 트리란? 예전에 이진탐색트리에 대해 알아본적이 있다. [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현 이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다 code-lab1.tistory.com 이진탐색트리는 큰 문제점이 있으니, 위 그림과 같이 한쪽으로 노드가 쏠릴 수가 있다. 10,9,8,7,6을 순서대로 삽입한다고 생각해보면 저런 형태의 트리가 만들어진다는 것을 알 수 있을 것이다. 위와 같은 형태의 트리에서 특정 값을 찾으려면 O(N)의 시간이 필요할 것이다. 예를 들..

원문보기 내부링크
Tistory

[자료구조] 레드-블랙 트리(Red-Black Tree)란? | 레드-블랙 트리 쉽게 이해하기

레드-블랙 트리(Red-Black Tree) 레드-블랙 트리는 자가 균형 이진 탐색 트리이다. 레드-블랙 트리는 다음과 같은 조건들을 만족한다. 1. 모든 노드는 빨간색 혹은 검은색이다. 2. 루트 노드는 검은색이다. 3. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 4. 빨간색 노드의 자식은 검은색이다. == No Double Red(빨간색 노드가 연속으로 나올 수 없다) 5. 모든 리프 노드에서 Black Depth는 같다. == 리프노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 트리 관련 용어를 잘 모르겠다면 다음 포스팅을 참고하자. [자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리..

원문보기 내부링크
Tistory

[JAVA] 자바(JAVA)란? 자바의 특징

자바(JAVA)란? 자바는 C언어에 객체 지향적 기능을 추가하여 만든 C++과 달리, 처음부터 객체 지향 언어로 개발된 프로그래밍 언어이다. 자바는 자바 가상 머신(JVM, Java Virtual Machine)을 사용하여 운영체제와 독립적으로 동작할 수 있다. 따라서 자바는 어느 운영체제에서나 같은 형태로 실행 될 수 있다. 자바의 특징 자바는 객체지향 언어이다. 객체를 만들기 위해서 설계도인 클래스를 작성하고, 객체와 객체를 연결하여 목적에 맞는 프로그램을 만든다. 객체지향 언어의 특징인 캡슐화, 상속성, 다형성을 완벽하게 지원한다. 이식성이 높다 자바 실행환경이 설치되어 있는 모든 운영체제에서 실행 가능하다. 하이브리드 언어이다. 컴파일 언어인 동시에 인터프리터 언어이다. 텍스트 소스를 컴파일하여 ..

원문보기 내부링크
Tistory

[운영체제] 세그멘테이션(Segmentation)이란?, 세그멘테이션 vs 페이징

세그멘테이션(Segmentation)이란? 페이징은 프로세스를 물리적으로 일정한 크기로 나눠서 메모리에 할당하는 것을 의미한다. 반면, 세그멘테이션은 프로세스를 논리적 내용을 기반으로 나눠서 메모리에 배치하는 것을 의미한다. 세그멘테이션은 프로세스를 세그먼트(segment)의 집합으로 표현한다. 이때 세그먼트는 논리 단위로 아래와 같은 것들이 해당된다. main program procedure function method object stack local variable global variable etc... 프로세스를 code영역, data영역, stack영역 등으로 나누는 것 또한 세그멘테이션이라고 할 수 있다. 세그멘테이션도 페이징과 비슷하게 세그먼트 테이블을 가지고 있다. 페이징과 비슷하게 논리..

원문보기 내부링크
Tistory

[운영체제] Copy On Write(COW)란? | Copy On Write 예시

Copy On Write (COW) 란? 1 2 3 4 5 6 std::string x("Hello"); std::string y = x; // x and y use the same buffer y += " World!"; // now y uses a different buffer // x still uses the same old buffer cs 위와 같은 코드가 있다고 하자. ( C++ 98에서의 동작이다. C++ 11 이상에서는 동작하지 않음 ) x라는 buffer에 "Hello" 라는 string을 넣고, y라는 복사본을 만든다고 하자. 이때 x와 y는 같은 buffer를 가리키게 된다. 하지만 이때 복사본인 y를 변경하면 아래와 같이 된다. 더이상 y는 같은 buffer를 가리키지 않고, 새로..

원문보기 내부링크
Tistory

[운영체제] 가상메모리(Virtual Memory)와 요구 페이징(Demand Paging), Valid-Invalid Bit, 페이지 부재(Page Fault)과정

가상 메모리(Virtual Memory) 메인 메모리의 크기는 한정되어 있다. 따라서 물리적인 메모리 크기보다 크기가 큰 프로세스는 실행시킬 수 없게 된다. 예를 들어 메인 메모리의 크기가 100MB 일 때 300MB 크기의 프로세스는 실행시킬 수 없다. 크기가 큰 프로세스를 실행시키기 위해서는 메인 메모리를 크게 키우는 방법이 있겠지만, 이것은 매우 비효율적이다. 따라서 나온 방법이 바로 가상 메모리(Virtual Memory)이다. 가상 메모리는 메모리 관리 기법의 하나로, 기계에 실제로 이용 가능한 자원을 추상화하여 사용자들에게 매우 큰 메모리인 것처럼 보이게 만드는 것을 말한다. 즉, 프로그램에 실제 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식이다. 가상적으로 주어진 주소를 가상 주소(vi..

원문보기 내부링크
Tistory

[DB] NoSQL이란?, NoSQL 특징, NoSQL 종류, NoSQL 장점

NoSQL이란? NoSQL은 비관계형 데이터베이스를 지칭한다. 즉, 관계형 데이터 모델을 지양 하며 대량의 분산된 데이터를 저장하고 조회하는 데 특화되었으며 스키마 없이 사용 가능하거나 느슨한 스키마를 제공하는 저장소를 말한다. NoSQL은 기존 RDBMS 형태의 관계형 데이터베이스가 아닌 다른 형태의 데이터 저장 기술을 의미하며, 관계형 데이터베이스의 한계를 극복하기 위한 데이터 저장소의 새로운 형태이다. NoSQL의 특징 RDBMS와 달리 데이터 간의 관계를 정의하지 않는다. RDBMS는 데이터 관계를 외래키 등으로 정의하고 JOIN 연산을 수행할 수 있지만, NoSQL은 JOIN 연산이 불가능하다. RDBMS에 비해 대용량의 데이터를 저장할 수 있다. 페타바이트 급의 대용량 데이터를 저장할 수 있다..

원문보기 내부링크
Tistory

[운영체제] 내부 단편화, 외부 단편화란? | 외부단편화 해결 방법

내부 단편화 (Internal Fragmentation) 내부 단편화란 주기억장치 내 사용자 영역이 실행 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남게 되는 현상을 말한다. 예를 들어 아래와 같은 그림을 살펴보자. 위와 같이 100MB의 메모리에 80MB 크기의 프로세스를 올리게 되면, 20MB의 내부 단편화가 발생하게 된다. 즉, 적은 크기의 잔여 메모리가 발생해 해당 메모리를 사용할 수 없게 된다. 외부 단편화 (External Fragmentation) 외부 단편화란 남아있는 총 메모리 공간이 요청한 메모리 공간보다 크지만, 남아있는 공간이 연속적(contiguous)이지 않아 발생하는 현상이다. 예를 들어 아래와 같은 그림을 살펴보자. 위와 같이 남아있는 메모리 공간은 50..

원문보기 내부링크
Tistory

[운영체제] 페이징(Paging)이란? 페이지 테이블이란?

페이징(Paging)이란? 페이징이란 논리주소의 메모리를 고정된 크기의 페이지(Page)로 나누어 관리하는 기법이다. 페이징은 아래와 같은 특징들을 갖고 있다. 물리주소 공간(Physical address)은 연속적이지 않을 수 있다(noncontiguous) 페이지는 모두 같은 크기를 가진다. 물리주소 공간을 페이지와 같은 사이즈로 나눈 것들을 프레임(Frame)이라고 한다. 페이지 사이즈(=프레임 사이즈)는 하드웨어에 의해 정해진다. 페이지의 크기는 일반적으로 2의 제곱수를 사용한다. 일반적으로 4KB(2^12) ~ 1GB(2^20) 페이지 테이블(page table)을 이용해 논리주소에서 프레임을 가리키는 물리주소로 매핑한다. 외부 단편화는 발생하지 않으나, 내부 단편화는 발생한다. 단편화에 대해서..

원문보기 내부링크
Tistory

[운영체제] 페이지 테이블 구조 (Hierarchical Page Table, 2-level Page Table, Hashed Page Table, Inverted Page Table)

Hierarchical Page Table 하나의 페이지 테이블 안에 여러개의 페이지 테이블을 넣은 페이지 테이블을 의미한다. 이 중 대표적으로 2-level page table에 대해 알아보자. 32-bit machine, 4K page size를 가정했을 때, 논리 주소는 아래와 같이 구성된다. page number : 20bit p1-page number : 10bit p2-page offset : 10bit page offset : 12bit 즉 p1은 outer page table(바깥 테이블)의 index이고, p2는 해당 바깥 테이블에서의 위치를 나타낸다. 이해가 쉽지 않다면 다음 그림을 살펴보자. p1을 통해 outer-page table의 인덱스를 찾고, 해당 인덱스가 가리키는 page ..

원문보기 내부링크
Tistory

[DB] 인덱스(index)란? 인덱스 자료구조

인덱스(index)란? 인덱스란 데이터베이스 테이블의 검색 속도를 향상하기 위한 자료구조라고 할 수 있다. 책의 색인(index)을 보면 해당 내용이 어디에 있는지 알 수 있듯이 데이터의 인덱스를 참조하면 데이터가 저장된 레코드의 주소를 알 수 있는 것이다. DBMS는 데이터베이스 테이블의 모든 데이터를 검색해서 원하는 결과를 가져오기에는 시간이 너무 많이 걸리므로 칼럼의 값과 해당 레코드가 저장된 주소를 키와 값의 쌍으로 인덱스를 만들어둔다. DBMS의 인덱스는 항상 정렬된 상태를 유지하기 때문에 원하는 값을 탐색하는 데는 빠르지만 새로운 값을 추가하거나 삭제, 수정하는 경우에는 쿼리문 실행 속도가 느려진다. 결론적으로 DBMS에서 인덱스는 데이터의 저장 성능을 희생하고 데이터의 읽기 속도를 높이는 기..

원문보기 내부링크
Tistory

[DB] 이상현상(anomaly), 함수 종속성(Functional Dependency)이란?

이상현상이란? 삽입 이상(Insertion Anomaly) : 튜플 삽입 시 특정 속성에 해당하는 값이 없어 NULL을 입력해야 하는 현상 삭제 이상(Deletion Anomaly) : 튜플 삭제 시 같이 저장된 다른 정보까지 연쇄적으로 삭제되는 현상 갱신 이상(Update Anomaly) : 튜플 갱신 시 중복된 데이터의 일부만 갱신되어 일어나는 데이터 불일치 현상 함수 종속성(FD : Functional Dependency)이란? 함수 종속성은 어떤 속성 A의 값을 알면 다른 속성 B의 값이 유일하게 정해지는 관계를 종속성이라고 한다. A->B로 표기하며 A를 B의 결정자(Determinant)라고 한다. A->B이면 A는 B를 결정한다(Determine) 한다고 하고, B는 A에 종속한다(Depen..

원문보기 내부링크
Tistory

[DB] 정규화(Normalization)란? 정규화 예시, 1NF, 2NF, 3NF, BCNF

정규화(Normalization)란? 정규화는 이상현상이 있는 릴레이션을 분해하여 이상현상을 없애는 과정이다. 이상현상이 존재하는 릴레이션을 분해하여 여러 개의 릴레이션을 생성하게 된다. 이를 단계별로 구분하여 정규형이 높아질수록 이상현상은 줄어들게 된다. 정규화의 장점 데이터베이스 변경 시 이상 현상(Anomaly)을 제거할 수 있다. 정규화된 데이터베이스 구조에서는 새로운 데이터 형의 추가로 인한 확장 시, 그 구조를 변경하지 않아도 되거나 일부만 변경해도 된다. 데이터베이스와 연동된 응용 프로그램에 최소한의 영향만을 미치게 되어 응용프로그램의 생명을 연장시킨다. 정규화의 단점 릴레이션의 분해로 인해 릴레이션 간의 JOIN연산이 많아진다. 질의에 대한 응답 시간이 느려질 수도 있다. 데이터의 중복 속..

원문보기 내부링크
Tistory

[DB] 키, 후보키, 기본키, 슈퍼키, 대체키, 외래키란?

키(Key)란? 키는 데이터베이스에서 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 튜플들을 서로 구분할 수 있는 기준이 되는 속성(Attribute)를 말한다. 키가 필요한 이유 테이블 내에서 어떤 데이터를 찾는다고 하자. 수 많은 데이터 중 내가 원하는 데이터를 찾으려면 엄청난 탐색 시간이 필요할 것이다. 이러한 탐색 시간을 줄여줄 수 있는 것이 키다. 후보키 (Candidate Key) 후보키는 릴레이션을 구성하는 속성들 중에서 튜플을 유일하게 식별하기 위해 사용하는 속성들의 부분집합, 즉 기본키로 사용할 수 있는 속성들을 말한다. 하나의 릴레이션내에서는 중복된 튜플들이 있을 수 없으므로 모든 릴레이션에는 반드시 하나 이상의 후보키가 존재한다. 후보키는 릴레이션에 있는 모든 튜플에 대해서 유일성..

원문보기 내부링크
Tistory

[운영체제] 동기화 문제(Synchronization problem), 경쟁 상태(Race Condition), 임계 영역(Critical Section)

동기화 문제 (Synchronization Problem) 동시에 공유 자원에 접근하는 것은 데이터의 일관성을 해칠 수 있다. 프로세스들의 실행 순서를 정하여 공유 자원의 일관성을 보장하는 것을 동기화(Synchronization)라고 한다. 경쟁 상태 (Race Condition) 여러 프로세스들이 공유 자원에 동시에 접근하려고 하는 상황을 경쟁 상태라고 한다. 어떤 프로세스가 마지막으로 데이터에 접근했는지에 따라 데이터의 상태가 달라지게 된다. 즉, 데이터의 일관성을 보장할 수 없어진다. 이런 경쟁 상태의 문제를 해결하기 위해 프로세스들은 동기화(Synchronized)되어야 한다. 임계 영역 (Critical Section) 임계 영역은 공유 자원이 접근되는 부분을 뜻한다. 만약 어떤 프로세스가 임..

원문보기 내부링크
Tistory

[DB] 트랜잭션(Transaction)이란? ACID란?

트랜잭션(Transaction)이란? 트랜잭션은 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 수행되어야할 일련의 연산들을 의미한다. 트랜잭션은 작업의 완전성을 보장해준다. 즉, 논리적인 작업 셋을 모두 완벽하게 처리하거나 또는 처리하지 못할 경우에는 원 상태로 복구해서 작업의 일부만 적용되는 현상이 발생하지 않게 만들어주는 기능이다. 사용자의 입장에서는 작업의 논리적 단위로 이해를 할 수 있고 시스템의 입장에서는 데이터들을 접근 또는 변경하는 프로그램의 단위가 된다. 트랜잭션은 SELECT, UPDATE, INSERT, DELETE와 같은 연산을 수행하여 데이터베이스의 상태를 변화시키는 작업의 단위다. 트랜잭션의 특징(ACID) Atomicity(원자성)..

원문보기 내부링크
Tistory

[DB] 트랜잭션의 고립(격리) 수준(Isolation Level) | 고립 수준 예시

트랜잭션의 고립 수준(Isolation Level)이란? 트랜잭션의 고립 수준이란 트랜잭션들끼리 일관성 있는 데이터를 얼마나 허용할 것인지 정해놓은 수준이다. 즉, 트랜잭션 수행 중 다른 트랜잭션이 해당 데이터를 조회하는 것이 가능한 정도를 결정해 놓은 것이다. 고립 수준이 높을수록 일관성은 보장되지만 그만큼 동시성이 떨어져 성능이 하락한다. 트랜잭션에 대해 잘 모르겠다면 다음 게시물을 참고하자. [DB] 트랜잭션(Transaction)이란? | ACID 트랜잭션(Transaction)이란? 트랜잭션은 데이터베이스의 상태를 변환시키는 하나의 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 수행되어야할 일련의 연산들을 의미한다. 트랜잭션은 code-lab1.tistory.com 이상 현상의 종류 D..

원문보기 내부링크
Tistory

[운영체제] fork() 함수란? , fork() 함수 예제 , 부모 자식 프로세스

fork() 함수란? Unix 환경에서 fork() 함수는 함수를 호출한 프로세스를 복사하는 기능을 한다. 이때 부모 프로세스와 자식 프로세스가 나뉘어 실행되는데, 원래 진행되던 프로세스는 부모 프로세스(parent), 복사된 프로세스를 자식 프로세스(child) 라고 한다. fork() 함수는 프로세스 id, 즉 pid 를 반환하게 되는데 이때 부모 프로세스에서는 자식 pid가 반환되고 자식 프로세스에서는 0이 반환된다. 만약 fork() 함수 실행이 실패하면 -1을 반환한다. 프로세스에 대해 잘 모르겠다면 다음을 참고하자. [운영체제] 프로세스란? 프로세스 메모리 구조, 상태, 스케줄링 프로세스(Process)란? 프로세스는 실행 중인 프로그램(program)을 뜻한다. 그렇다면 프로그램은 무엇인가?..

원문보기 내부링크
Tistory

[DB] 데이터베이스란? DBMS 란?

데이터베이스란? 데이터베이스(Database)는 통합 관리되는 데이터들의 집합을 뜻한다. 데이터베이스를 사용하는 이유는 뭘까? 다음과 같은 이유들을 들 수 있겠다. 데이터 공유 : 많은 사람들이 데이터를 공유할 수 있다. 중복의 제거 : 데이터를 한 곳에 모으면서 중복되는 데이터를 제거할 수 있다. 데이터 통합 : 흩어져 있는 데이터를 한 곳에 모을 수 있다. 보안성 : 권한이 있는 관리자만이 데이터를 관리한다면 데이터의 보안을 지킬 수 있다. 이외에도 다양한 이점이 있다. DBMS(DataBase Management System)란? DBMS는 데이터베이스 관리 시스템으로 데이터베이스 내의 데이터에 접근할 수 있도록 하는 소프트웨어들을 의미한다. DBMS는 어떻게 탄생하게 됐을까? DBMS 이전에는 파..

원문보기 내부링크
Tistory

[운영체제] 프로세스 제어 블록(PCB : Process Control Block)란? | 문맥교환(Context Switching)이란?

프로세스 제어 블록(Process Control Block)란? 프로세스 제어 블록(이하 PCB)은 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영 체제 커널의 자료 구조이다. 쉽게 말하면 운영체제가 프로세스를 제어하기 위해 프로세스의 상태 정보를 저장해 놓는 구조체이다. PCB는 다음과 같은 항목들을 저장하고 있다. Process Id : 프로세스의 고유 번호 Process State : ready, wait, running 등의 실행 상태 Program Counter(PC) : 프로그램 카운터, 다음 실행될 명령의 포인터 CPU registers : CPU 레지스터 CPU scheduling information : CPU 스케줄링 정보 Memory-management information..

원문보기 내부링크
Tistory

[운영체제] IPC(Inter-Process Communication)란? | pipes

IPC란? IPC는 Inter-Process Communication 의 줄임말로 프로세스간의 통신을 위한 메커니즘을 의미한다. 즉 IPC는 프로세스간의 통신을 돕는다. IPC는 다음과 같이 두 가지 모델이 존재한다. Shared Memory Message Passing 프로세스에 대해 자세히 알고 싶다면 다음을 참고하자. [운영체제] 프로세스란? 프로세스 메모리 구조, 상태, 스케줄링 프로세스(Process)란? 프로세스는 실행 중인 프로그램(program)을 뜻한다. 그렇다면 프로그램은 무엇인가? 프로그램은 명령어들의 모음을 포함한 디스크에 저장된 파일이다. 프로그램이 실행되면 이 code-lab1.tistory.com Shared Memory Shared Memory 방식은 말 그대로 프로세스들이 ..

원문보기 내부링크
Tistory

[운영체제] 쓰레드(Thread)란? | 쓰레드 프로세스 차이 | 멀티프로세스 멀티쓰레드 차이

쓰레드란(Thread)란? 쓰레드(Thread)란 프로세스 내에서 실행되는 흐름의 단위 혹은 CPU 스케줄링의 기본 단위 라고 할 수 있다. 쓰레드는 다음과 같은 특징을 가지고 있다. 쓰레드는 각자 자신의 Stack 영역을 보유한다. ( 최소한 자신의 레지스터 상태를 보유한다 ) 쓰레드는 프로세스 내에서 Code, Data, Heap 영역을 공유한다. 쓰레드를 생성하고 switching 하는 것은 inexpensive(비싸지않은) 하다. 쓰레드와 프로세스 차이 쓰레드와 프로세스는 다음과 같은 차이들이 존재한다. 프로세스는 각자 프로세스간의 통신에 IPC가 필요하다. 쓰레드는 쓰레드 간의 통신에 IPC가 필요하지 않다. 각 프로세스는 Code, Data, Heap, Stack 영역을 각자 보유한다. 쓰레드..

원문보기 내부링크
Tistory

[운영체제] 다중쓰레드모델(Multithreading model)이란?

사용자 수준 쓰레드(User level Thread) vs 커널 레벨 쓰레드(Kernel Level Thread) 사용자 수준 쓰레드는 사용자 수준(user level)에서 실행되며 thread library에 의해 관리된다. 커널 수준 쓰레드는 커널 수준(kernel level)에서 실행되며 커널에 의해 직접 관리된다. 이런 커널을 멀티쓰레드 커널(Multithreded kernel)이라고 부른다. - 현대 대부분의 OS가 멀티쓰레드 커널이다. 사용자 수준 쓰레드와 커널 수준 쓰레드는 서로 맵핑(mapping)된다. non-multithreaded kernels에서 유저 수준 쓰레드는 일반적인 프로세스처럼 처리된다. 커널이 쓰레드를 인식할 수 없어 맵핑이 이루어지지 않기 때문이다. multithrede..

원문보기 내부링크
Tistory

[운영체제] CPU 스케줄링 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin

CPU 스케줄링(CPU Scheduling)이란? CPU 이용률을 극대화하기 위해서는 멀티프로그래밍(multiprogramming)이 필요하다. 하지만 만약 CPU core가 하나라면 한 번에 하나의 프로세스만 실행 가능할 것이다. 이때 필요한 것이 CPU 스케줄링이다. 즉, CPU 스케줄링은 언제 어떤 프로세스에 CPU를 할당할지 결정하는 작업이라고 할 수 있다. CPU 스케줄러(CPU Scheduler)와 선점형(Preemptive), 비선점형(non-preemptive) 스케줄링 CPU 스케줄러는 메모리에 있는 프로세스들 중 어떤 프로세스를 실행할지 선택하고 CPU를 할당해주는 역할을 한다. CPU 스케줄러는 프로세스들이 다음과 같은 상황에 있을 때 스케줄링을 결정한다. 실행(running) 상태에..

원문보기 내부링크
Tistory

[알고리즘] 벨만 포드(Bellman-Ford) 알고리즘 | c++ 벨만포드 구현

벨만 포드 알고리즘(Bellman-Ford Algorithm) 벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다. 따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 다익스트라 알고리즘에 대해 알고싶다면 다음 포스팅을 참고하자. [알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다..

원문보기 내부링크
Tistory

[네트워크] 라우팅 알고리즘 비교 | Link State 알고리즘, Distance Vector 알고리즘

라우팅 알고리즘 라우팅 알고리즘이란 송신 측에서부터 수신 측 라우터의 네트워크를 통과하는 최적의 경로를 결정하는 알고리즘이다. 그러나 실제로는 여러 가지 이유로 최적의 경로를 결정하지 못할 수 있다. 예를 들어 'A기관은 B기관이 소유한 네트워크가 보낸 패킷을 전달해서는 안된다'와 같은 규칙 등이 존재할 수 있다. 그럼에도 불구하고 최대한 최적의 경로를 결정하는 라우팅 알고리즘은 네트워크 분야에서 매우 중요하다. 라우팅 알고리즘 분류 라우팅 알고리즘은 중앙 집중형 혹은 분산형인지로 구분할 수 있다. 중앙 집중형(global) 라우팅 알고리즘 : 네트워크 전체에 대한 완전한 정보를 가지고 출발지와 목적지 사이의 최소 비용 경로를 계산한다. 즉 모든 라우터가 연결 상태와 링크 비용을 알고 있다는 것이다. L..

원문보기 내부링크
Tistory

[운영체제] 프로세스란? 프로세스 메모리 구조, 상태, 스케줄링

프로세스(Process)란? 프로세스는 실행 중인 프로그램(program)을 뜻한다. 그렇다면 프로그램은 무엇인가? 프로그램은 명령어들의 모음을 포함한 디스크에 저장된 파일이다. 프로그램이 실행되면 이 프로그램의 명령어들과 데이터가 메모리에 적재되고 이것이 프로세스가 된다. 프로세스의 메모리 구조 각 프로세스는 위 그림과 같은 구조를 갖는다. 각 영역은 다음과 같은 역할을 한다. Code 영역 : 프로그램을 실행시키는 실행 파일 내의 명령어들이 위치하는 공간 Data 영역 : 전역변수, static 변수들이 위치하는 공간 Heap 영역 : 동적할당을 위한 메모리 영역( malloc(), new 등) Stack 영역 : 지역 변수, 파라미터(함수에 전달되는 인자)가 위치하는 공간 프로세스 상태(Proces..

원문보기 내부링크
Tistory

[네트워크] IP fragmentation, reassembly | IP 단편화

IP 단편화(fragmentation) network links는 MTU(Max Transfer Size)를 가진다. 링크 계층 프로토콜마다 다른 링크 타입과 MTU를 가지므로 네트워크는 큰 IP datagram을 분할할 필요성이 있다. 이러한 IP datagram을 여러 조각의 datagram으로 쪼개서 전송하고 최종 목적지에서 재결합(reassembly) 된다. IP 헤더를 통해 본래 하나의 datagram이었는지 구분하고 순서를 확인하게 된다. 4000byte datagram을 3개의 datagram으로 쪼개서 전송했다고 하자. 각 datagram은 헤더가 20byte씩을 차지한다. 즉 처음 datagram도 헤더가 20byte를 차지하므로 data field는 3980이다. 또한 MTU는 1500..

원문보기 내부링크
Tistory

[네트워크] IP,IP 클래스, IPv4, IPv6이란? | IP 클래스 구분

IP 주소 IP는 Internet Protocol의 약자로 기기간 네트워크 통신을 할 때 쓰는 프로토콜을 의미한다. IP에서 IP 기기의 주소를 나타내는 것이 바로 IP주소이다. 흔히 우리가 사용하는 IP는 이 IP주소를 의미한다. 우편배달을 예로 들자면 IP주소는 배달 주소를 나타내게 된다. 즉 IP주소를 사용하는 이유는 각각의 host들을 구분하여 데이터를 정확하게 송수신하기 위해서이다. 이러한 IP주소는 IPv4와 IPv6 체계로 나뉜다. 먼저 IPv4에 대해서 알아보자. IPv4 IPv4는 3자리 숫자가 4마디로 표기되는방식이다. 각 마디는 옥텟(octet)이라고 부른다. 위 주소는 내부적으로 32비트(각 마디당 8bit)로 처리된다. 예를 들어 192.168.123.123은 11000000.10..

원문보기 내부링크
Tistory

[네트워크] 서브넷, 서브넷마스크, 서브넷팅이란? | 서브넷팅 예제

서브넷의 등장 배경 흔히 사용되는 IPv4 주소 체계는 클래스를 나누어 IP를 할당한다. 하지만 이 방식은 매우 비효율적이다. 예를 들어 어떤 기관에 A 클래스를 할당한다고 하면 16,777,214개의 호스트를 할당할 수 있게 되는데, 이 기관이 100개의 호스트를 할당한다고 하더라도 16,777,114개의 호스트가 낭비되게 된다. 이러한 비효율성을 해결하기 위해 네트워크 장치들의 수에 따라 효율적으로 사용할 수 있는 서브넷(subnet)이 등장하게 되었다. 혹시라도 IP 클래스에 대해 모르겠다면 다음 포스팅을 참고하자. [네트워크] IP,IP 클래스, IPv4, IPv6이란? | IP 클래스 구분 IP 주소 IP는 Internet Protocol의 약자로 기기간 네트워크 통신을 할 때 쓰는 프로토콜을 ..

원문보기 내부링크
Tistory

[네트워크] poisoned reverse란? count to infinity 문제 해결법 | DV 알고리즘

Count to infinity 문제 Distance Vector 알고리즘(이하 DV 알고리즘)은 다른 라우터로 가는 최적 경로를 forwarding table에 저장해놓는다. 위와같은 상황에서 Y에서 X로 가는 비용이 60으로 증가한다면 어떻게 될까? ( 이해를 쉽게하기 위해 x라우터의 forwarding 정보는 무시하자 ) Y라우터는 인접 라우터들에 자신이 X로 가는 비용이 60으로 증가했음을 알리고, 최적 경로를 다시 계산하게 된다. 이 때Y라우터는 Z로부터 Z는 X라우터 까지 가는데 5의 비용이 든다는 정보를 얻게 된다. 오직 주변 노드의 정보로만 경로를 판단하기에 Y는 Z 노드까지만 가면 어떻게든 Z에서 X까지 5의 비용으로 갈 수 있다고 생각해 Y에서 Z를 가는 비용 1을 더해 X노드까지 6의..

원문보기 내부링크
Tistory

[네트워크] TCP란? | TCP의 특징 | TCP RDT | tcp 3way handshake

TCP란? TCP(Transmission Control Protocol)는 애플리케이션에서 보낸 데이터를 신뢰성 있게 수신 측에 전송을 보장하는 프로토콜이다. 다음과 같은 특징들을 가진다. point-to-point : 하나의 송신 측과 하나의 수신 측이 통신하는 1:1 통신이다. reliable : 신뢰성 있는 데이터 전송을 보장한다. pipelined : TCP 흐름 제어와 혼잡 제어가 window size를 설정한다. full duplex(전이중 통신) : 쌍방향 통신이 가능하다. 즉 데이터를 주고받을 수 있다. connection-oriented : 연결 지향적이다. 송신 측과 수신 측이 데이터를 교환하기 전에 handshaking을 한다. flow control : 흐름 제어를 한다. conge..

원문보기 내부링크
Tistory

[알고리즘] 다익스트라(Dijkstra) 알고리즘이란? | c++ 다익스트라 구현

다익스트라(Dijkstra) 알고리즘이란? 다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다. 다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능) 다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문) 2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다. 위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자. ..

원문보기 내부링크
Tistory

[네트워크] TCP 혼잡제어(congestion control)| AIMD, Slow Start | TCP Reno, Tahoe

TCP 혼잡 제어란? 혼잡(congetion)하다는 것은 너무 많은 source가 너무 많은 data를 너무 빨리 전송해 네트워크가 이를 처리하지 못하는 상태를 말한다. 조금 더 자세히 설명하자면 데이터의 양이 수신 측에서 처리할 수 있는 양을 초과하게 되면 송신 측에서는 수신 측에서 처리하지 못한 데이터를 손실 데이터로 간주하고 계속 재전송하게 되므로 네트워크가 더욱더 혼잡하게 된다. 이러한 혼잡 상태를 제어하는 것을 혼잡 제어라고 한다. TCP 혼잡 제어의 여러 가지 방법을 알아볼 것인데, 그전에 TCP에 대해 잘 모르겠다면 다음 포스팅을 참고하자. [네트워크] TCP란? | TCP의 특징 | TCP RDT | 3-way handshake TCP란? TCP(Transmission Control Pro..

원문보기 내부링크
Tistory

[네트워크] 패킷 스케줄링 기법(Scheduling Policies) | Round Robin, WFQ(Weighted Fair Queuing)

스케줄링 기법(Scheduling Mechanisms) 네트워크에서 스케줄링은 link 상으로 보낼 다음 패킷(packet)을 선택하는 것을 뜻한다. 스케줄링 기법에는 여러가지가 존재하는데, 그 중 몇 가지만 알아보자. FIFO(First In First Out) 스케줄링 FIFO 스케줄링은 간단하게 큐에 도착한 순서대로 전송하는 기법을 뜻한다. 이 때 만약 큐가 가득찼을 때 패킷을 버린다면 어떤 패킷을 버려야 할까? 이것도 다음과 같이 여러가지 방법이 있다. tail drop : 방금 도착한 패킷을 버린다. priority : 우선순위에 기반해 패킷을 버린다. random : 랜덤으로 패킷을 버린다. Priority 스케줄링 가장 높은 우선순위의 패킷을 먼저 전송하는 기법을 뜻한다. Round Robi..

원문보기 내부링크
Tistory

[네트워크] UDP란? UDP의 개념과 이해 | UDP checksum

UDP란? UDP(User Datagram Protocol)는 비연결형, 신뢰성이 없는 전송 프로토콜이다. IP데이터그램을 캡슐화하여 보내는 방법과 연결 설정을 하지 않고 보내는 방법을 제공한다. UDP는 TCP/IP 5계층에서 Transport Layer(전송계층)의 프로토콜이다. UDP의 특징 UDP는 흐름제어, 오류제어 또는 손상된 세그먼트의 수신에 대한 재전송을 하지 않는다. 따라서 내용이 전송 중에 손실 될 수 있고, 전송되는 세그먼트의 순서가 바뀔 수 있다. UDP는 TCP보다 간단하고 빠르다. 작은 header size를 가지고 있다. 흐름제어를 하지 않기 때문에 전송 속도를 최대한 빠르게 할 수 있다. 수신자와 송신자 간의 handshaking이 없는 connectionless 성질을 가진..

원문보기 내부링크
Tistory

[네트워크] Reliable Data Transfer - rdt 1.0/2.0/2.1/2.2/3.0 | RDT란? | FSM 이란?

RDT(Reliable Data Transfer)란? RDT는 신뢰성 있는 데이터 교환을 의미한다. 즉 송/수신하는 데이터가 오류 없이 온전히 전송되는 것을 뜻한다. Transport Layer(전송계층)에서는 신뢰성 있는 데이터 교환을 하고 싶어 하지만, 하위 레이어들에서는 신뢰성을 보장할 수 없기 때문에 문제가 발생할 수 있다. 이를 해결하기 위해 Transport Layer에서 RDT 프로토콜을 이용할 수 있다. 아래는 RDT 프로토콜을 이용해 데이터를 송/수신하는 예시이다. 송신 측 상위 레이어에서 보내려는 데이터가 있다면 rdt_send()를 호출해 데이터를 RDT 프로토콜로 전송한다. RDT 프로토콜에서 신뢰할 수 없는 채널인 하위 레이어로 보낼 때 udt_send()를 호출해 패킷을 전송한다..

원문보기 내부링크
Tistory

[네트워크] pipelined protocols(Go-Back-N, Selective Repeat)이란? | selective repeat 딜레마(dilemma)

pipelined protocols pipelined protocols에서 pipelining은 송신자가 다수의 패킷을 한 번에 보내는 것을 말한다. 즉 ACK신호를 받을 때까지 기다리다 ACK신호를 받고 나서 다음 데이터를 보내는 stop and wait 방식과 다르게 송신자가 ACKs 신호를 받지 않아도 패킷 여러 개를 보내는 방식이다. 송신자와 수신자가 버퍼를 가져야 하며, 대표적인 두 가지 프로토콜로 Go-Back-N과 Selective Repeat이 있다. 참고 : stop and wait 방식의 RDT [네트워크] Reliable Data Transfer - rdt 1.0/2.0/2.1/2.2/3.0 | RDT란? | FSM 이란? RDT(Reliable Data Transfer)란? RDT는..

원문보기 내부링크
Tistory

[알고리즘] 퀵 정렬(Quick Sort)이란? | c언어 퀵 정렬 구현

퀵 정렬(Quick Sort) 퀵 정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다. 1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다. 2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. 3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다. 3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 ..

원문보기 내부링크
Tistory

[알고리즘] 기본 정렬 알고리즘 비교| stable vs not stable| in-place vs not in-place | 선택 정렬(selection sort), 버블 정렬(bubble sort), 삽입 정렬(insertion sort), 합병 정렬(merge sort), 퀵 정렬(quick sort)

정렬 알고리즘이란? 정렬 알고리즘은 n개의 숫자가 주어졌을 때 이를 사용자가 지정한 기준에 맞게 정렬하는 알고리즘이다. 아주 간단한 알고리즘부터 조금 복잡한 알고리즘까지, 여러가지 알고리즘을 알아보고 비교해보자. 우선 정렬 알고리즘을 비교하기 전에 stable 과 not stable의 차이, in-place와 not inplace 개념에 대해 알아보자. stable vs not stable stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻한다. 예를 들어, int arr[5] = { 7, 3, 6, 2, 3 } 과 같이 3값이 두 번 들어 있는 배열이 있다고 하자. 이것을 어떠한 정렬 알고리즘으로 정렬 했을 때 중복 된 키 값이 처음 순서대로 정렬 되었다면 stable s..

원문보기 내부링크
Tistory

[네트워크] HTTP란? non-persistent HTTP vs persistent HTTP | RTT란?

Web 과 HTTP 웹 페이지는 객체(object)로 구성된다. 객체(object)는 HTML 파일, JPEG 이미지, JAVA applet, 오디오 파일 등이 될 수 있다. 웹페이지는 여러 참조된 객체를 포함하는 기본 HTML 파일로 구성되며, 각 개체는 URL로 주소 지정이 가능하다. HTTP HTTP(Hyper Text Transfer Protocol)는 텍스트 기반의 통신 규약으로 인터넷에서 데이터를 주고받을 수 있는 프로토콜이다. TCP/IP 5계층에서 Application Layer(어플리케이션 계층)에 속하는 프로토콜이다. HTTP의 동작 client 측에서 브라우저를 통해 어떠한 서비스를 요청(request)하면 server에서 해당 요청사항에 맞는 결과를 찾아 사용자에게 응답(respon..

원문보기 내부링크
Tistory

[알고리즘] 선택정렬(Selection Sort)이란? | c언어 선택정렬 구현

선택정렬(Selection Sort) 선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다. 1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다. 2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다. 3. 다음 인덱스에서 위 과정을 반복한다. 과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다. 예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자. 가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다. 다음은 5와 그 이후 값들 중 가장 작은 값인 3의 ..

원문보기 내부링크
Tistory

[알고리즘] 버블정렬(bubble sort)이란? | c언어 버블정렬 구현

버블 정렬(Bubble Sort) 버블 정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다. 위와 같은 배열을 오름차순으로 버블 정렬한다고 하자. 처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다. 다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다. 다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다. 1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다. 버블정렬의 특징 버블 ..

원문보기 내부링크
Tistory

[알고리즘] 삽입정렬(insertion sort)이란? | c언어 삽입정렬 구현

삽입 정렬(Insertion Sort) 삽입 정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 위와 같은 배열을 오름차순으로 정렬한다고 하자. 두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다. 5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다. 세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다. 네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다. 그 앞의 원소 5와 4를..

원문보기 내부링크
Tistory

[알고리즘] 백트래킹(Backtracking) | C언어 N-Queen구현

백트래킹이란? 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다. 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다. 해가 될 가능성이 있다면 유망하다(promising)고 한다. N-Queen 문제 N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 ..

원문보기 내부링크
Tistory

[네트워크] OSI 7계층이란? TCP/IP 5계층이란?

계층화(Layering)란? 계층화란 모듈들이 계층(Layer)을 이루도록 역할과 책임을 세분화 하는 것을 말한다. 시스템을 구성하는 모듈들의 상관 관계를 의존성을 이용해 구분한다. 상위 계층의 모듈은 하위 계층에서 제공하는 인터페이스를 이용해 구현되어야 한다. 계층화의 예로 비행기 서비스의 예를 들어보자. 어떤 사람이 출발 항공에서 도착 항공 까지 비행 서비스를 이용하는 것을 계층화(Layering) 한 것을 나타냈다. 매표소 계층, 수화물 계층, 게이트 계층, 활주로 계층, 비행기 계층으로 나누어 각각 계층이 역할과 책임을 세분화하여 맡는다. 이렇게 계층화를 하는 이유가 무엇일까? 계층화의 장점 복잡한 시스템을 파악하기 쉽게 단순화 시킬 수 있다. 시스템의 업데이트와 유지보수를 쉽게 할 수 있다. 한..

원문보기 내부링크
Tistory

[자료구조] 그래프(Graph)의 개념과 이해, 용어 | 인접행렬 vs 인접리스트 그래프 구현

그래프란? 그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다. 그래프 G는 객체를 나타내는 정점 V(vertex)와 객체를 연결하는 간선 E(edge)의 집합이다. 트리도 그래프의 한 종류이며, 그 중 사이클(cycle)이 허용되지 않는 그래프를 말한다. 그래프의 종류 방향 그래프 vs 무방향 그래프 간선에 방향이 있는 그래프는 방향 그래프(Directed Graph) 라고 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 한다. 완전 그래프 완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻한다. 정점이 N개인 무방향 그래프에서 최대 간선 수 : N(N-1)/2 개 ( ex..

원문보기 내부링크
Tistory

[자료구조] 해시 테이블(Hash Table) 이란? , 해시 알고리즘 , 해시 함수

해시 테이블(Hash Table)이란? 해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다. 해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다. 해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Fucntion) 해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에..

원문보기 내부링크
Tistory

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

DFS란? DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다. DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. DFS 예시 위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다. 가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다. 이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다) 이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다. 이후 스택..

원문보기 내부링크
Tistory

[알고리즘] 너비 우선 탐색(Breadth First Search : BFS) 이란?

너비 우선 탐색, BFS 란? BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고 [자료구조] 큐(Queue)의 개념, 이해 | c언어 큐 연결리스트로 구현, 소스코드 큐(Queue) 란? 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스 code-lab1.tistory.com BFS..

원문보기 내부링크
Tistory

[자료구조] 트리의 순회, 중위 순회, 전위 순회, 후위 순회 | C언어 트리 순회 구현

트리의 순회 이 게시글에서 설명하는 트리의 순회는 이진트리를 기준으로 한다. 이진 트리에 대해 모른다면 다음 포스팅을 참고하자. [자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 code-lab1.tistory.com 트리의 순회 중 중위(inorder) 순회, 전위(preorder) 순회, 후위 순회(postorder) 순회에 대해 알아보자. 여기서 설명할 때 L은 Left, V는 Visit, R은 Right를 의미한다. 즉 왼쪽 서브 트리, 노드 방문, 오..

원문보기 내부링크
Tistory

[자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현

이진탐색트리(Binary Search Tree)이란? 이진탐색트리란 다음과 같은 특징을 갖는 이진트리를 말한다. ( #이진트리 - 각 노드의 자식 노드가 최대 2개인 트리) 1. 각 노드에 중복되지 않는 키(key)가 있다. 2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. 3. 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. 4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 예를 들어 다음과 같은 트리가 이진탐색트리이다. 이진 탐색 트리의 특징 이진 탐색 트리는 기존 이진트리보다 탐색이 빠르다. 이진 탐색 트리의 탐색 연산은 트리의 높이(height)가 h라면 O(h)의 시간 복잡도를 갖는다. 이러한 효율적인 탐..

원문보기 내부링크
Tistory

[알고리즘] 그리디(Greedy), 탐욕 알고리즘 | 거스름돈 문제

그리디(Greedy) 알고리즘이란? 그리디 알고리즘은 "매 선택에서 그 순간 당장 최적인 답을 선택" 하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그리디 알고리즘은 최적 부분 구조(optimal substructure)를 가진 문제를 해결하는데 강점이 있다. 최적 부분구조란 매 순간의 최적해의 합이 문제에 대한 최적해여야 한다는 의미이다. 예를 들어 누군가 A도시에서 B도시를 거쳐 C도시로 간다고 하자. A도시에서 B도시를 갈 때 가장 짧은 거리인 150km 경로를 선택하고, B도시에서 C도시로 갈 때 가장 짧은 거리인 140km 경로를 선택하면, 전체적으로도 최적의 경로가 된다. 매 순간 최적 경로의 합이 전체 경로의 최적 경로가 되었다. 이러한 최적 부분 구조를 가진 문제는 그리디 알고리즘으..

원문보기 내부링크
Tistory

[자료구조]Max Heap, Min Heap, Heap 이란? | C언어 Heap 구현

힙(Heap)이란? 완전이진트리의 일종이다. 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 힙은 중복된 값을 허용한다. Max Heap 은 가장 큰 값을 빠르게 찾기 위한 것이고 Min Heap 가장 작은 값을 빠르게 찾기 위한 것이다. 완전이진트리가 무엇인지 모르겠다면 다음을 참고하자. [자료구조] 트리(Tree)의 개념, 이해, 종류 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 code-lab1.tistory.com Max Heap(최대 힙) Max Heap 은 부모 노드의 ..

원문보기 내부링크
Tistory

[알고리즘] 동적계획법(Dynamic Programming, DP)이란? 다이나믹 프로그래밍 이란? 피보나치 수열

피보나치 수열 피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... 이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다. 1 2 3 4 5 6 int fibo(int n){ if (n

원문보기 내부링크
Tistory

[자료구조] 트리(Tree)의 개념 | 이진 트리, 전 이진 트리, 완전 이진트리, 포화 이진 트리, 이진 탐색트리

트리(Tree)의 개념 트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 트리는 다음과 같은 특징들을 갖는다. 1. 트리는 하나의 루트 노드를 갖는다. 2. 루트 노드는 0개 이상의 자식 노드를 갖는다. 3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다. 4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다. 트리에는 사이클(cycle)이 존재할 수 없다. 여기서 사이클이란 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다. 트리의 노드는 s..

원문보기 내부링크
Tistory

[자료구조] 배열(Array) 연결리스트(Linked List) 비교

배열과 연결리스트는 순차적으로 데이터를 저장한다는 점에서 비슷하다. 두 자료구조에 대해서 알아보자. 배열(Array) 배열은 논리적 저장순서와 물리적 저장순서가 일치하는 자료구조이다. 즉 인덱스(index)로 해당 원소에 접근 할 수 있다. 따라서 원소의 인덱스값을 이용하면 O(1)에 해당 원소에 접근 할 수 있다. 그러나 삭제 또는 삽입의 과정에서 추가적인 시간이 소요될 수 있다. 예를 들어 아래와 같은 상황에서 배열의 첫번째 자리(Arr[0])에 새로운 원소를 추가한다고 하자. 위와 같은 상황에서 Arr[0] 에 데이터 10을 추가하기 위해서는, Arr[0] 부터 Arr[4] 까지 모든 원소가 한 칸 씩 오른쪽으로 이동하게 된다. 즉, 원소를 삽입할 때 최악의 경우 모든 원소들을 1씩 옮기는 작업이 ..

원문보기 내부링크
Tistory

[자료구조] 스택(stack) 의 개념과 이해 | c언어 스택 구현

스택(Stack) 이란? 스택 자료구조는 마치 접시가 쌓이는 것과 비슷하다. 당신이 접시를 쌓는다면 아래부터 위로 차근차근히 접시를 쌓게 될 것이다. 이 때 가장 위에 있는 접시를 가장 먼저 꺼낼 수 있을 것이고 가장 아래에 있는 접시는 가장 나중에 꺼낼 수 있을 것이다. 스택도 이와 동일하다. Last In First Out(LIFO) 구조로 가장 나중에 들어간 원소가 가장 먼저 나오게 된다. 스택의 연산은 Push, Pop 으로 단순하다. Push 연산시 가장 위에 원소를 추가하게 되고, Pop 연산시 가장 위의 원소를 반환한다. C언어 구현 스택을 구현 할 때는 배열로 구현할 수도 있고, 연결리스트(Linked List)를 이용해 구현할 수도 있다. 여기서는 배열을 이용해 간단히 구현해본다. 1. ..

원문보기 내부링크
Tistory

[자료구조] 큐(Queue)란? | c언어 큐 구현

큐(Queue) 란? 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 스택은 아래 부분이 막히고 윗 부분이 뚫린 통과 같았다면, 큐는 양 쪽이 뚫린 통과 같다. 스택이 가장 윗부분에서 데이터를 넣고 꺼냈다면, 큐는 front 에서 Dequeue(데이터를 꺼냄) 연산이 진행되고, rear 부분에서 Enqueue(데이터를 넣음) 연산이 진행된다. c언어 구현 큐는 배열 혹은 연결리스트로 구현할 수 있다. 배열로 구현할 시에는 여러가지 문제점이 발생할 수 있다. 여기서는 연결리스트를 이용해 큐를 구현해보도록 한다. 1. 노드 정의, ..

원문보기 내부링크
Tistory

[자료구조] 연결리스트(Linked List)의 개념, 이해 | 단순연결리스트(Singly linked list) C언어 구현, 소스코드

연결리스트(Linked List)란? -연결리스트(Linked List)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조이다. - 각 노드는 다음 노드를 가리키는 포인터를 포함한다. - 다음 노드를 가리키는 포인터는 다음 노드의 주소를 값으로 가지고 있다. - 각 노드의 포인터 변수는 다음 노드의 데이터의 주소를 값으로 가진다. 또한 각 포인터 변수의 주소도 따로 존재한다. (그림에 나타난 주소는 정확하지 않다. 이해를 돕기 위해 임의로 설정했다. 실제 주소값은 저런식으로 저장되지 않는다) 단순연결리스트(Singly Linked List)의 구현 가장 간단한 연결리스트인 단순 연결리스트를 구현해보자. 여러 구현 방법이 있지만, 아래 내용들을 응용하면 다양한..

원문보기 내부링크
Tistory

[알고리즘] Divide and Conquer(분할정복)이란? | Merge Sort(병합정렬)

정의 Divide and Conquer(분할정복)은 해결하기 힘든 큰 문제를 작은 문제로 분할하여 해결(정복)한 후 병합하는 알고리즘이다. 접근법 분할정복은 보통 다음과 같은 3단계의 과정을 거친다. 1. Divide(분할) : 문제를 더 작은 문제들로 분할 2. Conquer(정복) : 분할한 작은 문제들을 해결한다. 3. Combine(병합) : 작은 문제들의 해결법을 병합해 큰 문제의 해결법을 찾는다. 특징 1. 문제를 나눌 때 보통 재귀(recursion)를 많이 사용한다. 2. 재귀(recursion)를 이용할 때 오버헤드가 커 메모리를 많이 사용할 수 있다. 예시 Merge Sort(병합 정렬) 병합 정렬은 분할정복의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병..

원문보기 내부링크
Tistory

[백준] 9507번 Generations of Tribbles (자바 풀이)

문제 https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한..

원문보기 내부링크
Tistory

[백준] 16987번 계란으로 계란치기 (자바 풀이)

문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머..

원문보기 내부링크
Tistory

[백준] 21939번 문제 추천 시스템 version1 (자바 풀이)

문제 https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는..

원문보기 내부링크
Tistory

[백준] 2266번 금고 테스트 (자바 풀이)

문제 https://www.acmicpc.net/problem/2266 2266번: 금고 테스트 N층 빌딩이 있다. 이 빌딩의 F층은 금고를 떨어뜨렸을 때에 부서지는 최소 층이다. 다시 말하면, F층을 포함하여 그 위의 층에서 금고를 떨어뜨리..

원문보기 내부링크
Tistory

[백준] 4358번 생태학 (자바풀이)

문제 https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의..

원문보기 내부링크
Tistory

[백준] 3980번 선발 명단 (자바 풀이)

문제 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라..

원문보기 내부링크
Tistory

[백준] 1990번 소수인팰린드롬 (자바 풀이)

문제 https://www.acmicpc.net/problem/1990 풀이 쉬운 문제인데 어이없게 틀렸습니다를 반복해서 받았다. 우선 이 문제의 풀이는 다음과 같다. 1. 에라토스테네스의 체로 소수를 판별해놓는다. 2. 팰린드롬 판별..

원문보기 내부링크
Tistory

[백준] 15724번 주지수 (자바 풀이)

문제 풀이 이 문제는 간단한 누적합 문제이다. 만약 매번 합을 계산하면 시간초과가 발생할 것이다. 따라서 미리 가로줄을 누적합으로 계산해놓고, 좌표에 따라 누적합을 이용해서 출력하면 된다. 자세한 내용은..

원문보기 내부링크
Tistory

[백준] 16928번 뱀과 사다리 게임 (자바 풀이)

문제 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보..

원문보기 내부링크
Tistory

[백준] 9205번 맥주 마시면서 걸어가기 (자바 풀이)

문제 https://www.acmicpc.net/status?user_id=jo1997&problem_id=9205&from_mine=1 채점 현황 www.acmicpc.net 풀이 간단한 BFS 문제이다. 편의점들의 좌표를 ArrayList에 저장해놓고, BFS를 통해 모든 편의점들..

원문보기 내부링크
Tistory

[백준] 15900번 나무 탈출 (자바 풀이)

문제 https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을..

원문보기 내부링크
Tistory

[백준] 1012번 유기농 배추 (자바 풀이)

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는..

원문보기 내부링크
Tistory

[백준] 1202번 보석 도둑 (자바 풀이)

1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 C..

원문보기 내부링크
Tistory

[백준] 16943번 숫자 재배치 (자바 풀이)

문제 https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C..

원문보기 내부링크
Tistory

[백준] 22862번 가장 긴 짝수 연속한 부분 수열 (자바 풀이)

문제 https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력..

원문보기 내부링크
Tistory

[백준] 2015번 수들의 합4 (자바 풀이)

문제 https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는..

원문보기 내부링크
Tistory

[백준] 1717번 집합의 표현 (자바 풀이)

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산..

원문보기 내부링크
Tistory

[백준] 1504번 특정한 최단 거리 (자바 풀이)

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a..

원문보기 내부링크
Tistory

[백준] 17276번 배열 돌리기 (자바 풀이)

문제 https://www.acmicpc.net/problem/17276 17276번: 배열 돌리기 각 테스트 케이스에 대해 회전 연산을 마친 후 배열의 상태를 출력한다. n줄에 걸쳐 각 줄에 n개의 정수를 공백으로 구분하여 출력한다. www.ac..

원문보기 내부링크
Tistory

[백준] 1654번 랜선 자르기 (자바 풀이)

문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상..

원문보기 내부링크
Tistory

[백준] 20924번 트리의 기둥과 가지 (자바 풀이)

문제 https://www.acmicpc.net/problem/20924 20924번: 트리의 기둥과 가지 첫 번째 줄에는 노드의 개수 $N$($1 \le N \le 200\,000$)과 루트 노드의 번호 $R$($1 \le R \le N$)이 주어진다. 이후 $N-1$개의 줄에..

원문보기 내부링크
Tistory

[백준] 12852번 1로 만들기2 (자바 풀이)

문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 풀이 이 문제는 전형적인 DP 문제이다. bottom-up..

원문보기 내부링크
Tistory

[백준] 20365번 블로그2

문제 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경..

원문보기 내부링크
Tistory

[백준] 19583번 싸이버개강총회 (자바 풀이)

문제 https://www.acmicpc.net/problem/19583 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤..

원문보기 내부링크
Tistory

[백준] 2573번 빙산 (자바 풀이)

문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그..

원문보기 내부링크
Tistory

[백준] 21942번 부품 대여장 (자바 풀이)

문제 https://www.acmicpc.net/problem/21942 21942번: 부품 대여장 첫 번째 줄에 부품 대여장에 작성된 정보의 개수 $N$, 대여기간 $L$, 벌금 $F$이 공백으로 구분되어 주어진다. 대여기간 형식은 DDD/hh:mm으로..

원문보기 내부링크
Tistory

[백준] 2638번 치즈 (자바 풀이)

문제 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는..

원문보기 내부링크
Tistory

[백준] 11399번 ATM (자바 풀이)

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acm..

원문보기 내부링크
Tistory

노션(Notion)을 이용한 개발자 이력서/포트폴리오 만들기

노션으로 개발자 이력서/포트폴리오 만들기 다른 사람들이 노션을 이용해 멋있는 이력서/포트폴리오를 만드는 것을 보고 나도 노션을 이용해 깔끔한 이력서/포트폴리오를 만들고 싶어졌다. ( 적을 건 별로 없지만...

원문보기 내부링크
Tistory

[백준] 2667번 단지번호붙이기 (자바 풀이)

문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여" data-og-host="ww..

원문보기 내부링크
Tistory

[백준] 11501번 주식 (자바 풀이)

문제 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가..

원문보기 내부링크
1 2 3 4