Application Layer ( 응용 계층 ) 최종 목적지로, 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행 ex ) web, email 등 전송 단위 : 메세지 (message) HTTP (Hypertext Transfer Protocol) : 웹 상에서 클라이언트는 HTTP프로토콜을 이용하여 웹에 있는 object들을 볼 수 있고 필요한 동작들을 요청할 수 있음 Application layer protocol, TCP 이용 (port# 80) "HTTP is stateless" : request가 오면 response하고 끝! (서버는 클라이언트의 예전 정보 기억 X) 💡 HTTP 통신 1) 클라이언트는 서버에 대한 TCP connection(port 80)을 열어 놓음 2) 서버는 ..

문제 문제 바로가기> BOJ 21758번: 꿀 따기 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 풀이 벌 2마리와 벌통의 위치를 모두 다르게 설정해보는 방식으로 문제를 푼다면 시간 초과가 발생한다. 벌이 2마리, 벌통이 1개이므로, 총 3가지의 경우가 있다. 1. 벌 벌 벌통 이 경우, 첫 번째 벌은 가장 왼쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 두 번째 벌의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 2. 벌 벌통 벌 이 경우, 첫 번째 벌은 가장 왼쪽에, 두 번째 벌은 가장 오른쪽에 있는 게 이득이다. 따라서 반복문 O(N)을 통해 벌통의 위치를 지정해주고, 그 시점에서 얻을 수 있는 이익을 계산한다. 3...

문제 문제 바로가기> BOJ16946번: 벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 풀이 매번 벽을 만날 때마다 dfs 혹은 bfs 탐색을 진행하면, 복잡도가 O(N^2*M^2)이고, N과 M 은 최대 1000이므로, 시간초과가 발생한다! 이동 가능한 곳의 영역을 미리 체크해 놓는다면, 시간 복잡도를 O(N^M)으로 줄일 수 있다. 예를 들어 예제 2번의 경우, 4 5 11001 00111 01010 10101 다음과 같이 이동가능한 영역의 size?를 미리 체..

Binary Search 배열에서 원하는 값의 위치를 O(log N) 만에 찾는 방법 ⇔ 순차탐색 O(N) 배열 내 원소가 정렬된 경우에만 사용 가능 정렬되지 않은 배열의 경우, 찾고자 하는 숫자의 개수가 적다면 순차탐색이 빠를 수 있음 아래는 찾고자 하는 값이 없는 경우 -1을, 있는 경우에는 해당 위치를 반환해주는 Binary Search 코드이다. up/down 게임과 유사한 방식으로 원하는 값의 위치를 찾아가는 것을 볼 수 있다. int binary_search(int target){ int low=1, mid, high=n; while(low

문제 문제 바로가기> BOJ 17471번: 게리맨더링 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 풀이 #include #include #define MAX 11 #define INF 100001 using namespace std; int N; int ans = INF; int total = 0; // 총 인구 수 int people[MAX]; // 구역의 인구 수 bool visited[MAX]; // 방문 여부 저장 int isgroup1[MAX]; // 그룹 1에 속하는지 vector v[MAX]; // 각 구역과 인접한..

문제 문제 바로가기> BOJ 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 #include #include #define INF 1000000001 #define MAX_HOME 200001 using namespace std; int N, C; int home[MAX_HOME]; void input() { cin >> N >> C; for (int i = 0; i > home[i]; sort(hom..

문제 문제 바로가기> BOJ 2343번: 기타 레슨 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 매개 변수 탐색을 이용해서 가능한 블루레이의 크기 중 최소를 구하는 문제다. 주의할 점은 상한(high)을 설정하는 부분이다. 처음에 high를 10,001으로 설정했는데 바로 틀렸다,, 생각해보니, 각 강의의 길이가 10,000분을 넘지 않는 것이지, 블루레이의의 크기는 당연히 10,000분을 넘을 수 있기 때문!! 이 부분을 주의해 줘야 할 것 같다! 각 강의당 길이가 10,000분이므로, 10000*1000..

문제 문제 바로가기> SWEA 5644번: 무선 충전 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 input에서 주어진 경로를 따라 이동하면서, 다음과 같은 두 가지 경우로 나누어 문제를 해결해주면 된다. 1. 두 사용자가 동일한 위치에 있는 경우 → 또 다시 3가지 경우로 나뉜다 1) 주변에 충전 가능한 bc가 없는 경우 → continue 2) 1가지 bc를 나눠 사용해야 하는 경우 → 1개의 bc를 각각 나눠 사용한다. 어짜피 ans에 나눠서 더하나, 그 값을 더하나 같다. 3) 2가지 이상의 bc가 있는 경우 → 제일 큰 파워를 가진 두 bc를 이용한다. (나는 prioirty queue를 이용..

문제 문제 바로가기> BOJ 6987번: 월드컵 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 풀이 경기가 진행될 수 있는 모든 경우의 수를 탐색하여, 그 중 하나라도 결과 값과 일치하는 게 있다면 (= 가능한 결과), 1을 출력하도록 풀었다. 모든 경우의 수를 탐색할 경우, 시간 복잡도는 3^15(=14,348,907)(*4 = 57,395,628)로 시간 내 완전탐색이 가능하다! 총 경기 경우의 수는 6C2 = 15 이고, (이 조합을 미리 만들어주는 부분이 make_team() 함수) 두 팀이 경기를 진행..

문제 문제 바로가기> BOJ 16974번: 레벨 햄버거 16974번: 레벨 햄버거 상근날드에서 오랜만에 새로운 햄버거를 출시했다. 바로 레벨-L 버거이다. 레벨-L 버거는 다음과 같이 만든다. 레벨-0 버거는 패티만으로 이루어져 있다. 레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, www.acmicpc.net 풀이 패티가 늘어나는 규칙은 " (이전 레벨 패티) * 2 + 1 " 이다. N 0 1 2 3 4 5 ... patty 1 3 7 15 31 63 ... 햄버거의 아래 X장을 먹는 경우에는 총 3가지 경우가 있다. (재귀적으로, 분할정복으로 해결하기 위해) 1. (해당 레벨의) 가운데 패티보다 적게 먹는 경우 : get_patty(n-1, x-1) = 레벨을 낮추어 재귀적으로 탐색해준다. x-1..

문제 문제 바로가기> BOJ 2531번: 회전초밥 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 풀이 두 포인터를 조작해가며, 푸는 문제다. 회전 초밥이 "회전하는 벨트 위"에 있음을 주의해야 한다. 따라서 종료 조건이 right == k-1, 즉 회전 초밥 벨트를 모두 확인했을 경우다!!!! C++ #include #define DISH 30001 #define KIND 3001 using namespace std; int N, d, k, c; // 회전 초밥 벨트에..

문제 문제 바로가기> BOJ 20056번: 마법사 상어와 파이어볼 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 풀이 주의할점 1. 파이어볼이 나눠진 후, 방향이 변화되어 제자리에 담긴다. 이동 x 2. 인덱스 `-`가 되지 않도록, N*s를 더해 준다. → 어짜피 modulo 하면 사라짐 #include #include #define MAX 51 using namespace std; struct FIREBALL { int m, s, d; }; vector map[MAX..

문제 문제 바로가기> BOJ 11053번: 가장 긴 증가하는 부분 수열 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 DP와 이중 for문을 이용해 "현재 수를 마지막으로 하는 가장 긴 증가하는 부분 수열"의 길이를 저장해주었다. 이렇게 저장해두면, 답은 dp 배열 중 가장 큰 값이 되고, 이를 반복문을 돌 때 함께 업데이트 해주면 된다! #include #define MAX 1001 using namespace std; in..

문제 문제 바로가기> BOJ 2098번: 외판원 순회 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 중요한 Point 1. 출발지가 어디든 그 결과는 같다. A → B → C → A B → C → A → B C → A → B → C 조금만 들여다보면, 순회하기 때문에, 어느 지점에서 출발하든 동일한 경로가 되는 것을 확인할 수 있다. 따라서 출발지를 고정 시킨 후 탐색을 진행한다! 2. 중복되는 경로가 생긴다. 이미 방문해서 최소값을 찾아 놓은 부분 경로의 경우, ..

문제 문제 바로가기> BOJ 12100번: 2048 (Easy) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 블록이 이동하는 순서를 미리 정해 놓은 뒤 시뮬레이션 해보는 문제다. 블록을 합칠 때, vector를 이용하면 좀 더 쉽게 문제를 해결할 수 있다. C++ #include #include #define MAX 21 #define CNT 5 using namespace std; int N, ans=0; int dir[CNT]; vector tmp; int map[MAX..