알고리즘

다이나믹 프로그래밍

다이나믹 프로그래밍

그러므로 다음과 같은 수도 된다.N이 2인 경우 00, 01도 되는 것이다.해당 문제는 그림을 그리며 오르막 수가 될 수 있는 경우의 수를 나눠봤다.그리고 dp배열은 아래와 같이 정의를 했다.N이 1인 경우는 1자리의 수이다.위 사진의 첫번째 N이 1이고 0으로 시작하

해당 문제는 2n크기의 직사각형을 12, 2\*1 타일로 채우는 방법의 수를 구하는 것이다.Bottom-Up 방식으로 점화식을 설계 해보고자 했다.우선 dp배열에 대해서는 아래와 같이 설정을 했다.그래서 아이패드에 타일을 하나씩 그리며 채워보고 있었다.그러면서 점화식을

알고리즘

가장 긴 증가하는 부분 수열 이 문제는 가장 길게 증가하는 부분 수열을 구하는 것이다. A = {10, 20, 10, 30, 20, 50}인 경우 A 배열중 10, 20, 30, 50이 가장 긴 부분 수열이고 길이가 4이다. 여기서 나는 dp[5]가 4가 나오도록 설계를 해야겠다 생각했다. 그러면서 dp는 다음과 같이 설정을 했다. 즉, 위와 같이 ...

입출력의 예그래서 나도 위와 같이 단계별로 나눠서 코딩을 했다.여기서 중요한 포인트는 최신화라 생각을 했다.항상 기준 부분 문자열이 변경되고, 동일한 부분 문자열의 개수를 세줘야 하는 것이 가장 키포인트였다.기준 부분 문자열이 변경되는 경우와 부분 문자열의 개수가 변경

이 문제는 Key를 Lock에 딱 맞게 연결하면 되는 문제이다.Key를 연결하기 위해 90도 회전할 수 있고, 이동도 할 수 있다.그래서 완전탐색을 하기 위해 아래와 같이 알고리즘을 세웠다.그래서 처음에 나온 코드는 아래와 같다.위 코드는 잘못됐다.이유는 항상 이 코드

뱀의 이동 로직1\. 뱀이 이동하는 곳에 사과가 있다면, 사과가 사라지고 뱀의 꼬리는 그 자리에 있고 몸만 이동한다.2\. 뱀이 이동하는 곳에 사과가 없다면, 뱀의 머리와 꼬리가 함께 이동한다.뱀이 움직임을 멈추는 조건1\. 뱀의 머리가 벽을 뚫는 경우2\. 뱀의 머리

여기서 내가 가져간 방식은 제거하는 명령어가 온다면 제거를 한다. 그 다음 올바른 구조물인지 체크를 한다.또 설치하는 명령어가 온다면 설치를 한다. 그 다음 올바른 구조물인지 체크를 한다.즉, 우선 설치하거나 삭제하고 올바른지 체크를 하는 것이다.그런데 설치 or 제거

그러다면 5개의 치킨집에서 3개의 치킨집을 고르는 경우의 수를 먼저 생각해야했다.5C3은 5개의 치킨집중 순서와 상관없이 모든 경우의 수를 나타낸다.5P3은 순서를 고려하기 때문에 사용하면 안된다.그래서 경우의 수는 13Cm이 될 수 있다. 여기서 13인 이유는 M은

이 문제는 2020 카카오 신입 공채에서 나온 문제이다.N은 전체 외벽의 개수, weak는 문제가 있는 외벽의 좌표, dist는 각 친구들이 이동할 수 있는 거리를 나타낸다. 제한 조건을 보았을 때, weak과 dist 리스트의 길이가 매우 짧은 것을 볼 수 있다.이

특정 거리의 도시 찾기 N개의 도시들이 있고, M개의 도로 개수가 있고, 출발 도시인 X에서, 최단거리가 K만큼 떨어진 도시를 찾으면 된다. 각 도시들의 거리는 1이다. 문제 조건을 보면 N은 300000개, 도로 개수는 1000000개이다. 시간 복잡도는 O(N+M)으로 동작하기 때문에 시간 초과 없이 해결이 가능하다. 이 문제는 BFS를 이용하여 해...

나는 큐에 바이러스의 정보, 초, X좌표, Y좌표를 담아서 넣었다.그런 다음 네방향 로직을 통해서 문제를 해결했다.내 코드는 아래와 같다.

괄호 변환 이 문제는 2020 카카오 신입 공채에서 나온 문제이다. 알고리즘을 설계를 따로 할 필요가 없다. 문제에서 알고리즘을 알려줬고, 그대로 구현을 하면 되는 문제이다. 그래서 차근차근 주어진 대로 구현을 하면 되는 문제이다. 코드를 보면서 주어진 문제에 대해서 어떻게 진행을 했는지 참고하면 좋을 것 같다.

