개발자꿀꿀이

www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제가 기니까 잘 읽고 이해해야한다. 풀이 같은 극이 맞닿은 톱니는 돌아가지 않고 다른 극이 맞닿은 톱니는 반대 방향으로 돈다. 이 두개의 조건이 핵심이다. 해당 기어의 번호 앞뒤로 반복문을 통해 기어를 돌리는 전형적인 시뮬레이션 문제다. 시뮬레이션 문제는 노하우는 있겠지만 구현을 시켜내면 되는 문제기 때문에 시간이 많이 걸리는 편이다. n 번 톱니의 3번째 톱니와 n+1 번 톱니의 7번 톱니의 극이 같은..

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제가 길어서 직접 읽어보는 것이 좋겠다. 풀이 중복순열로 완전탐색을 해서 풀수도 있지만, 순열을 하나씩 만들어서 푸는 방법보다 DFS 로 하나씩 완전탐색하는 방식이 더욱 편할 것 같아 DFS로 풀었다. DFS로 오른쪽 왼쪽 위 아래 순서대로 밀었을때의 값을 저장하고 모든 방법을 돌리면, 4^5의 가짓수가 나온다. 이를 이용하여 풀면된다. 전형적인 시뮬레이션 문제다. static v..

문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않는..

문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영..

문제 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 하나씩 있는 패턴이다. *** * * *** N이 3보다 클 경우, 크기 N의 패턴은 공백으로 채워진 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태이다. 예를 들어 크기 27의 패턴은 예제 출력 1과 같다. 풀이 완전탐색 알고리즘에서 분할정복 알고리즘을 이용해서 푸는 문제다. 재귀를 이용해서 풀면쉽게 풀 수 있다. N = 27 일 때, 그림을 보면 N = 9 인 도형이 총 8개 있는 것을 알 수 있다. N = 9 일 때, 그림을 보면 N = 3 인 도형이 총..

문제 3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 1 2 3 4 5 6 7 8 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자. 1 3 4 2 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 7 8 6 1 2 3 4 5 6 7 8 가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오. 풀이 문제를 보면 BFS(너비 우선 탐색)로 풀어야 한다는 생각이 들지 않는다. ..

문제 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 풀이를 했다. 좀 더 직관적이고 보편..

문자열 문제중 정규표현식 문제와 정규표현식을 따로 정리해 놓겠다. 정규표현식의 기본 규칙이다. 자주 사용 되는 규칙이다. 이 외에 규칙들이다. /^[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..