문제 문제 바로가기> BOJ 17615번: 볼 모으기 17615번: 볼 모으기 첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주 www.acmicpc.net 풀이 크게는 총 2가지 경우가 있고, 그 안에서 또 2가지로 나뉘어 총 다음과 같은 4가지 경우가 있다. 1. 빨간 볼을 움직이는 경우 왼쪽으로 움직이는 경우 오른쪽으로 움직이는 경우 2. 파란 볼을 움직이는 경우 왼쪽으로 움직이는 경우 오른쪽으로 움직이는 경우 위 4가지 경우에서 최솟값을 찾아주면 되는 간단한 문제였다 ㅎㅎ 처음에 너무 복잡하게 생각하려고 하다보니 오히려 어렵게 느..

문제 문제 바로가기> BOJ 17822번: 원판 돌리기 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 풀이 원판을 2차원 배열로 입력받아서 시뮬레이션을 진행하는 문제였다. 처음에 시간을 절약하기 위해 M/2 < k 인 경우 반대 방향으로 M-k만큼 돌려주었고, sum, cnt 변수를 전역 변수로 가지고 있는 방식을 이용했다. 하지만, 이러한 부분을 빼고 그때그때 sum과 cnt를 가져오는 함수를 만들도록 코드를 변경하면, 코드가 더 깔끔해질 것 같았고, 시간 초과가 발생할 시간 복잡도도 아니어..

문제 문제 바로가기> BOJ 17825번: 주사위 윷놀이 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 풀이 각 칸에서 이동해야하는 다음칸, 점수를 저장해 두어야 하는데, 이 때 약간의 노가다 작업?이 필요하다. 그 외에는 단순 백트래킹 문제이다 ! 💡 문제 해결 Point 처음에 파란지점 때문에 2차원 배열([이동칸][현위치] = 다음위치)을 만들어서 바로 이동하게 하려고 했는데, 이렇게 하는 경우, 너무 많은 노가다 작업이 필요했다,, 개인적으로, blueP 지점을 별도 배열로 가지고 있는 부분이 중요한 ..

문제 문제 바로가기> BOJ 21611번: 마법사 상어와 블리자드 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 풀이 문제에서 요구하는 각 스텝의 구현이 모두 비슷해서 구현이 어렵지는 않은 문제였다. 다만... 모든 반례가 통과하는데, 왜 자꾸 75%에서 틀리지,, 라고 생각했는데... 바로 `if(x==0) break; ` 부분을 넣어주지 않았기 때문 ... x=0 이 되는 시점에서는 어떠한 처리도 할 필요없고, 해서도 안된다,,,!!!!!! 🥲 이 처리를 해주지 않으면, change_ma..

Transport Layer (전송 계층) host안에 존재하는 많은 프로세스 중 목적지 프로세스로 전달하는 역할을 담당 전송 단위 : 세그먼트 (segment) - TCP / 데이터그램(datagram) - UDP 주소 : Port 번호 💡 Application Layer에서 Transport Layer에 바라는 서비스 Application Layer에 서비스 제공 (in TCP/IP 4 계층) 1. data integrity (data 유실 없이 전달) → TCP 제공 2. throughput ex) 최소 x bps이상 보장 → 제공 x 3. timing ex) 내가 보낸 메세지는 x ms 안에 도착하면 좋겠다 → 제공 x 4. security (보안) → 제공 x TCP, UDP Transport ..

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..