5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 5014. 스타트링크 접근한 방법 단순 조건 분할과 반복문으로 풀이합니다. 1. 현재 s값을 기준으로 목표층(target)보다 적을 때, - 위층을 더한 것이 전체층 이내라면 위층으로 간다. - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. 2. 현재 s값을 기준으로 목표층보다 클 때, - 아래층을 뺀 것이 전체층 이내라면 아래층으로 간다. - 위층을 더한 것이 전체층 이내라면 위층으로 간다. 예를 들면 s가 9, target이 10, u = 2, d = 1 와 같은 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 배열의 값들 중 가장 큰 값을 찾아서 1씩 제거해주어야 합니다. 이중 for문을 쓰면 시간 초과가 발생하므로 힙 구조를 이용해 제거해주면 됩니다. 주어진 works를 맥스 힙으로 구성한 후 n만큼 반복하여 매 순회 시 힙에서 값을 1제거한 후 다시 넣어주는 방식을 사용합니다. 자료를 넣고 빼는 과정은 각각 logn시간이 걸리므로 제한 시간 내에 풀이할 수 있습니다. def solution(n, works): import heapq as hq q = [] for i in works: hq.heapp..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 섬 연결하기 접근한 방법 최소 신장 트리를 찾아낼 수 있는지를 묻는 기본 문제입니다. 프림, 크루스칼 알고리즘 중 선택해서 풀이하면 되고 저는 크루스칼을 이용해서 풀이했습니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 이용해서 간단히 구현할 수 있습니다. 파인드(findP)는 노드의 부모 노드를 찾는 함수이며, 유니온(unionP)은 두 노드 집합의 부모를 연결해주는 함수입니다. 주어진 costs 배열을 비용순으로 정렬해주는 과정이 꼭 필요하고 정렬된 엣지를 순회하면서 싸이클이 없는 경우에만 두 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 이중우선순위큐 접근한 방법 문제에서 우선순위큐를 쓰고 있으므로 우선순위 큐를 사용할 수 있는 heapq 라이브러리를 사용합니다. 두 개의 힙큐(최대힙, 최소힙)를 사용해서 최댓값과 최솟값을 관리하면 됩니다. Insert일 경우에는 두 힙에 모두 값을 넣어주고 최대힙의 경우 음수로 관리하면 구현할 수 있습니다. Delete일 경우 두 힙에서 동일한 값을 모두 빼주어야 하는데 최댓값을 빼는 경우 최소힙에서는 최대힙에서 pop된 값에 음수를 붙여 제거해야 값을 찾을 수 있으며 최솟값을 빼는 경우 최대힙에서..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Lv3. 기지국 설치 접근한 방법 각 자리의 기지국 설치 여부를 배열로 다루게 되면 효율성 테스트에서 탈락됩니다. 굳이 설치여부를 다룰 필요 없이 해당 범위만 건너뛰면서 탐색했습니다. 주어진 stations를 먼저 고려하기 위해 이 어레이를 큐나 스택으로 활용합니다. 오름차순으로 되어있는 김에 큐로 사용하는 것이 낫고 자바스크립트에서는 front 포인터를 두어서 큐 처럼 활용합니다. 현재 위치에 기지국을 설치할지 말지를 결정하는데 그 위치가 미리 설치된 기지국(A)의 범위 안에 들면 탐색할 필요 없이 A의 범..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 가장 먼 노드 접근한 방법 BFS를 이용해서 빠르게 해결할 수 있습니다. 주의할 점은 간선 저장 시 인접 행렬을 사용할 경우 시간이 초과됩니다. 노드 보다 간선이 적을 경우 매우 비효율적이므로 상대적으로 탐색에 더 효율적인 인접 리스트를 사용합니다. 간선을 저장했다면 큐를 이용해서 노드(now)와 간선 길이(cnt)를 관리합니다. JavaScript에서는 별도의 큐 라이브러리가 없으므로 shift 메서드를 사용하고 문제에는 영향이 없지만 비효율적이라 싫다면 front를 가리키는 포인터를 설정하여 큐 ..

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 7576. 토마토 접근한 방법 인접한 토마토부터 확인해야하니 BFS로 접근해야 하지만 익은 토마토가 여러개 분포하는 경우가 문제입니다. 큐를 2개 사용하여 해결했습니다. 우선 주어진 배열에서 익은 토마토를 모두 체크하여 큐1에 넣고 큐2는 빈 큐로 만들어줍니다. BFS로 진입하여 현재 큐1에 들어있는 익은 토마토의 상하좌우를 모두 체크해 큐2에 넣어줍니다. 큐1에 넣지 않는 이유는 무한 루프를 돌지 않기 위해서입니다. 다음번 루프에서는 현재 큐가..

1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1759. 암호 만들기 접근한 방법 주어진 문자들중 L개의 조합을 구하는 문제입니다. 조합 라이브러리와 DFS를 사용하는 방법이 있는데 저는 DFS를 사용했고 파이썬의 경우 조합 라이브러리를 쓰는 것이 속도 측면에서 더 유리합니다. 먼저 문자들을 정렬해놓고 스택을 이용해서 순서대로 값을 넣어줍니다. L개가 완성되면 자음과 모음 개수를 체크해서 자음이 1개, 모음이 2개 이상인 경우에만 출력해주면 답을 구할 수 있습니다. Python 풀이 import sys input..

6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 6603. 로또 접근한 방법 (1)조합과 (2)DFS를 사용하는 두 가지 방법이 있는데, 범위가 적으므로 Python을 쓰는 경우라면 조합 알고리즘으로 풀어내는게 더 빠르고 효율적입니다. 주어지는 수 들중 6개를 뽑는 경우들을 모두 구하는 것이므로 중복이 없는 조합을 구해야 합니다. 파이썬은 조합 라이브러리가 있지만 자바스크립트는 직접 구현해주어야 하므로 DFS로 풀어내는게 더 유리할 겁니다. DFS를 사용할 경우 스택에 값을 하나씩 넣습니다. 오름차..

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번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2133. 타일 채우기 이 문제는 개인적으로 패턴을 찾아내기까지 시간이 매우 오래걸렸습니다. 6칸짜리 타일까지 일부 만들어보던 중 4칸부터 모든 칸에 2개씩의 족보없는 타일이 들어간다는 것을 알게된 후부터 어느정도 파악하게 되었습니다. 접근한 방법 일단 홀수 칸들은 어떻게 생각해봐도 만들어질 수가 없으니 제외했고, 머리가 좋지않은 저는 일단 4칸까지는 그냥 그려봤습니다. 그려봤을 때 2칸에서 만들어진 3가지 패턴이 이후 패턴에서도 사용되는 것을 볼 수 있었죠. 즉 4칸에서 2칸을 채우는 용도로 보자면 3개의 패턴이 3번씩 채워지는 것을 볼 수 있습니다. 그러면 9가지가 만..

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 테이블에 담았을..