본문 바로가기

분류 전체보기

 (33)
열통망했다 열과 통계물리에서 살면서 제일 안좋은 점수를 받았다. 정말 여러가지로 할 말이 많지만, 드랍도 못했고 강의가 정말 좋으니 기말 100점을 바라는게 맞는것 같다. 최대한 걸수있는 클레임은 다 걸고 열심히 공부해야겠다. ㅜㅜ
[ICPC 본선 대비 뇌셋] Day 10 백준 16326번 Numbers www.acmicpc.net/problem/16326 16326번: Numbers In the first test, the following pairs of numbers are suitable: (5, 151), (55, 101), (101, 55), (151, 5). In the second test, the following pairs of numbers are suitable: (515, 9009), (636, 8888), (8888, 636), (9009, 515). In the third test, the following www.acmicpc.net 마찬가지로 NEERC set을 돌다가 만난 문제인데, 코딩은 좀 복잡할 것 같아 풀이만 남긴다. 레프 화이팅>y..
[ICPC 본선 대비 뇌셋] Day 9 알고리즘 시험이 끝났기 때문에 나를 막을 수 있는건 계측 뿐이다...... 오늘부터는 꾸준히 몇문제씩 올릴 예정 백준 16329번 space station www.acmicpc.net/problem/16329 16329번: Space Station The first line contains the number T, representing the number of tests. The first line that describes a test contains the three variables N M K. (1 ≤ N, M ≤ 1000) The following N–1 lines are of the form A B C (1 ≤ A ≤ B ≤ N; 0 ≤ C, K ≤ 106) www.acmicpc.net 며칠..
시험 성적에 대해서. 이번학기에는 총 23학점으로 다음과 같은 과목을 듣는다. 1. 전기와 자기 2. 수치해석개론 3. 열 및 통계 물리 4. 양자물리 2 5. 복소함수론 2 6. 계측 7. 알고리즘 사실 j같음의 순서대로 적으려고 했지만, 있는 듯 없는듯한 알고리즘의 존재를 까먹어서 마지막에 적었다. 아주 솔직히 말하자면, 전체 난이도의 합은 그렇게 높지 않다. 근데 4, 5, 6이 아주 그냥 혼을 빼먹는다. 지금까지 수치해개, 열통, 복소2의 시험을 봤는데, 열통은 지금까지 본 물리과 시험 중에서 제일 조졌고, 복소도 나름 조졌다. 문제는 나는 시험 성적에 대한 스트레스를 엄청 받는다는거다. 시험을 망하면 의욕이 떨어져서 공부도 안하고, 드랍고민만 하다가 PS하고..(사실 이건 악역향인지는 모르겠다) 그런다. Q3를 확실..
[ICPC 본선 대비 뇌셋] Day 8 백준 8987번 수족관 3 www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 그리디로 찾으면 된다. 제일 물이 많이 빠지는 것을 찾은 후, 그 다음에 물이 제일 많이 빠지는 것을 찾고, 그 과정을 반복한다. [증명] 제일 많이 빠지는 점을 S1이라고 하자. S1에서 물을 빼면 S1을 기준으로 양 옆으로 갈수록 수위가 높아진다. 그리고 이를 첫번째 수위라고 정의하자. 만약 S2, S3를 뺀 것이 S1, S2를 뺀 것보다 양이 많다고 가정..
[ICPC 본선 대비 뇌셋] Day 7 백준 4009번 순찰 www.acmicpc.net/problem/4009 4009번: 순찰 1부터 N까지 번호가 붙여진 N개의 마을과, 이들 마을을 모두 연결하는 N-1개의 도로가 있다. 각 도로는 정확히 두 마을을 연결하며, 임의의 마을로부터 다른 모든 마을까지 이들 도로들만 이용하�� www.acmicpc.net 왜인지 모르겠으나 점점 강해지는 느낌이 든다.. [관찰 1] 지름길을 하나 박으면, 두 끝 정점 사이의 최단 경로에 있는 도로는 한번만 이동해도 되며, 나머지 도로는 두번씩 지나가야 한다. [관찰 2] 지름길을 두개 박으면, 관찰 1과 비슷한 식으로 생각할때, 두 개의 최단 경로를 잡을 수 있고, 이들 중 중복되지 않는 도로는 한번씩만 이동해도 되고, 중복되거나 경로에 포함되지 않은 도로는 ..
[ICPC 본선 대비 뇌셋] Day 6 백준 1868번 보물찾기 www.acmicpc.net/problem/1868 1868번: 보물찾기 첫째 줄에 n이 주어진다. (1≤n≤50,000) 이후 n-1개의 줄에는 각각 두 개의 숫자가 주어진다. a와 b가 주어졌다면, a번 방과 b번 방 사이에 복도가 있어 왕래할 수 있다는 의미이다. 방의 번호는 1번부 www.acmicpc.net 이 문제를 본지 1주일만에 풀이를 쓰는 것 같다. 방법은 대충 생각하고 있었는데 구체화가 너무 더뎌 푸는데 오래걸렸다. 여담이지만, 내 첫 루비를 장식하게 되었다. [시도 1] 트리의 지름일 것이다. --> 반례를 찾을 수 있다. [시도 2] centroid decomposition을 하면 될 것이다. --> 반례를 찾을 수 있다. 일반적인 그리디를 통해서 문제를 접..
[ICPC 본선 대비 뇌셋] Day 5 백준 17970번 Islands www.acmicpc.net/problem/17970 17970번: Islands Your program is to read from standard input. The input starts with a line containing an integer n (5 ≤ n ≤ 100,000), where n is the number of villages in each island. The villages are numbered from 1 to n. In the following two lines, each line contains www.acmicpc.net 증명이 까다롭기는 하나 그렇게까지 어려운 문제는 아닌 것 같다. 사실상 왜 다이아 2인지는 잘 모르겠다. 물론 작년의..
[ICPC 본선 대비 뇌셋] Day 4 백준 19619번 자매도시 www.acmicpc.net/problem/19619 19619번: 자매 도시 첫번째 예제에서, N = 5, M = 6, U = [0, 0, 1, 1, 1, 2], V = [1, 2, 2, 3, 4, 3], W = [4, 4, 1, 2, 10, 3], Q = 3, X = [1, 2, 0], Y = [2, 4, 1]이다. 이 예제는 다음 그림과 같다. 그레이더는 처음에 init(5, 6, [0, 0, 1, 1, 1, 2] www.acmicpc.net 두 간선을 거리 w로 정렬한 뒤 하나씩 추가해나가면서 문제를 해결하면 된다. 역시 보물찾기를 보고 나니 다른 문제들이 쉬워보인다. 편의상 라인을 일렬로 연결된 그래프라고 부르자. w의 크기순으로 j번째 간선(거리 v[j]라고 하자)까..
[ICPC 본선 대비 뇌셋] Day 3 숙제와 시험이 너무 많고 보물찾기 문제가 너무 어려워서 못쓸뻔했지만 정원은 나름 쉬워서 먼저 풀이를 적는다. 백준 5484번 정원 www.acmicpc.net/problem/5484 5484번: 정원 재현이는 BOJ에서 가장 아름다운 정원을 소유하고 있는 사람으로, 정원에 n개의 꽃을 심어놓았다. 모든 꽃들이 화사하게 핀 여름날. 재현이는 아름다운 꽃들을 보고 있으니 갑자기 대한민국의 경 www.acmicpc.net 별로 생각 안하고 짜도 되지만 구현이 좀 더럽다. 또, 풀이에서는 1베(one based)를 쓰는 것이 이롭다는것을 느꼈다. 전처리: 모든 가능한 sub 가로줄과 sub 세로줄의 장미수를 구한다. --> 250^3 = 1e7 문제를 보는 순간 (i, j)를 왼쪽 아래 꼭지점으로 가지고 정확히..

티스토리툴바