아라찌

문제 땅따먹기 점수판 array가 주어짐 방향을 열 방향으로 한칸씩 내려가며 점수를 획득하여 점수 최댓값을 구하는 문제인데 같은 열 방향을 연속으로 밟을 수 없는 규칙이 있음 .+ 열의 갯수는 4개 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 제한사항 행의 개수 N : 100,000 이하의 자연수 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다. 점수 : 100 이하의 자연수 입출력 예 land answer [[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16 풀이 [시간초과] dfs로 풀어야 하지 않을까 란 생각을 했다. 범위가 크니깐..? [성공] dp로 도전.. (2차원 배열을 만들어서) dp[i] = dp[i..

문제 ()() 같은 문자열을 받아서 괄호가 잘 닫혀진 문자열이면 true, 아니면 false를 return 하는 문제 제한사항 문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다. 입출력 예 s answer ()() true (())() true )()( false (()( false 풀이 괄호문제라 stack을 사용해서 (를 받으면 push )를 받았을때 stack이 비었으면 문제있는거라 false stack이 비어있지 않았을 때 pop한게 ( 이면 넘어가는식으로 구현 코드

문제 자연수 n이 주어짐 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다. 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다. n보다 큰 수이긴 한데 n을 2진수로 변환했을 때의 1의 갯수가 같은 수들 중의 최솟값을 구하는 문제. 풀이 n의 2진수 1의 갯수를 target으로 잡아서 n을 1씩 늘려보면서 target이랑 같아질 때 까지 while문을 돌렸다.. 단순하게 생각한 문제라 시간초과가 날꺼라 생각을 했는데 통과했다. 분명 더 좋은 방법이 있을꺼라 생각하는데.. 크흠.. 코드 더 좋았던 풀이 나는 이진수를 String으로 변환 후에 1을 하나하나 count해서 구해줬는데 ..

문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 1+3 (3+1) 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 1 복사 3 4 7 10예제 출력 1 복사 4 8 14풀이방법 dfs DP 처음..

문제 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다. 도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때(중복 가능) 가능한지 여부를 판별하는 프로그램을 작성하시오. 입력 첫 줄에 도시의 수 N이 주어진다. N은 200이하이다. ..

안녕하세용 오랫만의 포스팅이에요.. 요즘 알고리즘 문제도 풀고.. 프로젝트랑 최근에 수술도 해서.. 정신없이 지냈어요..(잘 끝났어요 ^_^) 마무튼간 오늘의 포스팅. 바로 DP(다이나믹 프로그래밍) 의 문제를 여러 문제 풀면서 느낀 꿀팁과 함께 문제풀이를 작성해볼까 합니다. 꿀팁1: 규칙을 찾아라!! 직접 0부터 한 3까지..? 그려봐서 규칙을 찾아 보자(점화식) 그럼 문제 들어갑니다.. 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 예) n == 5일 경우 바로 꿀팁을 적용해 보죠.. 우선 n == 0일 때: 당연히 0개죠?? -> 0 n == 1일 때: 2*1의 틀에서 하나밖에 안들어가죠?? -> 1 n == 2일 때: 2*2의 틀에서 총 2..