★☆☆☆☆☆☆☆☆☆ 문제 접근 방법 연결 요소의 개수는 bfs와 dfs로 둘 다 해결 가능한데 bfs가 조금 미숙하다고 생각해 bfs로 문제를 풀었다. bfs나 dfs를 모든 정점에서 시작을 하고 visit [] 배열에 이미 방문한 정점은 true로 처리해준다. 이후에 visit이 false인 정점에서만 시작하고 bfs와 dfs는 연결된 모든 정점을 정말 탐색하기 때문에, bfs 나 dfs 함수가 실행되는 횟수는 연결 요소의 개수를 뜻한다. #include using namespace std; bool visited[1001]; bool arr[1001][1001]; int N, M; int cnt; void dfs(int vertex) { visited[vertex] = true; for (int i ..

★★☆☆☆☆☆☆☆☆ 문제 접근방법 상하좌우로 움직이면서 벽(1)이 아니고 주어진 범위 밖이 아닐 때 그곳으로 이동하는 형식의 BFS문제이다. BFS인 이유는 최단거리를 구하는 문제이기 때문이다. 조금 고민했던 부분은 최단거리를 저장하는 방식을 고민했다. BFS과정에서 CNT변수로 하나씩 올리면서 처리하려고 했지만 중복되는 경우엔 CNT가 두 번 올라 가는 게 에러였다. 좀 더 고민해보니 BFS를 시작하는 칸의 값+1을 다음칸들에 저장하면 된다. 자세한 건 코드로 설명하겠다. #include #include #include using namespace std; queueQ; pairp; bool arr[101][101]; //1,0으로 이루어진 미로 int dis[101][101]; //최단거리를 저장 i..

★☆☆☆☆☆☆☆☆☆ 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 접근방법 단순하게 DFS와 BFS를 구현하면 되는 문제여서 바로 실행에 옮겼다. #include #include using namespace std; vectorcheck_dfs(1001); vectorcheck_bfs(1001); queueQ; int N, M, V; bool arr[1001][1001]; void dfs(int vertex) { check_dfs[vertex] = true; cou..

★★★☆☆☆☆☆☆☆ 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 문제 접근 방식 처음에 이문제를 봤을 때는 이게 왜 DP문제일까 생각했다. 브루트 포스 알고리즘으로 접근해서 풀어도 시간이 안 부족할 것 같다고 생각이 들었는데 조금 더 생각을 해보니까 1,4,5일 차를 상담하는 게 최댓값이라면 1,4,5일 차까지의 최대 수익이 필요하다고 생각했다. 그렇다는 것은 5일 차까지의 최대 수익은 5일 차에 일할수 있는 모든 경우의 수를 계산하는 것이다. 이 값을 계산하지않는다면 5일 차까지의 값이 계속 필요한 경우 계속해서 이전 절차(5일 차까지의 수익 구하기)를 반복해야 한다. 즉, 1,2,3,4,5,~N일까지의 최대 수익을 메모이제이션을 해주면 된다..

★☆☆☆☆☆☆☆☆☆ DP(dynamic programming) DP로 풀 수 있는 문제인지 확인하기. (입력이 엄청 크거나 시간이 메모이제이션을 하지 않으면 부족할 때) 문제의 변수를 파악하기 (재사용할 변수 찾기) 점화식 구하기 (fibonacci(n)=fibonacci(n-1)+fibonacci(n-2))와 같이 변수에 의해 값은 바뀌지만 같은 변수일 때 같은 값이어야 한다. 문제 접근법 문제의 입력을 보면 최대 90 자릿수까지 고려해야 한다고 하는데 90 자릿수까지 이친 수를 계산하는 것은 시간적으로도 불가능하고 90자리의 수를 받아줄 자료형도 떠오르지 않았다. 그래서 우선 분할 정복이 먼저 떠올랐다. 분할 정복은 큰 문제를 작은 문제로 나누어 해결하는 방법이다. 그래서 1~n까지의 자릿수가 규칙적..

더보기 ★★★★★★☆☆☆☆ 문제 접근방식 처음에는 톱니바퀴를 생각했다. 톱니가 10개인 바퀴와 12개인 바퀴로 생각해서 각 바퀴가 돌아갈 때 두 수의 차이만큼씩 간격이 생길 거라고 생각했다. 이게 무슨 말이냐면 아래와 같이 생각했다. 큰 바퀴가 돌 때마다 큰 바퀴의 수를 고정해놓으면 작은 바퀴의 수는 2씩 차이가 난다. 그래서 만약 x, y가 3,9이면 차이가 6이니까 2와 2x의 차이가 6인 줄(위에 표에서 해당)에서 x와 2의 차이만큼 n에 더 해주었을 때 y와 같으면 정답일 거라고 생각했다. ex) m=12, n=10, x=9, y=3일 때 9-3=6, 위의 표에서 세 번째 줄의 6에 7을 더 해주면 3이나 온다. 이런 식의 접근을 했는데 반례가 너무 많았다. 그래서 이 로직을 더 고민하면서 몇 가..