일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- BHS
- 프로그래머스
- ps
- Application Layer
- baekjoon
- swea
- 전송 계층
- 관계형 모델
- DB
- dp
- leetcode
- Transport layer
- Database
- C++
- 임베디드
- 백준
- 부트시퀀스
- BST
- 네트워크
- Djikstra
- STL
- Network
- 문제풀이
- 릿코드
- 데이터베이스
- boot sequence
- Embedded
- 다익스트라
- 응용 계층
- 자료구조
- Today
- Total
목록Algorithm/Problem Solving (26)
BOBO's Note
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 풀이 방법 N개의 집 중 C개의 집에 공유기를 설치하는 모든 경우의 수는 이다. 각 경우의 수에 대하여 최소 인접 거리를 구하는 것은 O(C)의 시간이 걸리기 때문에 전체 시간복잡도는 이다. Brute force 방식으로 모든 경우의 수에 대하여 계산하면 시간 초과가 발생한다. 따라서 이진 탐색을 활용해 인접한 공유기 사이의 최소 거리를 찾아..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 각 사람으로부터 모든 BC(=Battery Charger)까지의 거리를 계산하여 선택할 수 있는 BC를 available_bc 벡터에 추가한다. for (int i = 0; i < 2; i++) { for (int j = 0; j < num_bc; j++) { d = abs(people[i].r - bc[j].r) + abs(people[i].c - bc[j].c); if (d
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRUN9KfZ8DFAUo&categoryId=AWXRUN9KfZ8DFAUo&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 길이가 n인 16진수 수열이 주어졌을 때, 앞에서부터 n/4개의 숫자가 비밀번호 후보가 된다. 이를 n번 한칸씩 shift하여 총 4*n개의 비밀번호 후보를 얻을 수 있다. 이때, 한칸씩 shift하는 것을 수열을 두개 이어붙여 손쉽게 구현할 수 있다. for (int i = 0; i < N; i++) { ..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRQm6qfL0DFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 이 문제 역시 구슬을 쏘는 위치의 순서를 모든 경우를 구하여 계산했다. W*H 게임판에서 N번 구슬을 쏘는 경우의 수는 W^N이다. 이때, W의 최대값은 12, N의 최대값은 4이기 때문에 전체 경우의 수는 12^4가지이다. 구슬을 쏘는 위치의 순서가 정해졌을 때, 게임을 시뮬레이션하는 함수는 play()이다. 각 슈팅에 대하여 shoot_at() 함수로 구현했다. int play() {..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 방법 n명의 사람이 2개의 계단 중 하나를 선택하여 내려갈 수 있다. 계단을 선택하는 전체 경우의 수는 2^n인데, n이 최대 10이기 때문에 모든 경우에 대하여 소요 시간을 구하였다. 각 사람들이 계단을 선택하는 조합을 구하고, 구한 조합에 대하여 calc_time() 함수를 통해 소요 시간을 구한다. 그리고 그 중 최소 소요시간을 result에 업데이트해나간다. void min_time(i..
https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net 풀이 방법 게임판을 저장하기 위해서 위와 같이 5개의 경로를 나누어 각 배열에 저장했다. 각 칸에 적혀진 값을 순서대로 저장한다. struct board { int route[21] = { -1, }; // on_route = 0 int route10[4] = { 10, 13, 16, 19 }; // on_route = 1 int route20[3] = { 20, 22, 24 }; // on_route = 2 int route30[4] = { 30, 28, 27, 26 }; // on_route = 3 int route25..
https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 풀이 방법 A op B 구조(A, B: operand, op: operator)에서 해당 연산을 괄호로 묶는 경우, 안 묶는 경우를 DFS로 완전 탐색한다. new_expr에 표현식을 완성해나가는데, 괄호를 묶는 경우는 연산을 해준 값을 바로 저장해준다. 이때, 연산을 해준 값이 10 이상일 수 있기 때문에 new_expr을 char형 배열이 아닌 int형 배열로 선언했다. for..
https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 풀이 방법 물고기를 먹으려할 때마다 BFS를 이용해서 어떤 물고기를 먹을지 결정한다. 더 이상 먹을 수 있는 물고기가 없으면 종료한다. BFS를 사용하여 탐색할 때 큐에 행, 열, 아기 상어로부터의 거리를 추가한다. queue q; 아기 상어로부터 거리가 동일한 물고기가 여러 개 존재하면 더 작은 행에 위치하고, 동일한 행에 존재하면 더 작은 열에 존재하는 물고기를 선택..