코드 낙서장

2836번: 수상 택시 상근이가 살고 있는 도시에는 큰 강이 흐르고 있고, 모든 사람의 집은 이 강 근처에 있다. 집은 0번부터 M번까지 강을 따라서 번호가 매겨져 있고, 인접한 집 사이의 거리는 모두 1 킬로미터이다. www.acmicpc.net 문제 확인 경로를 합칠 수 있으면 길이가 단축되므로 경로들을 정렬해서 합칠 수 있는지 확인하는 스위핑 문제입니다. 풀이 출발지가 목적지보다 왼쪽, 낮은 수인 경우 M으로 가는 도중 처리할 수 있으므로 배열에 넣지 않습니다. 배열에는 목적지가 출발지보다 왼쪽에 있는 경우만 선택해서 담아 이를 목적지 기준으로 정렬합니다. 경로를 합칠 때 돌아갔다가 오는 길이를 줄이기 위해서는 서로 겹치는 부분이 있는 경우만 합쳐서 새 경로를 만들어 줍니다. 예를 들어 다음과 같은..

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로..

2020 카카오 블라인드 채용 코딩 테스트 문제입니다. 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제 확인 스트링 처리 문제입니다. 풀이 문제 조건에 따라 경우의 수를 나눕니다. 압축한 패턴이 반복되는 횟수가 1인경우 패턴 그대로 입력합니다. 반복 횟수가 2 이상인 경우 : 길이가 1인 경우 "a2", "aa" 같으므로 length + num, 그 이상인 경우 length + num로 해결할 수 있습니다. num은 횟수를 문자열로 나타냈을때 길이이므로 log10을 취해 구할 수 있습니다. 코드 ..

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] ]

String : char 들의 집합으로 문자열을 의미하며 보통 varchar(N)으로 표현됩니다. Date : 날짜를 나타내는 변수로 "년/월/일" 형식입니다. Datetime : 날짜, 시간을 모두 포함하는 변수로 "년/월/일 시/분/초" 형식입니다. STRING 문자열 처리 시 보통 많이 사용하는 비교 구문으로 LIKE 가 있습니다. 주로 WHERE 절에 사용되며 문자열에 부분적으로 일치하는 패턴이 있는지 확인할 때 사용합니다. WHERE '칼럼' LIKE '조건' '%' : 해당 위치에는 어떠한 '문자열'이 와도 상관없음, 빈문자열도 가능함 '_' : 해당 위치에는 어떠한 '문자'가 와도 상관없음, 빈문자는 불가능 예를 들어 조건이 '_AA%' 인 경우 'BAA34', 'AAA'는 가능하지만 'AA..

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