전체 글

(C++) 백준 11724번 - 연결 요소의 개수

문제 링크 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 풀이 방향이 없는 그래프를 BFS 하여 풀이하였다. BFS를 사용하여 하나의 정점부터 차례대로 순회하면 이것들은 하나의 연결 요소가 된다. 그렇기에 출발점을 정점 하나하나로 두고, 방문했는지 여부를 사용하면 연결 요소의 수까지 파악할 수 있다. #include #include using namespace std; vect..

(C++) 백준 1715번 - 카드 정렬하기

문제 링크 : https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 우선순위 큐와 그리디 알고리즘을 사용하여 풀이하였다. 카드 비교 횟수를 최소화하려면 가장 개수가 적은 두 묶음씩 먼저 합치면서 진행하면 된다. 최소 힙을 사용해서 가장 갯수가 적은 묶음 두 개를 합친 후, 다시 이를 최소 힙에 넣고 앞의 과정을 반복하는 방식으로 풀이하였다. #include #include using namespace std; int n, tota..

(C++) 백준 11286번 - 절대값 힙

문제 링크 : https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 우선순위 큐와 커스텀 비교 함수를 사용하여 풀이하였다. 우선순위 큐에서는 가장 뒤에 위치한 값이 가장 우선순위가 높다는 것이 풀이하면서 상당히 헷갈리게 만들었다. 또한 우선순위 큐에서 비교 함수를 사용하기 위해서 아래와 같이 cmp라는 클래스와 내부의 operator()를 사용해야 한다는 사실도 새롭게 알게 되었다. #include #include usin..

(CS) HTTP Request/Response/Method, CORS, 서브넷

HTTP Request/Response 메시지 구조 HTTP 메시지는 웹에서 데이터를 전송하기 위해 사용되는 프로토콜인 HTTP(HyperText Transfer Protocol)에서 사용되는 메시지 구조이다. HTTP 메시지는 데이터 통신을 위해 사용되며 Request와 Response 두 가지 형태로 나뉩니다. 1. HTTP Request(요청) Start Line: 요청 메서드, URL 경로, 프로토콜 버전 등의 정보를 포함한다. 예: GET /index.html HTTP/1.1 Header Fields: 추가적인 메타데이터를 포함하는 헤더 필드들이 위치한다. General 헤더: Via(메시지 전달을 추적하고 요청 루프를 방지하며 요청/응답 체인에서 발신자의 프로토콜 기능을 식별하는 데 사용)와 ..

(C++) 백준 1620번 - 나는야 포켓몬 마스터 이다솜

문제 링크 : https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 문제 풀이 해시(unordered_map)를 사용하여 풀이하였다. 포켓몬 이름(string)을 key로 하고, 도감번호(int)를 value로 하는 unordered_map을 생성 후, 입력받는 대로 저장을 한다. 동시에 도감번호를 index로 하는 배열에도 포켓몬 이름을 저장한다. 다음으로 질문이 들어오는데 만약 이것이 int라면 당연히 앞 글자가 di..

(C++) 백준 7785번 - 회사에 있는 사람

문제 링크 : https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 풀이 해시를 이용한 풀이이다. unordered_set이라는 다소 생소한 STL을 사용하였다. 정렬은 cmp라는 cutom 비교 함수를 만들어서 사전순의 역순으로 정렬하였다. #include #include #include #include using namespace std; int n; string person, act; unordere..

(C++) 백준 1806번 - 부분합

문제 링크 : https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 풀이 투 포인터를 이용하여 풀이하면 된다. 여기서는 st와 en 두 개의 포인터를 사용한다. 1. 배열 A를 입력받는다. 2. en을 1씩 증가시키면서 total의 값이 S 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다. 만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break 한다. 3. st를 1만큼 증가시키고,..

(C++) 백준 2230번 - 수 고르기

문제 링크 : https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 문제 풀이 투 포인터를 사용하여 풀이할 수 있다. 여기서는 st와 en 두 개의 포인터를 사용한다. 1. 배열 A를 입력받은 후, 정렬을 한다. 2. en을 1씩 증가시키면서 A[en] - A[st]의 값이 M 이상일 경우, 그때 그 값이 최솟값인지 체크를 한다. 만약 en이 N이 되면 배열 끝까지 다 순회한 것이므로 더 이상 체크할 것이 없기 때문에 break ..

(CS) HTTP, HTTPS, TCP

HTTP 버전별 구분 1. HTTP 0.9 1991년에 처음 도입된 버전으로, 일반 문서만 검색하는 간단한 프로토콜이었다. 초기에는 버전 정보가 없었으나, 이후에 차후 버전과 구별하기 위해 HTTP 0.9라는 이름을 붙이게 되었다. 요청과 응답은 매우 간소했으며, 리소스에 대한 메서드로는 GET이 유일하다. HTTP 헤더가 없었는데 이는 HTML 파일만 전송될 수 있으며 다른 유형의 문서는 전송될 수 없음을 의미한다. 상태 혹은 오류 코드도 없어서 문제가 발생한 경우, 특정 HTML 파일이 사람이 처리할 수 있도록, 해당 파일 내부에 문제에 대한 설명과 함께 되돌려 보내졌다. 요청과 응답 예시 요청 GET /mypage.html 응답 A very simple HTML page 2. HTTP 1.0 199..

(C++) 백준 1541번 - 잃어버린 괄호

문제 링크 : https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 풀이 그리디 알고리즘을 사용한 풀이이다. '-' 이후로 오는 수는 모두 빼기 처리해 주면 최솟값을 구할 수 있다. #include #include using namespace std; string raw, num; int result; int main() { cin >> raw; bool isMinus = false; for(int i = 0; i