본문 바로가기

전체 글

 (346)
[백준] 5014. 스타트링크 풀이 (Python, JavaScript) 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 와 같은 ..
[프로그래머스] lv3. 야근 지수 풀이 (Python) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근한 방법 배열의 값들 중 가장 큰 값을 찾아서 1씩 제거해주어야 합니다. 이중 for문을 쓰면 시간 초과가 발생하므로 힙 구조를 이용해 제거해주면 됩니다. 주어진 works를 맥스 힙으로 구성한 후 n만큼 반복하여 매 순회 시 힙에서 값을 1제거한 후 다시 넣어주는 방식을 사용합니다. 자료를 넣고 빼는 과정은 각각 logn시간이 걸리므로 제한 시간 내에 풀이할 수 있습니다. def solution(n, works): import heapq as hq q = [] for i in works: hq.heapp..
[프로그래머스] lv3. 섬 연결하기 풀이 (Python, JavaScript) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 섬 연결하기 접근한 방법 최소 신장 트리를 찾아낼 수 있는지를 묻는 기본 문제입니다. 프림, 크루스칼 알고리즘 중 선택해서 풀이하면 되고 저는 크루스칼을 이용해서 풀이했습니다. 크루스칼 알고리즘은 유니온 파인드 자료구조를 이용해서 간단히 구현할 수 있습니다. 파인드(findP)는 노드의 부모 노드를 찾는 함수이며, 유니온(unionP)은 두 노드 집합의 부모를 연결해주는 함수입니다. 주어진 costs 배열을 비용순으로 정렬해주는 과정이 꼭 필요하고 정렬된 엣지를 순회하면서 싸이클이 없는 경우에만 두 ..
[프로그래머스] lv3. 이중우선순위큐 풀이 (Python) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 이중우선순위큐 접근한 방법 문제에서 우선순위큐를 쓰고 있으므로 우선순위 큐를 사용할 수 있는 heapq 라이브러리를 사용합니다. 두 개의 힙큐(최대힙, 최소힙)를 사용해서 최댓값과 최솟값을 관리하면 됩니다. Insert일 경우에는 두 힙에 모두 값을 넣어주고 최대힙의 경우 음수로 관리하면 구현할 수 있습니다. Delete일 경우 두 힙에서 동일한 값을 모두 빼주어야 하는데 최댓값을 빼는 경우 최소힙에서는 최대힙에서 pop된 값에 음수를 붙여 제거해야 값을 찾을 수 있으며 최솟값을 빼는 경우 최대힙에서..
[프로그래머스] lv3. 기지국 설치 / Python, JavaScript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Lv3. 기지국 설치 접근한 방법 각 자리의 기지국 설치 여부를 배열로 다루게 되면 효율성 테스트에서 탈락됩니다. 굳이 설치여부를 다룰 필요 없이 해당 범위만 건너뛰면서 탐색했습니다. 주어진 stations를 먼저 고려하기 위해 이 어레이를 큐나 스택으로 활용합니다. 오름차순으로 되어있는 김에 큐로 사용하는 것이 낫고 자바스크립트에서는 front 포인터를 두어서 큐 처럼 활용합니다. 현재 위치에 기지국을 설치할지 말지를 결정하는데 그 위치가 미리 설치된 기지국(A)의 범위 안에 들면 탐색할 필요 없이 A의 범..
[프로그래머스] lv3. 가장 먼 노드풀이 / Python, JavaScript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 가장 먼 노드 접근한 방법 BFS를 이용해서 빠르게 해결할 수 있습니다. 주의할 점은 간선 저장 시 인접 행렬을 사용할 경우 시간이 초과됩니다. 노드 보다 간선이 적을 경우 매우 비효율적이므로 상대적으로 탐색에 더 효율적인 인접 리스트를 사용합니다. 간선을 저장했다면 큐를 이용해서 노드(now)와 간선 길이(cnt)를 관리합니다. JavaScript에서는 별도의 큐 라이브러리가 없으므로 shift 메서드를 사용하고 문제에는 영향이 없지만 비효율적이라 싫다면 front를 가리키는 포인터를 설정하여 큐 ..
[백준] 7576. 토마토 풀이 / Python, JavaScript 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 7576. 토마토 접근한 방법 인접한 토마토부터 확인해야하니 BFS로 접근해야 하지만 익은 토마토가 여러개 분포하는 경우가 문제입니다. 큐를 2개 사용하여 해결했습니다. 우선 주어진 배열에서 익은 토마토를 모두 체크하여 큐1에 넣고 큐2는 빈 큐로 만들어줍니다. BFS로 진입하여 현재 큐1에 들어있는 익은 토마토의 상하좌우를 모두 체크해 큐2에 넣어줍니다. 큐1에 넣지 않는 이유는 무한 루프를 돌지 않기 위해서입니다. 다음번 루프에서는 현재 큐가..
[백준] 1759. 암호 만들기 풀이 / Python, JavaScript 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 1759. 암호 만들기 접근한 방법 주어진 문자들중 L개의 조합을 구하는 문제입니다. 조합 라이브러리와 DFS를 사용하는 방법이 있는데 저는 DFS를 사용했고 파이썬의 경우 조합 라이브러리를 쓰는 것이 속도 측면에서 더 유리합니다. 먼저 문자들을 정렬해놓고 스택을 이용해서 순서대로 값을 넣어줍니다. L개가 완성되면 자음과 모음 개수를 체크해서 자음이 1개, 모음이 2개 이상인 경우에만 출력해주면 답을 구할 수 있습니다. Python 풀이 import sys input..

티스토리툴바