소마 구현쪽에 투포인터 나왔다는 소리가 있어 어제 하루종일 투포인터 공부하느라 게시글을 못올렸습니다 ㅜㅜ...하지만 큰 수확이 있었으니...바로 골드4 투포인터 문제를 자력솔 했습니다!1806번 - 부분합수열이 주어지면 S보다 크거나 같은 부분수열의 합 중에서 가장 크

프로그래머스 - 가장 먼 노드DFS로 풀다가 한참 해맸습니다... 심지어 예전에 유사문제 한번 풀어봤던 것 같은데...어쨋든 이 문제의 쟁점은 BFS로 level(depth)를 구할 수 있는가 없는가 입니다.그림과 같이 노드의 간선이 2개 이상인 경우에는 DFS로 노드

프로그래머스 - 바탕화면 정리하기소마 테스트가 프로그래머스에서 진행된다길래 맛 좀 보려고 놀러왔습니다. 어려울 것 없는 간단한 리스트 활용 문제입니다.wallpaper에서 deque 하나 import 하고 시작하겠습니다. popleft를 통해 개별 원소마다 접근하고위에

18353번 - 병사 배치하기 가장 긴 오름차순 수열 문제에서 한번 꼰 문제입니다. 분석을 할 수 있으면 어렵지 않게 풀 수 있습니다.위 수열에서는 2,5,3,2,15 라는 체크해둔 수열을 제외하면 병사의 수가 최대가 되도록 할 수 있습니다. 그런데 체크해 둔 수열을

11048번 - 이동하기미로가 주어지고 각 미로의 칸에 사탕이 놓여있다고 가정할 때, 리스트 (0,0) 에서 (N,M)까지 가는데 주울 수 있는 사탕의 최댓값을 구하는 문제입니다. 언뜻 보면 BFS류라고 생각할 수 있으나 DP로 해결 가능합니다. 어제 저는 14494번

14494번 - 다이나믹이 뭐에요?이차원 배열이 주어질 때 시작점에서 끝점까지 가는데의 최단 경로의 수를 구하는 문제입니다. 문제에서 구체적으로 명시하지는 않았는데, 최단 경로가 맞습니다. 먼저 최단 경로는 이러한 식으로 생겼습니다. 문제에서 친절히 맨 위에서 아래,오

2156번 - 포도주 시식연속으로 3개를 고르면 안되고 마실수 있는 최대 포도주를 구하는 문제입니다.전에 풀었던 계단 문제와 비슷한 감이 없잖아 있는데 조금 더 복잡합니다. 본 문제는 세 가지 경우로 나눠서 풀 수 있습니다. 1\. i번째 잔을 아예 고르지 않거나2\.

17216번 - 가장 큰 감소 부분 수열가장 큰 감소하는 부분 수열의 합을 구하는 문제입니다. 합의 최소는 자기 자신이므로 dp값은 기존 리스트 인덱스와 똑같이 초기화해줍니다. 각 인덱스마다 순회를 돌며 자기 자신보다 큰 인덱스가 존재하면 자기 자신의 dp값과 자기자신

11055번 - 가장 큰 증가하는 부분수열가장 큰 증가하는 부분수열을 구하는 문제입니다. 이전에 풀었던 가장 긴 증가하는 부분수열을 응용한 문제라고 보시면 될 것 같습니다. 먼저 dp를 list와 똑같이 초기화해줍니다. 왜냐하면 현재 문제에서 제일 작게 나올 수 있는

1463번 - 1로 만들기 세 가지 연산을 사용해서 주어진 수를 최대한 적게 연산하여 1로 만들때, 연산의 횟수를 구하는 문제입니다. 분석

10844 - 쉬운 계단 수쉽지않은 문제였습니다. 일단 위와같이 각 자릿수의 차이가 1인 수를 게단수라고 할 때, 자릿수가 주어지면 해당 자릿수에서 가능한 계단 수의 경우의 수의 합을 출력하면 되는 문제입니다. 이 문제가 어려운 이유로는 두 가지가 있습니다. 일단 첫번

9184번 - 신나는 함수 실행문제에 주어진 코드를 실행시키려고 하는데 문제에서 해당 코드를 실행시키면 시간이 너무 오래걸릴까봐 걱정이랍니다. 해당 코드를 시간초과가 나지 않게 실행시키는 코드를 작성하면 됩니다....보자마자 짐작이 갑니다. DP의 메모이제이션 기법을

안될 가능성이 높으나 15기 소프트웨어 마에스트로에 지원했습니다. 뭐든 도전해보는게 중요하니까요.따라서 하던 DP 잠시 미뤄두고 소마 기출 푸는거에 집중하려 합니다. 기출에 DP도 포함되어 있으니 겸사겸사 공부하겠습니다. 1012 - 유기농 배추BFS로 1이 뭉쳐있는

11053번 - 가장 긴 증가하는 부분 수열 (LIS)가장 긴 증가하는 부분 수열을 탐색하는 문제입니다. 이 문제는 이분 탐색과 DP 두 가지 방법으로 풀이할 수 있으나 저는 DP 연습중이므로 DP로 풀겠습니다. DP로 풀이하는 방법은 다음과 같습니다. 위와 같이 생긴

15686번 - 치킨 배달

11726번 - 2\*N 타일링이런 문제입니다. 2xn이라는 총 공간이 주어졌을 때 1x2타일과 2x1타일을 이용해서 이 공간을 채울 수 있는 경우의 수를 구하면 되는 문제입니다. 이런 경우 두 가지 유형으로 나눌 수 있는데먼저 타일이 1x2타일로 끝나는 경우 와 타일

9095번 - 1,2,3 더하기DP문제인데 그냥 재귀로 풀어버렸습니다 하하...입력받을 횟수를 받고변수를 받아 재귀를 돌려줍니다. 만약 start변수가 end와 같아지거나 더 커진다면 cnt를 하나 올리고 함수를 종료합니다. 1,2,3을 사용하여 해당 숫자를 어떻게 만

그동안 BFS와 DFS 골드 문제들을 풀어보면서 알고리즘이 어떤 건지, 어떻게 활용하여 해결 할 수 있는지 감을 잡아갔습니다. 약 47일간 DFS와 BFS를 해결했으므로 하나만 계속해서 힘든 것도 있고 보다 다양한 알고리즘을 접하고자 오늘부터는 DP 알고리즘에 손대보려

13265번 - 색칠하기트리가 하나 주어졌을 때 이 트리를 두 가지 색으로 색칠할 수 있는지 묻는 문제입니다. 다만, 이어진 노드끼리는 같은 색을 띨 수 없습니다. 일단 단순히 구현 문제라고 생각하고 노드를 모두 이진 트리로써 취급하여 생각해보기로 했습니다. 레벨 1에

2660 - 회장뽑기트리가 하나 주어지면 노드 하나를 잡고 이 노드를 회원이라고 합시다. 이 회원과 이어진 노드는 회원의 친구이고, 회원과 이어진 노드의 이어진 노드는 회원의 친구의 친구입니다. 회원이 모두와 친구라면 (해당 노드가 모든 노드와 직접적으로 이어져있다면)