컴퓨터공학 & 정보통신/알고리즘 문제 풀이41 [알고리즘] 벡터 크기 어림잡기 개요 알고리즘 문제들에는 메모리 제한이 있으며, 이를 준수하는 방식의 알고리즘을 작성해야 합니다. 벡터 메모리 크기 어림 잡기 안내 메모리 단위 : MB기준으로 설명합니다.* 예1) 원소의 갯수가 100,000 개인 정수형 벡터vector V(100000, 0);정수형 원소의 크기는 각 4B(byte) 이므로 벡터의 크기는 4 * 100 000 == 400 000B(byte).대략 백만 바이트가 1MB이므로, 400 000B(byte)는 0.4MB 라고 생각하면 됩니다. * 예2) vector V(100000000, 0);4억 바이트는 대략 400Mb 2024. 9. 22. [알고리즘] 대각선에 위치한 좌표 체크하기 개요 nqueens와 같은 문제 풀이 시 대각선을 체크할 필요가 있습니다. 알고리즘 문제 풀이에 도움이 되는 대각선 체크 코드를 공유합니다. 전제 백준 문제 풀이를 기반으로 솔루션을 설명합니다. COL 정수형 일차원 벡터는 i 번째 row에 놓인 퀀의 col 번호입니다. (없으면 0)vector COL(15, 0); 솔루션 row 및 col 값이 각각 2, 1 이라고 합시다.i == 0 일때 abs(1 - COL[0]) == 2 - 0 이므로 COL[0]이 3일때 대각선에 위치한 좌표(0,3)가 있음을 확인할 수 있습니다. i == 1 일때 abs(1 - COL[1]) == 2 - 1 이므로 COL[1]이 0 또는 2일때 대각선에 위치한 좌표가 있음(1,0 또는 1,2)을 확인할 수 있습니다.즉, 대각.. 2024. 9. 22. [백준] 1167 트리의 지름 C++ 문제 풀이 접근 해당 문제를 풀기 위해서는트리와 그래프의 차이점트리에서 임의의 노드 i 를 잡아 가장 먼 거리에 위치한 노드 j 를 찾았을 때 j로부터 가장 길이가 먼 노드 k를 찾음으로 트리의 지름을 구할 수 있음들을 반드시 이해해야 합니다. 이해했다면 총 두 번의 탐색을 통해 트리의 지름을 구할 수 있음을 알 수 있습니다. (두 번의 탐색을 통해 트리의 지름을 구할 수 있다는 말을 이해하고 동의해야 합니다)대부분 인터넷에서 찾을 수 있는 풀이는 dfs로 풀지만 전 다익스트라를 통해 풀어보겠습니다. 풀이 과정 탐색하는 그래프가 트리임이 보장되므로, 절대 사이클을 가지지 않습니다.사이클을 가지지 않으므로 최소 거리 == 해당 노드로 가는 거리 입니다.해당 노드로 가는 최장 거리와 최소 거리는 동일합니다.따라서 가장.. 2024. 9. 22. [알고리즘/수학] 나머지 분배 법칙 개요 나머지 분배 법칙은 사칙 연산의 분배 법칙과 다릅니다. 나머지 분배 법칙 아래 분배 법칙을 적용한 결과, 사칙 연산의 분배 법칙과 다르게 기존의 나머지 연산 적용이 남아있습니다.( a + b ) % mod = ( a % mod + b % mod ) % mod 알고리즘 문제에서의 주의점 간혹 알고리즘 문제에서 오버플로를 피하기 위해 편의 상 N을 나눈 값을 출력하라고 합니다. (예: 1000000) 앞서 설명했듯 나머지 분배 법칙은 사칙 연산의 분배 법칙과 다르다는 점을 명심해야 합니다. 두 개 이상의 경우에 수를 문제 풀이 과정에서 연산해야 하는 경우 한꺼번에 묶어서 나누어 주어야 합니다. 아래 두 연산은 서로 다른 값을 도출하기 때문입니다. 알고리즘 문제에서 요구하는 사항을 정확히 인식해서 나누어.. 2024. 8. 23. [백준] 1946 신입 사원 c++ 접근 두 가지의 성적을 비교하여 신입 사원 간 우위를 확인하기 위해서는 서류 성적을 먼저 정렬할 필요가 있어 보입니다. 그 후 면접 성적을 비교하여 가장 많은 신입 사원의 수를 계산해야 합니다. 정렬 후 첫 번째 신입사원은 다른 신입사원보다 반드시 서류 성적이 뛰어날 것이므로 면접 성적이 어떻게 되었든 반드시 합격하는 신입사원입니다. (정렬 후 그리디한 접근이 이 문제에서 반드시 최대의 경우의 수를 도출하는 이유입니다.) 첫 번째 신입 사원과 두 번째 신입사원의 면접 성적과 비교하였을 때, 만약 첫 번째 신입사원보다 면접 성적이 좋은 경우 두 번째 신입사원을 비교 기준으로 변경합니다. 달리 얘기해서, 이미 서류 성적이 낮은 세 번째 네 번째 ... 신입 사원들은 두 번째 신입사원보다 면접 성적이 높기만 .. 2024. 8. 11. [백준] 2178 미로 탐색 c++ 개요 항상 완전 탐색 문제가 모두 bfs 및 dfs로 풀 수 있는 것은 아닙니다. 이 문제는 bfs로 풀어야 하는 문제입니다. 접근 방법 (1,1) 좌표에서 (N,M) 좌표까지 이동하기 위해 필요한 최소 칸 수를 구해야 합니다.BFS 또는 DFS 기법을 통해 탐색을 해야 합니다.일반적인 완전 탐색의 조건은 아래와 같습니다.문제 요구사항에 만족하는 범위에 위치좌표의 값이 0이 아니며처음 방문문제 특성 상 (1,1)좌표를 제외하고 좌표의 값이 1인 경우일 때, 무조건 처음 방문하는 좌표입니다. 따라서 처음 방문하는 좌표를 계속 탐색하며 값을 갱신해 주면 됩니다. 솔루션#include #include #include #include using namespace std;int N, M;int dx[4] = {.. 2024. 8. 9. 이전 1 2 3 4 ··· 7 다음
