본문 바로가기

전체 글

 (346)
[백준] 6603. 로또 풀이 / Python, JavaScript 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 6603. 로또 접근한 방법 (1)조합과 (2)DFS를 사용하는 두 가지 방법이 있는데, 범위가 적으므로 Python을 쓰는 경우라면 조합 알고리즘으로 풀어내는게 더 빠르고 효율적입니다. 주어지는 수 들중 6개를 뽑는 경우들을 모두 구하는 것이므로 중복이 없는 조합을 구해야 합니다. 파이썬은 조합 라이브러리가 있지만 자바스크립트는 직접 구현해주어야 하므로 DFS로 풀어내는게 더 유리할 겁니다. DFS를 사용할 경우 스택에 값을 하나씩 넣습니다. 오름차..
[백준] 1748. 수 이어쓰기 풀이 / Python 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 1748. 수 이어쓰기 1 접근한 방법 단순한 유형의 브루트포스 문제입니다. 수의 범위를 보면 최대 1억번입니다. 적당한 시간이 주어진다면 일반적으로 O(n)복잡도로 해결 가능한 범위이지만 이 문제의 경우 제한 시간이 매우 타이트하므로 n번 이내로 해결해야 합니다. 수학적으로 접근합니다. 규칙을 자세히 찾아보면 굳이 일일이 자릿수를 더해줄 필요가 없습니다. 어떤 수의 각 자릿수마다 나올 수 있는 최대 길이는 정해져있습니다. 예를 들면 1개 자리는 1 ~ 9이므로 9번 * 1, 2개 자리는 10~99이므로 90번 * 2, 3개 자리는 100~999이므로 900번 * 3 ... 그러면 ..
[백준] 2133. 타일 채우기 풀이 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2133. 타일 채우기 이 문제는 개인적으로 패턴을 찾아내기까지 시간이 매우 오래걸렸습니다. 6칸짜리 타일까지 일부 만들어보던 중 4칸부터 모든 칸에 2개씩의 족보없는 타일이 들어간다는 것을 알게된 후부터 어느정도 파악하게 되었습니다. 접근한 방법 일단 홀수 칸들은 어떻게 생각해봐도 만들어질 수가 없으니 제외했고, 머리가 좋지않은 저는 일단 4칸까지는 그냥 그려봤습니다. 그려봤을 때 2칸에서 만들어진 3가지 패턴이 이후 패턴에서도 사용되는 것을 볼 수 있었죠. 즉 4칸에서 2칸을 채우는 용도로 보자면 3개의 패턴이 3번씩 채워지는 것을 볼 수 있습니다. 그러면 9가지가 만..
[백준] 11054. 가장 긴 바이토닉 부분 수열 풀이 / Python, JavaScript 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 접근한 방법 가장 쉽게 푸는 방법은 가장 긴 증가하는 부분 수열을 구하는 알고리즘을 주어진 수열의 정방향과 역방향으로 적용해주면 해결 가능합니다. 주어진 예제를 봅시다. 1 5 2 1 4 3 4 5 2 1 위 수열에서 정방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을 때 결과는 아래와 같습니다. 가장 긴 수열이 어떤 부분 수열인지는 상관없습니다. [1, 2, 2, 1, 3, 3, 4, 5, 2, 1] 다음으로 역방향으로 가장 긴 증가하는 부분 수열을 DP 테이블에 담았을..
[프로그래머스] 리코쳇 로봇 풀이 / Python, JavaScript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Lv2. 리코쳇 로봇 접근한 방법 이런 유형의 최단 거리 문제는 대부분 BFS로 해결되는데 조건이 조금 특이합니다. 한번 이동 시 벽 또는 장애물이 있을 때까지 계속 들어가야 합니다. 벽이나 장애물을 만나면 그 이전 칸에서 멈춰야 하므로 이 부분에서 이동했던 한칸을 다시 되돌려줘야 합니다. 큐와 방문여부를 담은 배열을 만들어 BFS로 해결합니다. Python은 덱 라이브러리를 사용하면 되고 JavaScript에서는 별도의 라이브러리가 없어 배열로 풀이합니다. 큐에서 row, column 정보를 담은 원소를 꺼..
[백준] 1149. RGB거리 풀이 / Python, JavaScript 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 1149. RGB거리 무작정 1행부터 이전 색깔을 제외하고 가장 작은 값들만 찾아 더해가면 일부 케이스에서 틀리게 됩니다. 각 행마다 나올 수 있는 비용은 총 3가지 이기 때문에 매번 3가지 경우의 비용을 모두 계산해주어야 합니다. 매 행에 들어있는 값을 빨강(R), 초록(G), 파랑(B)이라고 할 때 각 열의 누적 비용은 다음과 같습니다. 현재 행의 R의 누적 비용 = 현재 행의 R의 비용 + 이전 행의 B의 누적 비용과 G의 누적 비용중..
[백준] 1912. 연속합 풀이 / Python, JavaScript 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1912. 연속합 풀이 문제해결 아이디어는 다음과 같습니다. 1. 주어진 수열의 값들을 하나씩 순회한다. 2. 순회하는 값들을 현재값으로 축적한다. 3. 현재값이 증가할 경우 현재까지의 최댓값을 갱신한다. 4. 현재까지의 최댓값보다 더 큰 값이 발견되면 그 값을 현재값과 최댓값으로 새로 갱신한다. 처음 풀이 시 DP를 사용하지는 않았지만 문제 유형이 DP이므로 DP를 이용한 풀이방식도 함께 올립니다. 접근 방식은 동일하며 DP를 사용했을 때 코드가 더 간결하고 속도가 미세..
[백준] 14002. 가장 긴 증가하는 부분 수열4 풀이 / Python, JavaScript 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 14002. 가장 긴 증가하는 부분 수열4 부분 수열 1 문제와 동일한 문제이지만 여기서는 길이 뿐만 아니라 구성되는 수열을 출력해야 합니다. 가장 긴 증가하는 부분 수열 1문제에 대한 풀이는 아래에 남겨놓았습니다. [백준] 11053. 가장 긴 증가하는 부분 수열 풀이 / Python, JavaScript 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴..

티스토리툴바