연산자 끼워넣기 이 문제는 숫자 사이에 연산자를 끼워넣어서 최대값과 최솟값을 출력하는 문제이다. 즉 모든 경우의 수에 대해서 확인을 해야한다. 그래서 dfs를 통해서 완전 탐색을 하였다. 즉 +, -, *, /에 대해서 모든 경우의 수에 대해서 진행을 했다. 입력으로 숫자의 개수 N이 주어지고, 숫자를 입력하게 한다. 그런 다음 연산의 사용 가능 개수들...

이 문제는 학생들이 선생님에게 걸리지 않게 벽을 잘 설치하는 것이다.벽은 3개 설치할 수 있는데, 걸리지 않는 경우가 있다면 YES를 출력하면 된다.선생님이 학생을 발견하는 경우는 선생님의 위치는 그대로 있고 상, 하, 좌, 우 방향으로 쭉 볼 수 있다.우선 벽을 설치

이 문제는 단순 4방향 문제이고, 인구 이동을 못할 때까지 반복문을 돌려서 체크하면 된다.4방향 이동 조건은 L이상, R이하인 경우이다.우선 매번 탐색을 하기 전에 초기화 해주는 작업이 중요했다.연합을 하는 나라는 모두 이동이 되고 난 뒤, 최신화가 되어야 한다.그런

떡볶이 떡 만들기 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기의 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의...

N과 M(1) 입력 첫째 줄에 자연수 N과 M이 주어진다. N과 M은 1이상 8이하 출력 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다. 중복되는 수열은 여러번 출력하면 안되고, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 해결방법 이 문제는 2가지의 방법으로 풀 수 있다. ...

공유기 설치 입력조건 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. 출력 조건 첫째 줄에 가장 인접한 두 공유기 사이의 최대 ...

정렬된 배열에서 특정 수의 개수 구하기 문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 [1, 1, 2, 2, 2, 2, 3]이 있을 때 x=2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다. 단, 이 문제는 시간 복잡도 O(logN)으로 알고리...

나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다...

금광 문제 n x m 크기의 금광이 있습니다. 금광은 1 x 1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어 있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m - 1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이...

시소 짝꿍 문제 설명 어느 공원 놀이터에는 시소가 하나 설치되어 있습니다. 이 시소는 중심으로부터 2(m), 3(m), 4(m) 거리의 지점에 좌석이 하나씩 있습니다. 이 시소를 두 명이 마주 보고 탄다고 할 때, 시소가 평형인 상태에서 각각에 의해 시소에 걸리는 토

개인정보 수집 유효기간 문제 설명 고객의 약관 동의를 얻어서 수집된 1~n번으로 분류되는 개인정보 n개가 있습니다. 약관 종류는 여러 가지 있으며 각 약관마다 개인정보 보관 유효기간이 정해져 있습니다. 당신은 각 개인정보가 어떤 약관으로 수집됐는지 알고 있습니다. 수집된 개인정보는 유효기간 전까지만 보관 가능하며, 유효기간이 지났다면 반드시 파기해야 합니...

다익스트라 알고리즘 설명 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 입니다. 다익스트라 알고리즘은 그리디 알고리즘으로 분류가 됩니다. 그 이유는 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문입니다. 원리 출발 노드를 설정...

플로이드 워셜 알고리즘 설명 다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우였다. 하지만 플로이드 워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 알고리즘이다. 다익스트라 알고리즘은 출발 노드가 1개이고 다른 모든 노드들의 거리를 저장하기엔 1차원 리스트를 사용했...

뒤에 있는 큰 수 찾기 문제 설명 정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다. 정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요...

마법의 엘리베이터 문제 설명 마법의 세계에 사는 민수는 아주 높은 탑에 살고 있습니다. 탑이 너무 높아서 걸어 다니기 힘든 민수는 마법의 엘리베이터를 만들었습니다. 마법의 엘리베이터의 버튼은 특별합니다. 마법의 엘리베이터에는 -1, +1, -10, +10, -100, +100 등과 같이 절댓값이 10c (c ≥ 0 인 정수) 형태인 정수들이 적힌 버튼이 ...

점 찍기 문제설명 좌표평면을 좋아하는 진수는 x축과 y축이 직교하는 2차원 좌표평면에 점을 찍으면서 놀고 있습니다. 진수는 두 양의 정수 k, d가 주어질 때 다음과 같이 점을 찍으려 합니다. 원점(0, 0)으로부터 x축 방향으로 ak(a = 0, 1, 2, 3 ...), y축 방향으로 bk(b = 0, 1, 2, 3 ...)만큼 떨어진 위치에 점을 찍...