전체 글

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 설명 문제는 간단하다. 수열이 주어지면 가장 긴 증가하는 부분 수열을 찾으면 된다. 예시 처럼 10 20 10 30 20 50이 주어지면 10 20 30 50이 가장 길다. 문제에 대한 아이디어 제일 처음 생각해본 아이디어는 무작정 sort해서 겹치는 것을 빼면 안될까? 라고 생각했지만 이 문제는 2가지의 순서가 존재했다. 현재 수열들 수 자체의 순서와 inde..

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에 따라 현재 방문한 숫자..