깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 깊이 우선 탐색은 한 방향으로 계속 가다가 더 이상 갈 수 없으면 부모 노드로 돌아와 다른 방향으로 탐색한다. 주로 Stack이나 재귀 함수를 이용해 구현한다. 모든 노드를 방문하거나 가중치, 이동 과정에 제약이 있을 경우에 사용하면 좋다. 자기 자신을 호출하는 순환 알고리즘의 형태를 갖고 있다. BFS보다 좀 더 간단하나 단순 검색 속도 자체는 BFS보다 느리다. 너비 우선 탐색은 현재 노드에서 가장 가까운 노드를 먼저 방문해 탐색한다. 주로 Queue를 이용해 구현한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾는 경우에 사용하면 좋다. 기본 원리 https://www.acmicpc.n..

동적 계획법(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다.똑같은 연산을 반복하지 않도록 만들어 주고 실행 시간을 줄일 수 있다.작은 문제들을 풀어나가다 보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해 내어 동적 계획법에 적용한다. 풀이법dp[i]가 의미하는 바dp[i]를 initialize 하는 방법dp[i]의 점화식dp[i]를 채우는 순서정답이 의미하는 바 https://jyeonth.tistory.com/7 Leetcode: Word BreakWord Break I Given a non-empty string s and a dictionary wordDict containing a li..

덱(Deque) 큐의 변형판으로 앞, 뒤 양쪽에서 모두 삽입과 삭제가 가능하다. 문제 https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net #include #include #include usi..

큐(Queue) 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료�� www.acmicpc.net #include #include #include #include using namespace std; int main() { int t; cin >> t; while (t--) { int n, m; cin >> n >> m; queue q; vector v(n); for (int i = 0; i > v[i]; if (i == m) q.push(m..

스택(Stack) 문제 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄www.acmicpc.net#include #include #include using namespace std;int main(void){ ..

1. HTTP(HyperText Transfer Protocol) 1) 개념 웹 상에서 클라이언트와 서버 간에 요청/응답으로 자원을 주고받을 때 쓰는 프로토콜이다. 클라이언트인 웹브라우저와 서버는 주로 웹 페이지(HTML)인 텍스트 교환을 하는데, 누군가 네트워크에서 신호를 중간에 가로챈다면 내용이 노출되는 보안 이슈가 존재한다. 평문 통신이기 때문에 도청이 가능하다. 통신 상대를 확인하지 않기 때문에 위장이 가능하다. 완전성을 증명할 수 없기 때문에 변조가 가능하다. 80번 포트를 사용한다. 2) 특징 비연결형(Connectionless): 하나의 세션 안에서 클라이언트와 서버가 Request와 Response을 수행하면 세션이 끊어진다. 무상태성(Stateless): 연결을 끊는 순간 클라이언트와 서..