이름 못 정한 블로그

2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 문제 한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모..

요새 터미널을 진짜 자주 만진다. 그러다보니까 패키지를 설치할 일도 많은데 패키지를 설치하기 위해서 검색을 하다보면 apt를 사용하라는 경우도 있고 apt-get을 사용하라는 경우도 있다. 똑같은 패키지를 apt로도 설치하고 apt-get으로도 설치하길래 도대체 무슨 차이인가 궁금했다. 결론은 둘 다 패키지를 설치하는 명령어임은 똑같다. apt는 apt-get과 apt-cache를 부분적으로 합쳐서 새로 만든 명령어다. apt는 apt-get에 비해 옵션이 조금 부족한 대신 사용자가 보기 편하게 만들었다. apt를 사용하면 진행 상황을 알려주기 위한 표시도 있고 메세지가 조금 더 자세하게 출력된다. 일반 사용자라면 apt를 사용하는게 조금 더 보기 편하지만, 조금 더 디테일한 스크립트 작업이 필요할 때는..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 문제 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 ..

오늘부터 B형 문제를 풀기 시작했다. 사실 원래 어제부터 풀었어야 했는데 어제 풀던 문제는 도대체 놓치고 있는 게 어떤 포인트인지 못 알아내서 결국 해결하지 못하고 그냥 넘어왔다. B형 문제의 첫인상은 생각보다 할만해 보이는데? 였지만 B형 문제는 B형 문제였다. 구현이 진짜 너무 힘들었다. 설계에 시간을 많이 투자하라는 말이 진짜 빈 말이 아니었다. 대충 이 정도면 됐겠지 싶어 바로 코딩에 들어갔다. 설계가 부실한 상태로 코딩을 하다 보면 중간중간에 디테일을 즉흥적으로 구현하게 되고 그 중구난방 한 디테일들이 모여서 큰 문제를 만들어낸다. 디테일하게 설계할수록 구현이 쉽고 디버깅할 것도 많이 없다. 내가 이 문제를 어떻게 풀지 딱 정해놓는 게 필요할 것 같다. 이랬다 저랬다 하면 나만 더 피곤 해질 뿐..

오늘부터는 역량테스트 B형 공부를 시작하게 됐다. 하루에 한문제씩 올라오게 되는데 아직 기초 문제도 다 못 풀어서 오늘 올라온 문제는 시작도 못했다. 어제부터 한 문제를 계속 붙잡고 있는데 도저히 해결이 되지 않는다. 일단 예시 입력까지는 다 맞았는데 제출하면 어림도 없다. 원래는 매일 백준 문제를 1개씩은 풀면서 따라왔었는데 도저히 불가능할 것 같다. B형 시험은 제한시간이 4시간이다. 그런데 4시간 안에 풀면 B형을 붙을 수 있는 수준이라 한참 부족한 나는 4시간보다 더 오래 걸릴 것 같다. 하루에 최소 4시간씩은 한문제만 붙들고 있을텐데 연구실 인턴하면서 1일 1백준까지 하기엔 시간이 너무 부족하다. 가끔 시간 여유가 생기면 간간히 풀어야겠다. 그런데 지금 풀고 있는 문제는 왜 풀리지 않을까...?

이제 연습 파트는 거의 다 끝났고 내일부터는 실전 문제를 풀게 된다. 최종 목표는 삼성 역량 테스트 B형을 취득하는 건데 아마 그건 쉽지 않을 것 같다. 특강이 끝나기 전에 테스트를 보게 되는데 거의 손도 못 대고 나올 것 같다... 뭐 되는 데까지는 해봐야지. 그리고 오늘 문제를 풀면서 Trie라는 자료구조를 새로 알게됐다. 문제에 Trie를 적용해서 풀어야 하는데 나는 전혀 모르는 자료구조라서 일단 자료구조 공부부터 했다. 곧 문제도 풀어봐야지.

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

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 워드프로세서 등을 사용하는 도중에 찾기 기능을 이용해 본 일이 있을 것이다. 이 기능을 여러분이 실제로 구현해 보도록 하자. 두 개의 문자열 P와 T에 대해, 문자열 P가 문자열 T 중간에 몇 번, 어느 위치에서 나타나는지 알아내는 문제를 '문자열 매칭'이라고 한다. 워드프로세서의 찾기 기능은 이 문자열 매칭 문제를 풀어주는 기능이라고 할 수 있다. 이때의 P는 패턴이라고 부르고 T는 ..

오늘은 딱히 새로운 내용을 배우진 않았고, 대신 꽤나 큰 문제를 하나 풀었다. 이 문제도 주어진 명세에 맞게 API를 구현하는 문제였다. 데이터베이스를 관리하기 위해 삽입, 삭제, 수정, 검색 기능을 구현해야 했다. 이전까지 이런 유형의 문제는 대부분의 함수는 쉽고 한두 개의 함수들만 빡 어려웠었는데, 아직 내가 해쉬에 익숙하지 않아서인지 이번 문제는 전체적으로 난도가 있었던 것 같다. 해쉬를 잘 관리하는 게 생각보다 쉽지 않았다. 막연하게 당연하지라고 생각했던 사실들을 이 문제를 풀면서 몸소 느꼈다. 1. 두 문자열의 해쉬 값이 같다고 해서 둘이 같은 문자열임을 보장할 수는 없다. => 그렇다고 충돌이 일어날 때마다 두 문자열을 검사하면 시간 복잡도가 폭발적으로 증가할 수 도 있다. 그래서 대충 맞다고..

3033번: 가장 긴 문자열 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. www.acmicpc.net 문제 상근이는 꿈에서 길이가 L인 문자열을 외웠다. 꿈에서 깬 상근이는 이 문자열을 종이에 적었다. 종이를 적던 중에 어떤 문자열은 두 번 이상 등장하는 것 같은 느낌을 받았다. 문자열이 주어졌을 때, 두 번 이상 등장한 부분 문자열 중 가장 길이가 긴 것을 찾는 프로그램을 작성하시오. (부분문자열은 겹쳐서 등장할 수도 있다) 입력 첫째 줄에 L이 주어진다. (1 ≤ L ≤ 200,000) 다음 줄에는 길이가 L이면서 알파벳 소문자로 이루어진 문자열이 주어진다. 출력 첫째 줄에 두 번 이상 등장하는 부분 문자열 중 길..