분류 전체보기104 [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. 8. [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. 6. [알고리즘] 백트레킹 백트래킹이란? 해를 얻을 때까지 모든 경우의 수를 시도하는 알고리즘이다. 규칙을 적용하여 얻은 결과가 틀리면 그 규칙을 적용한 다음부터 현재까지의 결과를 무시하고 이전으로 돌아가서 다른 규칙을 선택하여 다시 시도한다. 보통 DFS를 사용해서 탐색하면서 조건을 통해 필요 없는 부분을 쳐낸다. 백트래킹 예시 N-Queen 문제가 가장 대표적인데, 예시로 너무 많이 나와서 다른 문제를 준비해봤다. N과 M (1) 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 해결방법 해당 숫자를 골랐는지의 유무를 저장하는 visited 배열을 사용하여 1부터 고르지 않은 숫자를 찾아 arr 배열에 저장한.. 2023. 10. 5. [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. 4. [알고리즘] 다익스트라 다익스트라 알고리즘이란? 다익스트라는 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘이다. 최단 경로 구하는 과정 출발점으로부터의 최단거리를 저장할 배열 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. 2. 이전 1 2 3 4 ··· 18 다음
