https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 문제 설명 이번 문제는 사전에 a와 z로만 이루어진 문자열들이 알파벳 순서대로 수록되어 있다. 이 때 n과 m이 주어졌을 때, 자신의 사전에 k번째 문자열을 출력하는 것이다. 예를 들어 n=2, m=2 이면 a가 2개, z가 2개 이고 2번째 문자열이므로 azaz이다. 문제에 대한 아이디어 문자열의 순서를 찾으라는 것에서 순열이 생각났다. 예시 처럼 a a z z가 주어졌을 때, 고등학교 때 배운 4! / ..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 설명 문제가 길지만 간단하게 설명하자면 예제 입력에 있는 5 * 5 이차원 배열에서 1열에서 5열까지 파이프를 연결해야 한다. 그 때 X에는 연결 할 수 없고 한 곳에는 하나의 파이프만 지나갈 수 있다. 그리고 파이프를 설치할 수 있는 곳은 현재를 기준으로 오른쪽 위, 오른쪽, 오른쪽 아래 이렇게 3개이다. 이 때 파이프를 설치할 수 있는 최대 개수를 구하는 프로그램이다. 예제를 직접 풀어보면 이렇게 2개 ..

코딩테스트에서 나오는 문제 중 하나인 LCS 구하기에 대해 공부해 보았다. 이 글의 내용은 Do it! 알고리즘 코딩테스트를 참고하였다. 최소 공통 조상이란? 트리 그래프에서 임의의 두 노드를 선택했을 때, 두 노드가 각각 자신을 포함해 거슬러 올라고면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 '최소 공통 조상' LCA(Lowest common ancestor) 이라고 한다. 최소 공통조상을 구하는 방법은 2가지가 있다. 일반적으로 구하는 방법과 빠르게 구하는 방법이다. 일반적으로 구하는 방법은 Depth를 하나씩 거슬러 올라가야 해서 모든 Depth를 탐색해야 할 수 도있다. 그래서 시간 복잡도가 크다. 하지만 빠르게 구하는 방법은 2의 K승 씩 올라가서 비교하면서 빠르게 구할 ..

https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 설명 결론은 가로선을 추가해 세로선의 결과가 자신의 번호가 나오게 해야 한다는 것이다. 그때 추가한 가로선의 개수를 출력하는 문제이다. 단 추가할 수 있는 가로선은 최대 3개이다. 문제에 대한 아이디어 및 구 이렇게 어떤 것을 추가하고 빼는 문제들은 브루트 포스를 사용해서 모든 경우를 검사해 보는 경우가 많다. 그래서 나도 이 문제를 풀 때 2차원 배열로 사다리를 만들고 하나씩 추가해 가면..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제설명 총합 classic {500, index = 0} {150, index = 2 } {800, index =3} 1450 pop {600, index = 1} {2500, index =4} 3100 pop이 더 인기가 많았으므로 pop부터 실린다. 단, 실행한 곡이 많은 순으로 실려야 하므로 4, 1 순서이다. 그 다음 classic은 순서가 3, 0, 2이지만 2곡만 실려야한다 했으므로 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제설명 5 1 3 5 10 7 4 9 2 8 중 부분합으로 15 이상인 수열 중 가장 길이가 짧은 것을 찾는 것이다. {5, 10} {10, 7}이 제일 짧다. 문제에 대한 아이디어 부분합과 수열의 길이를 구하라는 것에서 투 포인터를 써야겠다고 생각했다. 제일 처음 시작 할 때, First = 0, Second = 0; sum =0; count =0;이다. 1. sum < s 이면..