코드 낙서장

1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 확인 map, set을 이용해 해쉬로 풀어도 되지만 느리므로 투 포인터 알고리즘으로 풉니다. 풀이 2개의 수를 잡아서 어떠한 수를 만들 수 있는지 확인하는 방식은 O(N^2), 하나의 수를 잡고 이 수를 만들 수 있는지 확인하는 방식 또한 O(N^2)지만 전자의 경우 그 수가 배열 안에 있는지 확인해야 하는 작업이 필요하므로 더 많은 시간이 필요합니다. 투 포인터 알고리즘을 사용하기 위해 먼저 정렬을 합니다. 그 후 두 포인터를 0, n-1에 두고 현재 확인할 수를 i : 0~n-1로..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 확인 경로 탐색 문제입니다. 단순 dp로 풀 수 있지만 최대 경우의 수 dp[10][1000][1000] 보다 bfs, 가지치기가 경우의 수가 적으므로 bfs으로 풉니다. 풀이 문제에서 핵심은 벽을 부수는 경우 최단경로가 달라질 수 있다는 점입니다. 따라서 벽을 부순 횟수에 따라 방문했던 칸을 다시 방문할 수 있으므로 다음과 같이 풀 수 있습니다. 처음 방문 : 현재 벽을 부순 횟수 k를 기록합니다. n번째 방문 : 기록된..

5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 확인 문자열 처리, 사전 검색 문제입니다. 사전 순으로 정렬하여 dfs 탐색으로 풀 수 있지만 간단하게 트라이 자료구조를 이용해서 풀 수 있습니다. 풀이 모든 입력을 트라이 자료구조에 삽입하고 현재 단어 위치에서 갈 수 있는 문자의 종류 개수를 count 변수로 둡니다. count 변수를 활용해서 자동완성이 가능한지 여부를 구할 수 있습니다. count == 1 : 현재 위치에서 갈 수 있는 문자의 종류는 하나, 따라서 자동완성이 가능합니다. count > 1 ..

9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 확인 소수 관련 문제입니다. 범위가 10000으로 적으므로 에라토스테네스의 체 알고리즘으로 간단하게 풀 수 있습니다. 풀이 10000 이하의 수를 에라토스테네스의 채 알고리즘을 통해 소수를 미리 구해둡니다. 그 후 가장 가까운 두 소수를 찾기 위해 입력받은 수에서 2를 나눈 2개의 변수를 두고 하나는 증가, 하나는 감소하며 두 변수 모두 소수일 때 출력합니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1..

1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 확인 괄호를 기준으로 이전 길이 값이 변경되므로 스택을 활용해서 풀 수 있습니다. 풀이 배열을 따라가면서 문자마다 3가지 경우로 나눌 수 있습니다. '(' : 바로 이전의 숫자의 곱만큼 길이가 길어지므로 ary[i-1], 이전 문자열의 길이를 저장합니다. ')' : 기록해둔 스텍을 반영합니다. 문자 : 현재 길이를 +1 합니다. 스택을 재활용하기 때문에 ')' 문자를 만나면 결과를 반영한 후 stack[top]=0 으로 초기화를 해 주어야 합니다. 코..

1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 문제 확인 dfs 커팅, 완전 탐색으로 풀 수 있지만 500x500 이므로 크기가 커서 효율성이 떨어지기 때문에 dfs, dp로 풀어야 합니다. 풀이 판다는 전 지역보다 옮긴 지역이 더 많은 대나무가 있어야 하므로 다음식을 항상 만족합니다. ary[ path[i][x] ][ path[i][y] ]

1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 확인 스트링에서 패턴 스트링을 찾는 문제는 대부분 kmp 알고리즘으로 풀 수 있습니다. 풀이 kmp 알고리즘을 그대로 적용하면 풀리는 문제입니다. 커누스-모리스-프랫 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서, 커누스-모리스-프랫 알고리즘(Knuth–Morris–Pratt algorithm, KMP)은 문자열 중에 특정 패턴을 찾아내는 문자열 검색 알고리즘의 하나이다. 문자열 ko.wikipedia...

1298번: 노트북의 주인을 찾아서 어느 날 모든 학생들은 한 명이 한개의 노트북을 가지고 공부하던 도중, 자리를 바꾸다가 그만 노트북이 뒤섞이고 말았다. 대다수의 학생들은 자신의 노트북을 잘 알고 있어서 자신의 노트북을 www.acmicpc.net 문제 확인 이분 매칭 그래프에서 최소 버텍스 커버 문제입니다. 풀이 백준 돌멩이 제거 문제와 동일합니다. [백준] 1867 돌멩이 제거 문제 주소 : www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째.. latter2005.tistory.com 학생과 노트북을 이분 매칭..

14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 문제 확인 구간 업데이트 처리 문제입니다. 세그먼트 트리를 활용해서 풀 수 있지만 점 쿼리 처리에 특화된 펜윅트리를 사용하여 더욱 빠르게 풀 수 있습니다. 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT) 펜윅 트리(Fenwick Tree, Binary Indexed Tree, BIT)란? 이전 게시물에서는 세그먼트 트리에 대해 게시물을 올렸다. (세그먼트 트리 :: http://www.crocus.c..

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 확인 1000 x 1000 크기 이므로 완전 탐색으로 풀면 시간 초과가 나므로 dp로 풀어야 합니다. 풀이 dp 배열의 의미를 현재 위치에서 만들 수 있는 최대 크기의 정사각형으로 둡니다. 현재 위치(i, j)에서 만들 수 있는 가장 큰 정사각형은 (i-1, j), (i-1, j-1), (i, j-1)의 최솟값 + 1 이 됩니다. 그 이유는 (i-1, j-1)의 값이 뒷부분 정사각형을 채워주고 (i, j-1), (i-1, j) 값이 새로워 가로를 채워주는 역할을 하기 때문입니다. 다음의 경우 dp[i-1, j-1] = 3, d..