코딩테스트 공부

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 설명 판다는 무조건 현재 보다 대나무가 많은 지점으로 이동해야 한다. 판다는 최대한 많은 칸을 방문해야 한다. 문제에 대한 아이디어 제일 처음 든 생각은 DFS를 이용해 모든 지점을 탐사하면서 제일 많이 움직인 count를 구하자 였다. 움직일 때 무조건 현재 보다 대나무가 많은 지점을 선택하면서 움직였다. 모든 지점을 탐색할려고 하니깐 시간 초과가 나왔다. 그래서 무슨 조건이 더..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 설명 문제에 나와있는데로 외판원 순회 문제는 유명한 문제라고 한다. 하지만 나는 처음 공부해본다 ㅜㅜ 문제는 간단했는데 외판원이 모든 돌 때, 처음 도시로 다시 돌아와야 한다. 이 때 제일 적은 비용을 들이는 여행 계획을 찾는 것이다. 문제를 푸는 아이디어 이 문제는 다이나믹 프로그래밍으로 풀어야한다. 거의 모든 곳을 돌면서 최소의 값을 찾아 더해야 한다..

https://school.programmers.co.kr/learn/courses/30/lessons/62284 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 우유와 요거트가 담긴 장바구니 SELECT distinct a.cart_id from (select cart_id, name from cart_products where name = 'Milk') as a join cart_products as b on a.cart_id = b.cart_id where b.name = "Yogurt" order by id asc Milk와 Yogurt가 같이 있는..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 설명 2차원 배열을 알려 주면 칸에 숫자가 1인 제일큰 정사각형의 넓이를 찾으면 된다. 문제에 대한 이이디어 이런 문제들은 점화식을 잘 찾아서 사용해야 한다. 그래서 더 어려운 것 같다. 정사각형의 넓이를 찾아라를 쉽게 말하면 정사각형이 될 수 있는 한 변의 최대 길이를 찾아라 라고 할 수 있다. 어떻게 정사각형의 한 변의 길이를 찾을 수 있을까? 정사각형의 조건은 가로 세로의 길이가 같고 또 모든 인접한 면이 1이어야 한다. 지금 자신이 1이라면 왼쪽 대각선 ..

순열 순열은 영어로 Permutation 이라고 한다. nPr : n개 중에서 r개를 뽑아서 나열하는 경우의 수 이다. {1, 2, 3}을 순열로 나타낼 때, 2 1 3 과 1 2 3 은 다른 표현이다. 조합 조합은 영어로 Combitation 이라고 한다. nCr : n개 중에서 순서에 상관없이 r개를 뽑는 경우의 수이다. 즉 { 1 ,2 , 3} 에서 2개를 뽑을 때, {1, 2} 와 {2, 1}은 하나라고 친다. 그러므로 경우의 수는 {1, 2 }, {1, 3}, {2, 3} 3개 이다. 순열과 조합 구현해보기 순열 구현해보기 순열은 재귀를 사용해 간단하게 구현할 수 있다. visited 배열을 사용하여 방문한것은 true로 한다. output 배열을 하나 만들어 depth에 따라 현재 방문한 숫자..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 설명 2개의 문자열이 주어지면 2개의 문자열에 모두 포함 된 부분문자열 중 가장 긴 것의 길이를 출력하는 것이다. ABRACADABRA와 ECADADABRBCRDARA의 공통 부분 문자열은 CA, CADA, ADABR이 존재한다. 이 중 제일 긴 문자열의 길이는 5이기 때문에 답은 5이다. 문제에 대한 아이디어 공통의 부분 문자열을 찾는 알고리즘이다. 이 알고리즘 가장 유명한 것은..

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