이름 못 정한 블로그

오늘은 드디어 해쉬에 대한 내용을 배웠다. 사실 이전까지의 내용들은 학부 수업을 들으면서 조금씩이라도 공부한 내용이었다면, 해쉬는 거의 배운 적이 없다. 배우더라도 이런게 있다 식으로만 지나갔던 것 같다. 실제로 해쉬가 여기저기에 많이 쓰이는 것으로 알고 있어서 꽤 궁금했었다. 하지만 더 찾아보지는 않았었다. 딱 이 정도로만 해쉬를 알고 있었는데 오늘 특강에서 배운 내용들은 좀 신기했다. 그리고 몇 문제를 풀었는데, 아무리 해도 시간 초과가 해결되지 않았다. 알고보니 그 문제는 KMP 혹은 라빈 카프 알고리즘을 적용해서 푸는 문제였다. KMP 알고리즘을 배우기는 했지만 배운지가 너무 오래돼서 기억이 가물가물하고 배울 당시에 되게 어려웠던 기억이 있어서 선뜻 KMP로 풀고 싶지 않았다. 그래서 라빈 카프 ..

2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있..

14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고, 동쪽을 바라보는 방향이 3인 상태로 놓여져 있으며, 놓여져 있는 ..

오늘은 heap 파트의 마지막 문제를 풀었다. 이번 문제는 어려운 알고리즘을 적용해야 하는 문제는 아니었다. 주어진 API를 기능에 맞게 구현하는 문제였다. API가 4~5개 정도 있었는데 하나를 빼고는 모두 어떤 상황을 만들기 위한 입력을 받는 부분이라 쉽게 구현할 수 있었다. 마지막 API는 내용이 어렵지는 않았지만 정확히 작동하도록 구현하는게 쉽지 않았다. 일단 입력이 상당히 난해해서 디버깅하는데 애를 좀 먹었다. main 부분 코드가 주어지기 때문에 알아서 API를 호출해준다. 그래서 아직도 입력 텍스트만 보고는 이게 뭘하고 싶은건지 모른다. 시간이랑 공간 제약은 상당히 넉넉해서 문제를 풀 때 거의 구애받지 않았다. 중간에 깨달았는데 나는 문제를 너무 어렵게 풀고 있었다. 크기가 고정된 배열인 경..

14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 문제 크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다. 오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다. 다음과 같은 N=6인 경우 지도를 살펴보자. 이때, 길은 총 2N개가 있으며, 아래와 같다. 길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 ..

설 연휴가 끝나고 오랜만에 평일이 됐다. 연휴 동안에 SWEA에 들어가 보니 heap 자료가 이미 올라와있길래 두 문제 미리 풀었다. 그리고 오늘은 세 문제 풀어놨다. 5년 전 자료구조 수업에서 heap을 배우고 이게 뭐야 했던 기억이 있는데 이제는 heap이 뭔지 알고 있다. 오늘 SWEA에서 문제를 풀면서 분명 heap 시간인데 문제가 너무 DP스러워서 일단 DP로 시작했다. 그런데 문제를 풀다보니 DP로는 해결되지 않을 것 같았다. DFS나 BFS 둘 중 하나를 사용해야 할 것 같길래 일단 무지성 DFS를 했다. SWEA는 스택 메모리가 야박하다는걸 segmentation fault를 보고 깨달았다. 그래서 BFS로 문제를 해결하고 있는데 아무리해도 답이 안 나왔다. 알고보니 DFS할 때 썼던 bo..

1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 알파벳 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이..

1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 민오는 1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 1번 문제가 가장 쉬운 문제이고 N번 문제가 가장 어려운 문제가 된다. 어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다는 것을 알게 되었다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건..

17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 문제 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다. 1 2 3 2 1 1 4 5 6 예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다. A[1][1] A[1][2] → A[1][3] → ..

2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 문제 KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다. 같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서..