블로그

https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 이 문제 개인적으로 그냥 dfs만 쓰면 풀리는 문제..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 벽 부수고 이동하기 1번부터... 사용한 알고리즘: BFS (BFS를 사용했으므로 벽을 뚫고 가는 경우가 더 빠른지, 벽을 뚫고 가지 않는 경우가 더 빠른지 비교해 주는 IF문 등이 필요 없음을 이해하는 것이 중요하다고 생각한다) 또한, dp에서 0, 1 로 벽을 뚫었을 경우와 뚫지 않았을 경우를 나눠주는 이유는 해당 문제를 bfs로 풀려면 답에 영향을 주는 모든 상태를 ..

https://www.acmicpc.net/problem/17071 17071번: 숨바꼭질 5 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 500,000)에 있고, 동생은 점 K(0 ≤ K ≤ 500,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제에서 나는 -1, +1, *2 와 같이 위치를 이동할 수 있는데, *2의 경우는 일단 제쳐두고 +-1만 생각하면 t초에 X의 위치에 있었다면 t+2n 초에도 X의 위치로 갈 수 있다. *2가 있어서 헷갈리는데, *2가 있다고 해서 위의 말이 거짓이 되는 건 아니다. *2로부터 추가적인 규칙이 안 생길 뿐이지.. 그래서 일반적인 BFS와는 다르게, "t초에 ..

C언어는 0이 아닌 모든 값을 true라고 한다 그럼 음수값이나 소수는? 음수나 소수여도 다 true이다. 0은 float형으로 선언되어있어도 false이다 C++에서도 마찬가지

https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 괄호가 없을 때를 생각해 보면 */ 의 우선순위가 +- 보다 크고, stack에 있는 애보다 자기가 우선순위가 커야지만 들어갈 수 있다. stack에 있는 얘가 자기보다 우선순위가 같거나 크다면, 자기가 우선순위가 더 커질 때까지 stack에 있는 얘를 뽑는다 이 문제에서는, 괄호가 그걸 막게 되는데, * + 같은 경우 +가 들어가기 전에 *를 빼야 하지만 * ( + 와 같이 되면 *를 뺄 필..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net DFS + DP 모든 (i, j) 에 대해서, DP값(구해진 값) 이 없으면 해당 (i, j)부터 DFS를 들어간다 (있으면 그거 씀) for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (visit[i][j] == 0) { ans = max(ans, dfs(i, j)); } else ans = max(ans, visit[i]..

https://www.acmicpc.net/problem/1327 1327번: 소트 게임 홍준이는 소트 게임을 하려고 한다. 소트 게임은 1부터 N까지 정수로 이루어진 N자리의 순열을 이용한다. 이 게임에선 K가 주어진다. 어떤 수를 뒤집으면, 그 수부터 오른쪽으로 K개의 수를 뒤집 www.acmicpc.net 이론적으로 매 번 (N-K) 개의 경우의 수가 있는데 이 경우들 중에 어떤 경우를 선택해야 하냐는 문제 우선 그리디로 안되니까 그리디 제외, 규칙성도 찾기 어려우므로 그 외 알고리즘들 몇 개도 제외 브루트 포스로 가야할 것 같은데, (N-K)^(?) 가 되니까 도대체 언제까지 해야될지도 모르겠고 시간복잡도를 생각하기도 어렵다 따라서 매 번 N-K의 경우의 수로 바뀐 string이 있을 텐데 해당 ..

https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 그래프 탐색 문제 dp 풀기 싫어서 도피성으로 푸는 건 절대 아니고... 아마도....,, 처음에 문제 지문이 진심 저게 뭔소리지 하고 밑에 예제보고 그냥 이해한대로 풀어봤는데 아니더라 ㅋㅋ ㅠ 지문이 잘 이해가 안될 수 있는데 잘 읽어보면 말 그대로의 의미다 예제 1의 입력 같은 경우 산봉우리가 (0, 0)의 4와 (0, 6), (1, 6)의 1과 (대충아래쪽 3개..

https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 2회차? 숙제 출석은 안하고 숙제만 열심히 해가는 사람 맨날 못가서 죄송합니다........ bfs문제로 주셔서 당연히 풀어봤을줄 알았는데 안풀어봐서 당황 문제 봤는데 플로이드 워셜이 제일 좋아보여서 두 방법 다 해보려했는데 1000^3 이 너무 커서 당황 아 이거 bfs 의 특성을 이용해 최단거리를 구하는게 아니라 그냥 bfs의 탐색을 이용해 거리만 구하는거구나 라는걸 문제 풀다가 알아서 당황 암튼 dfs로도 되고 딱히 bfs가 필요한 문제..

dp가 너무 어렵다.. 너무 너무 어려워ㅣㄹㅇ리어ㅣㄹㅇㄹ 으악~ https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 배낭에 뭔가를 그만 싸라 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. ..