본문 바로가기

분류 전체보기63

[BAEKJOON] 1967 트리의 지름 (C++) 오늘은 트리 관련 문제를 풀기로 결정했다. 요즘 알고리즘연습 수업에서 트리를 다루는데 따라가기 벅찼기 때문. 문제는 그림을 잘 줘서 이해하기 수월했다. 전체 트리를 쭉 늘렸을 때 지름이 가장 큰 부분을 찾아서 출력하는 것. 내가 생각한 방법은 다음과 같다. dfs를 호출하면 해당 노드에서 가질 수 있는 길이의 한 부분(양팔 중 한 팔)의 최댓값을 리턴해준다. 그리고 호출받은 값과 해당 노드까지의 거리를 더해서 현재 노드에서 가질 수 있는 길이 한 부분의 최댓값을 구한다. 또 최댓값과 두번째 최댓값을 더해서 해당 노드에서 가질 수 있는 지름의 최댓값을 구하고 ans를 업데이트 할 수 있다면 업데이트 해준다. int dfs(int v) { if (tree[v].size() == 0) return 0; int.. 2023. 4. 25.
[BAEKJOON] 1744 수 묶기 (C++) 광기의 이왜않 오늘 그리디 재밌길래 풀었는데 진짜 이왜않은 무한반복이다. 이거 전에도 1339 단어수학 풀었는데 비슷했다. -> 알파벳이 순서대로 10개만 나올거라는 안일한 생각을 해버렸다. https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 이 문제는 그리디 문제라는 걸 알고 풀긴 했지만, 그리디의 경우는 충분히 케이스들을 확실히 나눌만 한 상황들이 주어지는 것 같다. 키 포인트는 1. 음수는 음수끼리, 양수는 양수끼리 곱하되, 절댓값이 큰.. 2023. 4. 24.
[BAEKJOON] 1043 거짓말 (C++) 첫 시도 입력을 받으면서 해당 파티(i번째)에 진실을 아는 사람이 있다면 해당 파티에 있는 모든 사람을 진실을 아는 사람에 추가한다. -> konwTrue 배열에서 1로 체크돼있다면 진실을 아는 것. 또 사람마다 방문한 파티를 2차원 배열로 유지한다. -> peopleParty[1] 에 있는 값들은 1이 방문한 파티 마지막으로 1번부터 n번까지 돌면서 진실을 아는 사람이 간 파티를 체크한다. ->lieParty[1] ==1 이라면 1번파티는 진실을 아는 사람이 방문한 파티 lieParty를 돌면서 ans값을 업데이트 한다. 결과 : 안됨. 왜 안되는지 생각해봐도 모르겠다.. 오기로 더 해보려다가 이미 너무 시간을 많이 써서 다른 사람들의 풀이를 참고 #define _CRT_SECURE_NO_WARNING.. 2023. 4. 23.
[BAEKJOON] 1780 종이의 개수 (C++) 분할정복을 사용하는 문제 알고리즘연습에서 과제로 나왔던 448C문제처럼 재귀를 이용해 해결해야겠다는 생각이 들었다. https://codeforces.com/contest/448/problem/C Problem - C - Codeforces codeforces.com 처음에 배열을 입력받고, 시작인덱스의 좌표, 사이즈를 dfs함수에 넘겨서 재귀를 시작한다. (초기조건 -> 1,1,n) 이후 배열의 첫 숫자와 비교해서 다른 값이 범위내에 존재하는 경우 해당 배열 사이즈를 3으로 나눠서 총 9번의 dfs를 다시 호출하도록 하였다. 함수에 넘어온 size의 값이 1인 경우는 그냥 종이 한 장으로 계산되므로 해당 값을 정답에 업데이트하고 함수를 종료시켰다. 이론상 완벽했는데, 제출에 실패해서 테스트케이스를 좀 .. 2023. 4. 23.

티스토리툴바