본문 바로가기

Algorithm/Baekjoon38

11725_트리의 부모 찾기 ▶ 실버 2 (트리) 문제 풀이 처음엔 queue 를 선언하여 parent 배열이 다 채워질 때까지 노드 쌍을 queue에 다시 삽입하는 방법을 생각했다. 하지만 O(N^2) 시간복잡도로 시간 초과가 났다. 그래서 bfs, dfs 중 bfs를 이용하여 풀었다. 코드 #include #include #include #include #include #include #include #define MAX 100001 using namespace std; int n; vector tree[MAX]; queue q; bool visited[MAX]; int parent[MAX]; void bfs() { q.push(1); while(!q.empty()) { int start = q.front(); q.pop(); .. 2023. 8. 4.
11497_통나무 건너뛰기 ▶ 실버1 풀이 간단하게 수를 정렬하여 인접한 수의 차의 최대가 최소가 되도록 하면 되는데, 중요한 것은 첫 인덱스와 마지막 인덱스 역시 인접하다고 간주하는 것이다. 1, 2, 3, 4, 5가 주어진다면 가장 큰 수인 5를 중심으로 멀어질수록 정렬한 순으로 작아지면 된다. 결국, 1, 3, 5, 4, 2의 순으로 배치해야 최솟값을 구할 수 있다. 따라서 일단 주어진 배열을 정렬하고, 2칸 씩 건너뛰면서 수의 차를 확인한다. n이 짝수일 경우에는 n / 2번을, n이 홀수일 경우에는 n / 2번 시행한 후 마지막 인덱스도 포함하기 위해 한 번 더 시행한다. 코드 #include #include #include #include #include #include using namespace std; int ar.. 2023. 3. 16.
2477_참외밭 ▶ 실버2 풀이 입력은 항상 6번 주어지고, 전체 사각형 - 작은 사각형의 방식으로 면적을 구한다. 방향과 길이가 주어지는데, 두 번 주어지는 방향이 두 개이고 한 번 주어지는 방향이 두 개이다. 두 번 주어지는 방향에서 작은 사각형이 존재한다. ex) 7 4 50 2 160 3 30 1 60 3 20 1 100 전체 사각형: 50 * 160 작은 사각형: 60 * 20 전체 사각형은 한 번만 주어지는 방향의 길이를 곱하면 되고, 작은 사각형은 두 번 주어지는 방향 중 가운데 두 길이를 곱하면 된다. 따라서, 두 번 주어지는 방향과 한 번 주어지는 방향을 구분하고, 한 번 주어지는 방향 중 가운데 껴 있는 두 길이를 구한다. 코드 #include #include #include #include #incl.. 2023. 3. 12.
1339_단어 수학 ▶골드4 문제 풀이 이 문제는 문자 간의 우선순위를 정하는게 중요한 문제였다. 주어진 문자들 중에서 가장 큰 자릿수를 가진 문자가 가장 큰 수를 부여받고, 그 다음 큰 자릿수를 가진 문자가 그 다음 큰 수를 부여받고.... 이런 순으로 주어진 모든 문자에 숫자가 할당되면 이를 더하고 값을 출력한다. 처음에는 어렵게 생각해서 문자열이 긴 순으로 저장하고 문자를 할당하는 map을 따로 만들어서 할당 여부를 확인하고...뭐 이런식으로 진행했는데 너무 비효율적인 방법이었다. 자릿수를 생각하지 않아도 되도록 주어진 알파벳의 번호에 해당하는 인덱스 배열에 자릿수에 해당하는 값을 더한다. ex) ACDB -> 1320(거꾸로) -> alpha[0] = 1, alpha[2] = 10, alpha[3] = 100, al.. 2023. 3. 8.
1080_행렬 ▶실버1 문제 풀이 먼저 행렬 A와 B를 입력받고, 같은 위치에 있는 A와 B의 요소가 다른지 확인한다. 새로운 2차원 배열 C를 생성하고 두 수가 다르다면 1, 같다면 0을 C에 넣는다. C의 요소를 모두 탐색하면서 C의 요소가 1이라면 그 주변의 3 X 3 행렬을 모두 토글하고 다시 탐색한다. 전부 탐색을 했다면 C 행렬의 요소가 모두 0일 경우에만 정답을 출력하고, 나머지 경우에는 -1을 출력한다. 코드 #include #include #include #include #include #include #include #include using namespace std; string a[51]; string b[51]; //a와 b의 차이 유무를 나타내는 행렬 int c[51][51]; int main.. 2023. 3. 7.
1213_팰린드롬 만들기 ▶실버3 문제 풀이 생각해야할 것 1. I'm Sorry Hansoo가 출력될 조건 : 문자의 개수가 홀수인 문자가 두 개 이상일 경우 2. 사전 순으로 출력하는 방법 3. 절반 인덱스 지나면 반대로 출력하는 방법 먼저 문자의 개수를 세기 위해 배열을 선언하고 입력한 문자의 개수를 센다. for문으로 A부터 차례대로 탐색하는데, ① 해당 알파벳 개수가 존재하지 않는 경우, ② 알파벳 개수가 홀순데 처음 등장했을 경우, ③ 알파벳 개수가 홀순데 또 등장했을 경우, ④ 알파벳 개수가 짝수인 경우 로 나누어 진행한다. ① 해당 알파벳 개수가 존재하지 않는 경우 ☞ 다음 과정을 진행하지 않고 건너뛴다. ② 알파벳 개수가 홀순데 처음 등장했을 경우 ☞ 홀수 개 문자가 등장했다는 것을 불리언 값으로 나타내고, 정답.. 2023. 3. 5.

티스토리툴바