공부하자

• [C++] 문자열 분리하기(split) C++에서는 문자열을 분리하는 함수가 따로 없어서 직접 구현해야 한다. 코드는 아래와 같다. #include #include using namespace std; int main() { string str = "Hello World!"; //구분할 문자열 istringstream ss(str); //istringstream에 저장 string buffer; //분리된 문자열을 담는 변수 while (getline(ss, buffer, ' ')) { //' '을 기준으로 분리 후 출력 cout 2023.10.14
• [C++] 백준 1520: 내리막길 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해결방법 dfs와 dp를 사용해서 풀 수 있는 문제이다. dp[x][y]에 저장되는 값은 (x, y)에서 (n-1, m-1)까지 가는 방법의 개수이다. 제일 왼쪽 위 (0,0)에서 현재 위치의 값보다 작은 방향으로 이동하면서 d[x][y] += dfs(nx,ny) 식을 통해 dfs를 돌려 다음 위치의 dp값을 받아오면 된다. 코드 #include using namespace std; int n, .. 2023.10.08
• [C++] 백준 19637: IF문 좀 대신 써줘 문제 https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 해결방법 특정 값이 아닌 범위를 찾는 것임을 기억하고 있어야 한다. 출력할 수 있는 칭호가 여러 개일 경우 가장 먼저 입력된 칭호 출력해야 하므로 입력받은 값 X가 mid번째 칭호의 전투력보다 작거나 같으면(x < v[mid].second) right=mid-1을 해준다. 이 외에는 left=mid+1을 해준다. 위에서 X와 칭호의 전투가 같았을 때.. 2023.10.06
• [알고리즘] 백트레킹 백트래킹이란? 해를 얻을 때까지 모든 경우의 수를 시도하는 알고리즘이다. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 이전으로 돌아가서 다른 규칙을 선택하여 다시 시도한다. 보통 DFS를 사용해서 탐색하면서 조건을 통해 필요 없는 부분을 쳐낸다. 백트래킹 예시 N-Queen 문제가 가장 대표적인데, 예시로 너무 많이 나와서 다른 문제를 준비해봤다. N과 M (1) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 해결방법 해당 숫자를 골랐는지의 유무를 저장하는 visited 배열을 사용하여 1부터 고르지 않은 숫자를 찾아 arr 배열에 저장한.. 2023.10.05
• [C++] 백준 1238: 파티 문제 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 해결방법 다익스트라 알고리즘으로 풀 수 있다. 1부터 N까지 각 노드를 출발지로 하는 최단거리를 구한 후, X를 목적지로 하는 최단 거리를 배열에 저장한다. X를 출발지로 하고 1부터 N까지의 최단 거리를 구한 후, 1에서 구한 배열에 더해준다. 배열에 각 인덱스에 저장된 값은 노드 -> X + X -> 노드 값이다. 따라서 가장 큰 값을 출력해주면 된다. 코드.. 2023.10.04
• [알고리즘] 다익스트라 다익스트라 알고리즘이란? 다익스트라는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 최단 경로 구하는 과정 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B](가중치)와 d[B]의 값을 비교한다. d[A] + P[A][B] < d[B] 라면, d[B] = d[A] + P[A][B]로 갱신시킨다. A의 모든 이웃 노드 B에 대해 이 작업을 수행한다. A의 방문 상태를 TRUE로 바꾼다. 방문하지 않은 모든 노드들 중, 출발점으로부터의 거리가 제일 짧은 노드를 다시 A로 지정한다. 도착 노드의 방문 상태가 TRUE.. 2023.10.02
• [알고리즘] 이분 탐색 이분 탐색 알고리즘이란? 정렬되어 있는 리스트에서 탐색 범위를 절반씩 줄여가며 원하는 데이터를 탐색하는 알고리즘이다. 정렬된 리스트에서 중간 값을 선택하고 선택한 값과 찾고자 하는 값의 크고 작음을 비교한다. 선택한 중간값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 꼭 정렬해야함을 잊지 말자! 이분 탐색 알고리즘 구현 - C++ 이분 탐색은 O(log N) 의 시간복잡도를 가진다. #include using namespace std; int main(){ int arr[10]={1,2,3,4,5,6,7,8,9}; int target=6; int low=0, high=9;//시작 인덱스, 끝 인덱스 int res=0; //이분탐색 부분 while(low.. 2023.10.01
• [C++] 백준 25828: Corona Virus Testing 문제 https://www.acmicpc.net/problem/25828 25828번: Corona Virus Testing Testing for Corona can be done individually, e.g., 100 people require 100 test kits. Alternatively, the test can be done in groups (pools), e.g., 100 people can be divided into five group of 20 people each and then using only one test kid per group. If one www.acmicpc.net 해결방법 그룹별 검사하는 데 사용되는 키트 수는 그룹 수 + 그룹별 인원수 * 양성인 그룹 수이고 .. 2023.05.22
• [C++] 백준 25881: Electric Bill 문제 https://www.acmicpc.net/problem/25881 25881번: Electric Bill The first input line contains two integers (each between 2 and 20, inclusive), indicating the rate/KWH for the first 1000 KWH and the rate/KWH for the additional usage, respectively. The next input line contains a positive integer, n, indicating the number www.acmicpc.net 해결방법 입력받은 고객의 에너지 소비량에서 1000은 기본 요율, 1000을 뺀 나머지는 추가 요율을 적용하여 .. 2023.05.21