최선을다하는

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이..

No1. 메모장 프로그램 실제 메모장 처럼 원래 있는 텍스트 문자열을 읽어들인 다음 커서의 위치에 삽입, 커서 옮기기, 그리고 커서 뒤에있는 특정 원소의 개수 찾기 총 3가지의 기능을 만드는 문제였다. 구상을 최소 한시간 그리고 1시간 반까지도 해도 된다는 코치님들의 말을 실천하고자 우선 펜 부터 잡았다. 처음에는 메모장의 최대 크기가 300*300 이여서 배열을 2배 사이즈로 놓고 짝수 인덱스는 커서 홀수 인덱스는 문자로 놓고 풀려고 했다. 하지만 조금만 더 생각 해보니 삽입 연산을 추가하면 문자들이 한칸 씩 뒤로 밀리게 되어 배열을 사용하면 절대 안될 것 같았다. 만약 구상을 하지 않았다면 배열로 열심히 구현하다가 눈물을 머금고 지울뻔 했다. 그래서 삽입 연산에 유리한 링크드 리스트를 활용하려 하였고..

https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 ..

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 중 더 깊은 노드를 같은 높이의 부모노드로 변경한다. 이는 비트 연산자로 구현할 수 있다. 그다음 두 노드들의 가장 윗 노드들부터 내려오면서 확인한다. 이때 두 숫자가 달라지는 시점이 공..