개발자꿀꿀이

문제 오늘은 ACM-ICPC 대회 전 날이다. 상근이는 긴장을 풀기 위해서 팀원들과 근처 술집으로 갔다. 상근이와 친구들은 다음 날 있을 대회를 연습하기 위해서 작은 게임을 하기로 했다. 먼저, 선영이는 상근이에게 총 N개의 정수로 이루어진 수열 X1, X2, ... XN을 적어준다. 게임은 총 K번 라운드로 이루어져있고, 매 라운드마다 선영이는 상근이에게 명령을 하나씩 내린다. 명령은 아래와 같이 두 가지가 있다. 변경: 이 명령은 친구가 수열의 한 값을 바꾸고 싶을 때 사용한다. 곱셈: 선영이는 상근이에게 i와 j를 말한다. 상근이는 Xi × Xi+1 × ... × Xj-1 × Xj 의 값이 양수인지, 음수인지, 0인지를 대답한다. 곱셈 명령에서 상근이가 대답을 잘못했을 때의 벌칙은 소주 한 잔이다...

문제 N개의 도시와 그 도시를 연결하는 N-1개의 도로로 이루어진 도로 네트워크가 있다. 모든 도시의 쌍에는 그 도시를 연결하는 유일한 경로가 있고, 각 도로의 길이는 입력으로 주어진다. 총 K개의 도시 쌍이 주어진다. 이때, 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 구하는 프로그램을 작성하시오. 풀이 LCA 문제에서 SparseTable 에 2^i 의 조상까지의 경로에 최소와 최대를 저장할 배열을 두개 더 선언한다. pmax[][] : 2 ^ i 까지의 조상으로 가는 경로에 최댓값을 저장 pmin[][] : 2 ^ i 까지의 조상으로 가는 경로에 최솟값을 저장 이 두가지의 배열을 이용하면 값을 구할 수 있다. LCA 코드를 보겠다. public static nod..

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 conpulake.tistory.com/62 백준 1761 (정점들의 거리) - LCA 풀이 문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해 conpulake.tistory.com 앞서 선형방식으로 간단하게 풀었지만 SparseTable을 이용해서 풀면 시간복잡도가 훨씬 줄어든다. conpulake.tistory.com/61 백준 11438 ( LCA 2) ..

문제 N(2 ≤ N ≤ 40,000)개의 정점으로 이루어진 트리가 주어지고 M(1 ≤ M ≤ 10,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 풀이 선형 시간의 LCA 알고리즘을 사용하였다. 해당 LCA까지의 간선 비용을 모두 합한 것이 두 정점 사이의 거리가 된다. 배열은 세개를 선언하였다 parents[] : 해당 정점의 바로 위 조상을 저장 하는 배열 parent_len[] : 해당 정점의 바로 위 조상과의 거리를 저장하는 배열 depth[] : 1번 정점을 제일 큰 조상을 두고 그로 부터의 깊이를 저장하는 배열 거리를 구하는 코드는 아래와 같다. public static int find_Dist(int a, int b) { if(depth[a] < depth[b]) {..

문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 풀이 conpulake.tistory.com/60 백준 11438 (LCA 2) - 최소공통조상(HLD 풀이) 문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 conpulake.tistory.com 위의 링크에서 HLD 풀이를 했다. 좀 더 직관적이고 보편..

문제 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 풀이 최소 공통 조상(Lowest Common Ancestror)을 찾는 문제다. 방식은 여러가지가 있겠지만 HLD(Heavy-Light Decomposition)의 Heavy-Edge 와 Light-Edge 로 구분한 것을 이용해 트리를 분할하여 푸는 방식을 이용하여 풀었다. Heavy-Edge : 각 정점에서 아래로 뻗어나가는 간선중에서 가장 무거운 간선을 의미한다.( 여기서 무겁다는 것은 자식이 가장 많은 정점으로 이어지는 ..

문자열 문제중 정규표현식 문제와 정규표현식을 따로 정리해 놓겠다. 정규표현식의 기본 규칙이다. 자주 사용 되는 규칙이다. 이 외에 규칙들이다. /^[0-9a-zA-Z]([-_\.]?[0-9a-zA-Z])*@[0-9a-zA-Z]([-_\.]?[0-9a-zA-Z])*\.[a-zA-Z]{2,3}$/i 이메일 /^01([0|1|6|7|8|9]?)-?([0-9]{3,4})-?([0-9]{4})$/ 핸드폰 번호 백준 1013 (Contact) www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1..

www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제가 길어서 링크를 넣는다. 이 문제에서 풀이 방식을 설명하고 있다. 풀이는 KMP 알고리즘을 이용하면 된다. KMP 알고리즘은 빠르게 같은 문자를 찾는 방식이다. 접두사로 접미사에 얼마나 연속적으로 나오는가를 이용하는 알고리즘이다 시간복잡도가 O(n) 에 가깝기 때문에 많이 사용 되고 있다. bowbowbow.tistory.com/6 KMP : 문자열 검색 알고리즘 문자열 검색이 뭐지? 워드프로세서를 ..

문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다. 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다. 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다. 폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다. 풀이 스택과 문자열처리에 관한 문제다. 스택을 직접 사용하지 않고 스택의 자료구조..

문제 문자열과 놀기를 세상에서 제일 좋아하는 영식이는 오늘도 문자열 2개의 LCS(Longest Common Subsequence)를 구하고 있었다. 어느 날 영식이는 조교들이 문자열 3개의 LCS를 구하는 것을 보았다. 영식이도 도전해 보았지만 실패하고 말았다. 이제 우리가 할 일은 다음과 같다. 영식이를 도와서 문자열 3개의 LCS를 구하는 프로그램을 작성하라. 풀이 LCS 의 개념을 미리 앞에서 풀어 봤기 때문에 문제를 이해하는데는 어렵지 않았다. conpulake.tistory.com/55 백준 9252 (LCS 2) 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. ..