본문 바로가기

분류 전체보기75

다이나믹 프로그래밍 ( Dynamic Programming ) 다이나믹 프로그래밍 문제는 종류가 굉장히 많으며 컴퓨터적인 사고력을 물어보기에 적합하다는 점에서 자주출제되는 문제이다. 다이나믹 프로그래밍하나의 문제는 단 한 번만 풀도록 하는 알고리즘=> 한 번 푼 것을 여러 번 다시 푸는 비효율적인 알고리즘을 개선시키는 방법dp같은 경우 문제에서 규칙성을 찾아서 점화식을 세우는 게 가장 중요하다. 다이나믹 프로그래밍을 쓰는 이유일반적으로 상당수의 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있다.( 단, 퀵 정렬이나 병합 정렬은 동일한 문제를 다시 푸는 단점이 없다. 그러므로 매우 빠르다. ) 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시   ' 피보나치 수열 '   피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 .. 2022. 2. 21.
깊이 우선 탐색 ( DFS ) 깊이 우선 탐색 ( DFS )탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 알고리즘미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해 느리다. 깊이 우선 탐색 특징넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것스택(Stack)을 사용- 사실 스택을 사용하지 않아도 구현이 가능하다. 왜냐하면 컴퓨터는 구조적으로 항상 스택의 원리를  사용하기 때문이다.자기 자신을 호출하는 재귀 알고리즘의 형태이다.탐색 과정이 시작 노드에서 한없이 깊게.. 2022. 2. 20.
운영체제 프로세스와 스레드의 차이프로세스(Process)실행 중인 프로그램. 즉 디스크로부터 메모리에 적재되어 CPU의 할당을 받을 수 있는 것을 말한다.운영체제로부터 주소 공간, 파일, 메모리 등을 할당받으며 이것들을 총칭하여 프로세스라고 한다.프로세스 제어 블록 (Process Control Blcok, PCB)  PCB는 특정 프로세스에 대한 중요한 정보를 저장하고 있는 운영체제의 자료구조이다. 운영체제는 프로세스를 관리하  기 위해 프로세스의 생성과 동시에 고유한 PCB를 생성한다. 프로세스는 CPU를 할당받아 작업을 처리하다가도 프로세스 전환이 발생하면 진행하던 작업을 저장하고 CPU를 반환해야 하는데, 이때 작업의 진행 상황을 모두 PCB에 저장하게 된다. 그리고 다시 CPU를 할당받게 되면 PCB에 .. 2022. 2. 20.
웹 개발을 하기 위해 구현 전 알아야 할 기초 지식 좋은 코드란?읽기 쉬운 코드중복이 없는 코드테스트가 용이한 코드Object Oriented Programming ( 객체지향 프로그래밍 )객체 지향 프로그래밍 이전의 프로그래밍 패러다임을 살펴보면, 중심이 컴퓨터에 있었다. 컴퓨터가 사고하는대로 프로그래밍을 하는 것이다. 하지만 객체지향 프로그래밍은 인간 중심적 프로그래밍 패러다임이라고 할 수 있다. 즉, 현실 세계를 프로그래밍으로 옮겨와 프로그래밍하는 것을 말한다. 현실 세계의 사물들을 객체라고 보고 그 객체로부터 개발하고자 하는 애플리케이션에 필요한 특징들을 뽑아와 프로그래밍 하는 것이다. 이것을 추상화라고 한다. OOP로 코드를 작성하면 이미 작성한 코드에 대한 재사용성이 높다. 자주 사용되는 로직을 라이브러리로 만들어두면 계속해서 사용할 수 있으며.. 2022. 2. 19.
TCP, IP, Ethernet 헤더 Ethernet 컴퓨터 네트워크 기술의 하나로, 물리 계층와 데이터 링크 계층으로 나뉜다. 물리 계층 => 신호와 배선 정의 데이터링크 계층 => MAC 패킷과 프로토콜의 형식 정의 Ethernet 헤더 구조 Destination MAC( 6 bytes ) Source MAC ( 6 bytes ) Type ( 2 bytes ) 목적지 주소 출발지 주소 상위 계층 Protocol 종류 구분 ( IP : 0x0800, ARP : 0x0806 등 ) IP ( Internet Protocol ) 컴퓨터가 갖게 되는 주소 Wifi가 달라질 때마다 얻는 주소가 달라진다. 비신뢰성, 비연결성 통신이다. 비신뢰성 => 흐름에 관여하지 않기 때문에 보낸 정보가 제대로 갔는지 보장 X ex) 전송 과정에서 패킷이 손상되거.. 2022. 2. 18.
너비 우선 탐색 ( BFS ) 너비 우선 탐색 ( Breath First Search )데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘현재 노드에서 가까운 것을 먼저 탐색하는 방식깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것 너비 우선 탐색 특징재귀적으로 동작 XFIFO 원칙으로 탐색 ( Queue가 필요함 )그래프 탐색 알고리즘은 방문한 노드를 꼭 방문 처리 해줘야 한다. ( 하지 않을 경우 무한 루프에 빠질 수 있음 )너비 우선 탐색 장점과 단점출발노드에서 목표노드까지의 최단 길이 경로 보장경로가 매우 길 경우 탐색 가지가 급격히 증가함에 따라 보다 많은 저장 공간이 필요함해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색한 후 실패로 끝남무한 그래프의 경우 해가 없는 경우 해를 찾지.. 2022. 2. 15.

티스토리툴바