최선을다하는

https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 크기가 N×M인 행렬 A와 M×K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N×M×K번이다. 행렬 N개를 곱하는데 필요한 곱셈 연산의 수는 행렬을 곱하는 순서에 따라 달라지게 된다. 예를 들어, A의 크기가 5×3이고, B의 크기가 3×2, C의 크기가 2×6인 경우에 행렬의 곱 ABC를 구하는 경우를 생각해보자. AB를 먼저 곱하고 C를 곱하는 경우 (AB)C에 필요한 곱셈..

오늘 강의는 해쉬에 대한 내용이었다. 해쉬는 프로그래밍을 공부하기 시작하면서 처음부터 되게 많이 들어본 자료구조인데 실제로는 한 번도 써보지 않았다. 그냥 막연히 해쉬 버킷을 나누고 버킷에 원소를 넣어두는 형식으로 알고만 있었는데 실제로 해쉬 버킷을 나누고 관리하는 것이 중요한 부분이었다. 들어오는 원소를 특정 변환 함수로 변환을 해서 키값을 얻어내는데 이 키값으로 해쉬 버킷을 나누는 것이었다. 해쉬 버킷이 총원소의 수보다 적기 때문에 키값이 겹칠 수밖에 없는데 이때 해쉬 버킷의 원소는 최대한 균등하게 배분되어야 해쉬 버킷으로 나누는 의미가 있기 때문에 균등하게 나누는 것 역시 중요하였다. 연습 문제는 많이 풀지 못했는데 처음 사용하는 자료구조라 쉽게 풀 엄두를 내지 못하였다. 주말에 풀고 다시 올려야겠..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰인 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일..

KMP 알고리즘은 한 문자열(s)에 다른 문자열(p)이 몇번 나타나는지를 확인 할 수 있는 알고리즘이다. 문자열 p 의 앞과 뒤가 얼마나 같은지 미리 확인한 다음 두 문자열 s 와 p를 확인하다가 맞지 않는 부분이 나오면 한칸 옮기는 것이 아니라 겹치는 부분을 제외하고 넘어 갈 수 있다. #include #include #include using namespace std; vector getPi(string p) { int m = p.size(); int j = 0; vector pi(m, 0); for (int i = 1; i 0 && p[i] != p[j]) j = pi[j - 1]; if (p[i] == p[j]) pi[i] = ++j; } return pi..

위상 정렬은 선행되어야 하는 조건들이 주어지고 그 수들의 순서를 구해야 할 때 사용할 수 있다. 위상 정렬을 활용하기 위해서는 진입 차수와 인접한 노드를 알아야 한다. 진입 차수란 해당 노드가 실행되기 위해서 선행되어야 하는 노드의 개수를 뜻한다. 진입차수가 주어지면 진입 차수가 0 인 노드들부터 큐에 넣는다. 그다음 큐에서 원소 하나씩 확인하게 되는데 큐에서 pop 된 순서가 최종 순서가 되며 pop 이 되었다면 인접한 노드들의 진입 차수를 1 감소시킨다. 이때 인접한 노드의 진입 차수가 0이 되었다면 큐에 추가하여 자신의 순서가 확정되길 기다린다. 아래의 코드는 백준 2252번 줄세우기의 코드이다 #include #include #include using namespace std; int n,m, i..

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 ..

LCA 알고리즘은 트리 혹은 DAG에서 사용하는 알고리즘으로 최소 공통 조상을 구하는 알고리즘이다. 1. 각 트리의 깊이를 구한다. 루트 노드의 깊이는 0이다. 깊이를 구하면서 각 노드의 부모 노드도 저장해둔다. - BFS 와 DFS 등으로 구현할 수 있다. 2. 그 다음 각 노드의 2^K 승만큼의 부모 노드를 저장해둔다. - 모든 부모 노드를 저장할 필요가 없는 이유는 이진수가 모든 수를 표현할 수 있듯 3번째 조상을 구하려면 1번째 조상의 2번째 조상을 구하면 되기 때문이다. 3. 공통 조상을 구하는 두 노드 u v 중 더 깊은 노드를 같은 높이의 부모노드로 변경한다. 이는 비트 연산자로 구현할 수 있다. 그다음 두 노드들의 가장 윗 노드들부터 내려오면서 확인한다. 이때 두 숫자가 달라지는 시점이 공..

- LIS (Longest Increasing Subsequence) 1~N 번까지 순서대로 i번째 dp값을 최신화해준다. j는 i보다 작은 수 즉 배열의 앞에 있는 숫자라고 할 때 i번째 숫자가 j번째보다 크고 dp [i]가 dp [j] + 1보다 작다면 dp [i]의 값을 dp [j]+1로 최신화해준다. int arr[101]; int dp[101] ; int N,ans = 0; void LIS() { for (int i = 0; i arr[j]) { if (dp[i] < dp[j] + 1) dp[i] = dp[j] + 1; } } ans = max(ans, dp[i]); } } 위의 ..

https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는..

https://www.acmicpc.net/problem/1082 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 문제 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해야 한다. 문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 원하는 만큼 ..