채소의 코딩세상

문제는 다음의 링크에서 확인하자. https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 이 문제를 해결하기 위해 다음과 같은 아이디어를 생각해보았다. 일반적으로 그래프에서 모든 간선의 비용이 동일할 때는 BFS를 이용하여 최단 거리를 찾을 수 있다. 다시 말해 이 문제는 '모든 도로의 거리는 1' 이라는 조건 덕분에 너비 우선 탐색을 이용하여 간단히 해결할 수 있다. 먼저 특정..

문제는 다음의 링크에서 확인하자. https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이 문제를 풀기 위해 다음과 같은 아이디어를 생각해보았다. 전체 치킨 집의 수에서 M개를 선택하는 것은 조합의 개념이므로 조합을 사용하기로 했다. 그렇게 치킨집을 선택할 수 있는 모든 경우를 구한 후, 각 경우에 따른 모든 집과 해당 치킨집 까지의 거리의 합을 구해 그 중 최솟값을 답으로 출력하도록 코드를 짜보았다. # 치킨 배달 from i..

이 문제는 2020 카카오 신입 공채 코딩테스트에 출제되었던 문제이다. 아래의 링크를 참고하자. https://school.programmers.co.kr/learn/courses/30/lessons/60061?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 전형적인 시뮬레이션 문제이다. 문제에서 제시한 구체적인 처리 과정을 프로그램 상에서 차례대로 수행하여 결과를 도출하면 된다. 이 문제의 전체 명령의 개수는 1,000개이하이며 제한 시간은 5초로 넉넉한 편이다. 따라서 O(M^3)의 시간복잡도 알고리즘을 사용해도..

문제 A, B 두 사람이 볼링을 치고 있습니다. 두 사람은 서로 무게가 다른 볼링공을 고르려고 합니다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여됩니다. 또한 같은 무게의 공이 여러개 있을 수 있지만, 서로 다른 공으로 간주합니다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재합니다. 예를 들어 N이 5이고, M이 3이며 각각의 무게가 차례대로 1, 3, 2, 3, 2일때 각 공의 번호가 차례대로 1번부터 5번까지 부여됩니다. 이때 두 사람이 고를 수 있는 볼링공 번호의 조합을 구하면 다음과 같습니다. (1번, 2번), (1번, 3번), (1번, 4번), (1번, 5번), (2번, 3번), (2번, 5번), (3번, 4번), (4번, 5번) 결과..

문제 동네 편의점의 주인인 동빈이는 N개의 동전을 가지고 있습니다. 이때 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하세요. 예를 들어, N = 5 이고, 각 동전이 각각 3원, 2원, 1원, 1원, 9원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 8원입니다. 또 다른 예시로, N = 3 이고, 각 동전이 각각 3원, 5원, 7원짜리(화폐 단위) 동전이라고 가정합시다. 이때 동빈이가 만들 수 없는 양의 정수 금액 중 최솟값은 1원입니다. 입력 조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어집니다. (1 return 1 2. if 리스트의 최댓값 리스트의 2번째 ..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 이 문제 풀이의 핵심은 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 경우를 찾는 것이다. 그렇다면 어떻게 해야 뒤집어야 하는 0그룹의 개수와 1그룹의 개수를 구할 수 있을까? 필자는 이렇게 생각했다. 예시를 들어 생각해보자. 입력으로 '001101' 이 주어졌다고 치자. 입력값을 리스트에 넣고 리스트의 원소를 차례대로 이웃하는 원소와 비교를해서 값이 같다면 넘어..

원소가 n개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다. {6, 2, 5, 1, 7, 4, 8, 3} 이라는 배열이 있을 경우, LIS는 {2, 5, 8, 7} 이고, 길이는 4 {2, 5}, {2, 7} 등 증가하는 부분 수열은 많지만 그 중에서 가장 긴 것은 {2, 5, 8, 7} {10, 20, 10, 30, 20, 50} 이라는 배열이 있을 경우, LIS는 {10, 20, 30, 50} 이고, 길이는 4 D[i] = arr[i]를 마지막 원소로 가지는 부분 수열의 최대길이 라고 정의할 때, 가장 긴 증가하는 부분 수열을 계산하는 점화식을 작성해보면, 다음과 같다. (DP 테이블..

문제 N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 값이 x인 원소가 하나도 없다면 -1을 출력합니다. (단, 이 문제는 시간 복잡도 O(logN)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.) 입력 조건 첫째 줄에 N (0

문제 정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다. 1) X가 5로 나누어떨어지면, 5로 나눈다. 2) X가 3으로 나누어 떨어지면, 3으로 나눈다. 3) X가 2로 나누어 떨어지면, 2로 나눈다. 4) X에서 1을 뺀다. 정수 X가 주어졌을때, 연산 4개를 적절히 사용해서 1을 만들어야한다. 이 연산을 사용하는 횟수의 최솟값을 출력해라. 입력 조건 첫째 줄에 정수 X가 주어진다. (1

다이나믹 프로그래밍 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 어떤 문제에서는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법으로 동적 계획법이라고 표현하기도 한다. 피보나치 수열 다이나믹 프로그래밍의 대표적인 예시인 피보나치 수열을 보자. 피보나치 수열은 이전 두항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열은 다음과 같은 형태로 끝없이 이어진다. 이를 점화식으로 나타냈을 때 알 수 있는 특징은 다음과 같다. f(n) = f(n - 1) + f(n..