본문 바로가기

Problem Solving/[C++] Boj

 (59)
[C++] 백준 2178: 미로 탐색 문제 이해- N * M 크기의 배열이 주어진다.- 배열의 값이 1이면 이동 가능하고, 0일경우 불가능하다.- (1,1)에서 출발하여 (N, M)까지 가야한다.- 이 때 지나야하는 최소의 칸 수를 구하라. - 시간 제한: 1초- 메모리 제한: 192MB - N: 행 (2 ~ 100, 10^2)- M: 열 (2 ~ 100, 10^2)- 미로의 맵(공백없이 주어진다) - (1, 1)에서 (N, M)까지 갈 때 지나는 칸의 최솟값을 구하라.※ 단, 입력은 항상 도착 가능하도록 주어진다.  문제 풀이지금 되돌아보면 너무 답답하지만끝까지 빠르게 도달해야 하니까 깊이 우선 탐색을 해야겠다! 그럼 DFS네 라고 생각했다.깊이 우선 탐색이 돌아갈 수 있다는 걸 전혀 생각하지 못했다...  하지만 코드로 구현해 본 결과 ..
[C++] 백준 11403: 경로 찾기 문제 이해- 가중치 없는 방향 그래프 G가 주어진다.- 모든 정점 (i, j)에 대하여 i에서 j로 가는 길이 있는지 없는지 구하라. - 시간 제한: 1초- 메모리 제한: 256MB - N: 정점의 개수 (1 ~ 100, 10^2)- 인접 행렬(1일경우 경로가 존재, 0일경우 경로가 없음) - N개의 줄에 걸쳐 i에서 j로 가는 경로가 있으면 1, 없으면 0을 출력하라.  문제 풀이처음에 생각한 풀이는정점 i -> j로 가는 모든 경우의 수를 DFS로 해보는 풀이였다. 인접 행렬로 주어진 그래프를 벡터 배열을 통해 표현하고 DFS를 사용하였다. 단 i에서 다시 i로 가는 경우도 고려를 해야 했기에처음 시작 정점을 방문 표시하지 않아야한다는 주의할 점이 있었다.  1. i - > j 모든 경우의 수 DFS..
[C++] 백준 1699: 제곱수의 합 문제 이해- 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다.- 그때 합을 구성하는 제곱수들의 개수를 항의 개수라고 한다.- N의 항의 개수가 최소가 되도록하는 개수를 구하라. - 시간 제한: 2초- 메모리 제한: 128MB N: 자연수 (1 ~ 100,000, 10^5) 항의 최소 개수  문제 풀이이전에 푼 문제가 DP가 불가능한 그리디 문제였어서 DP를 전혀 생각하지 못했다.접근 방식에 대해 항상 고민하자.  이 문제는 DP로 풀 수 있는데,'dp[a] = b를 a를 나타낼 수 있는 항의 최소 개수는 b개이다.' 라고 정의했다.  예시를 들면 쉽게 이해할 수 있는데N = 3)3 = 1^2 + 1^2 + 1^2dp[3] = 3이 될것이다. 그러나N = 4)4 = 2^2dp[4] ..
[C++] 백준 6603: 로또 문제 이해- 1 ~ 49 사이의 수 중에서 k개를 골라 집합 S를 만든 후 S의 부분집합의 크기가 6인 집합의 경우의 수를 모두 구하라. - 시간 제한: 1초- 메모리 제한: 128MB - 여러 개의 테스트 케이스- k: 수의 개수 (6 ~ 13)※ 0이 주어지면 종료된다.- k의 원소들 (1 ~ 49) - 수를 고르는 모든 방법을 사전순으로 출력한다.- 각 테스트케이스 사이에는 공백을 출력하라.  문제 풀이k의 원소들이 주어지면 그 중 6개를 고르는 문제이다.백트래킹으로 쉽게 풀 수 있었는데여기서 주의할 점은 사전순으로 출력한다는 것이다. 사전순으로 출력하려면 다음 원소를 선택할 때는 이전 원소보다는 다음 인덱스에 있는 것을 선택해야 한다.이 점을 유의해서 재귀 함수의 매개변수를 깊이뿐만 아니라 인덱스..
[C++] 백준 2004: 조합 0의 개수 문제 이해- nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하라. - 시간 제한: 2초- 메모리 제한: 128MB - 정수 n, m(0 ~ 2,000,000,000, 10^9, n != 0) - 첫째 줄에 nCm의 끝자리 0의 개수  문제 풀이끝자리 0의 개수는 소인수 중 2와 5의 개수로 구할 수 있다!둘 중 작은 것의 개수가 바로 끝자리 0의 개수이다.   nCm = n! / (n-m)! m! 이다.즉, n!의 소인수 개수에서 (n-m)!과 m!의 소인수 개수를 빼주면 nCm의 소인수 개수가 나올 것이다.   그럼 n!의 소인수(k) 개수는 어떻게 구할 수 있을까?일반적인 반복문을 사용하면 수의 크기가 워낙 크기에 시간 초과에 걸릴 수밖에 없다.  정답은 n을 k의 지수들로 나누어주는 것이다.이..
[C++] 백준 1865: 웜홀 문제 이해- N개의 지점- 방향이 없는 M개의 도로- 방향이 존재하는 음의 가중치를 가진 W개의 웜홀- 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 탐색하라. - 시간 제한: 2초- 메모리 제한: 512MB TC: 테스트 케이스의 개수 (1 ~ 5)N: 지점의 수 (1 ~ 500, 10^2)M: 도로의 개수(1 ~ 2,500, 10^3)W: 웜홀의 개수(1 ~ 200, 10^2) - TC개의 줄에 걸쳐서 만약에 시간이 줄어들면서 출발 위치로 돌아오는 것이 가능하면 YES, 불가능하면 NO를 출력하라.   문제 풀이음의 가중치를 가진 최단 경로 탐색이라는 점에서 '벨만-포드 알고리즘' 사용해야 함을 인지했다.문제에서 원하는 것은 시간이 줄어들면서 출발 위치로 돌아올 수 있는지(음의 사이클이 존..
[C++] 백준 10971: 외판원 순회 2 문제 이해- Traveling Salesman Problem (TSP)라고 불리는 문제이다.- 1번부터 N번까지 도시에 번호가 매겨져있다.- 도시들 사이에는 길이 존재하는데, 이는 없을 수도 있다.- 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획중이다.- 단, 한 번 갔던 도시로는 다시 갈 수 없다.※ 맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외이다.- 가장 적은 비용을 들이는 여행 계획의 비용을 출력하라. - 시간 제한: 2초- 메모리 제한: 256MB N: 도시의 수 (2 ~ 10)W[i][j]: i번 도시에서 j번 도시까지 가기 위한 비용 (1 ~ 1,000,000, 10^6)- 비용은 비대칭적이다.- W[i][i]는 항상 ..
[C++] 백준 18870: 좌표 압축 문제 이해- N개의 좌표: X1, ..., Xn 이 있다.- Xi를 좌표 압축한 결과 Xi'의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. - 시간 제한: 2초- 메모리 제한: 512MB N: 좌표의 개수 (1 ~ 1,000,000, 10^6)Xi: 좌표 (-10^9 ~ 10^9) X1', ..., Xn'을 공백으로 구분하여 출력하라.  문제 풀이배열을 두 개 사용하여하나는 원본 배열,하나는 중복된 값을 제거한 정렬된 배열 형태로 둔 뒤에,비교하여 순서를 출력하면 될 것 같았다.  중복된 값을 제거하고 정렬하는 건 vector에 내장된 unique 함수를 이용하였는데 다음과 같다.sort(v.begin(), v.end());v.erase(unique(v.begin(), v...

티스토리툴바