본문 바로가기

IT/알고리즘34

[BAEKJOON] 백준 24041: 성싶당 밀키트 (node.js) 문제 링크: https://www.acmicpc.net/problem/24041 24041번: 성싶당 밀키트 첫 번째 줄에 $N, G, K$가 공백으로 구분되어 주어진다. 두 번째 줄부터 $N$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번째 재료에 대한 정보인 부패 속도 $S_i$, 유통기한 $L_i$와 중요한 재료인지를 나타내는 www.acmicpc.net 풀이 시간이 지나며 세균이 증식을 할 때, 제한된 균수 이하로 밀키트를 구매일로 부터 며칠 후 까지 먹을 수 있는 계산하는 문제이다. (무슨 이런..). 조건의 제한을 확인했을 때 부패속도 S1은 최대 10^9이며, 구매 후 최대 10^9까지 먹을 수 있기 때문에, 최대 균 수는 10^9 *2가 될 수 있다. 제한된 균 수를 확인하는 과정에서, 모든 .. 2023. 2. 17.

[JavaScript] Array vs Queue vs Deque Array 이대로 알고리즘에 활용해도 될까? 자바스크립트를 사용한 알고리즘 풀이에서 Queue를 구현하기보다는 Array를 사용하곤 했다. 자바스크립트에서 Array는 기본 배열 메서드(push, pop, unshift, shift)를 통해 Queue를 구현하지 않아도 FIFO로 사용이 가능하기 때문에, 간단히 풀이할 때는 array를 활용하곤 했으나, 시간복잡도 측면에서 좋지 않을 것이라 생각이 들었다. 📌 자료구조의 가장 앞 데이터 삭제하기(Dequeue) 다시 생각해보더라도 array에서 push와 pop의 경우는 시간복잡도가 O(1)으로, 배열의 마지막에 데이터를 추가하거나 빼기만 하면 되기 때문에 간단하다. 하지만 queue의 속성인 FIFO를 활용하기 위해 가장 앞에 있는 데이터를 제거할 때 .. 2023. 1. 8.

[BAEKJOON] 백준 4803번: 트리 (node.js) 문제 링크: https://www.acmicpc.net/problem/4803 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 문제 그래프는 정점과 간선으로 이루어져 있다. 두 정점 사이에 경로가 있다면, 두 정점은 연결되어 있다고 한다. 연결 요소는 모든 정점이 서로 연결되어 있는 정점의 부분집합이다. 그래프는 하나 또는 그 이상의 연결 요소로 이루어져 있다. 트리는 사이클이 없는 연결 요소이다. 트리에는 여러 성질이 있다. 예를 들어, 트리는 정점이 n개, 간선이 n-1개 있다. 또, 임.. 2023. 1. 8.

[BAEKJOON] 백준 3009번: 네 번째 점 (Python) 문제 링크: https://www.acmicpc.net/problem/3009 3009번: 네 번째 점 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. www.acmicpc.net 문제 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오. 입력 세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다. 출력 직사각형의 네 번째 점의 좌표를 출력한다. 코드 x_ = [] y_ = [] for i in range(3): x, y = map(int, input().split()) x_.append(x) y_.append(y) for i in r.. 2021. 9. 14.

[BAEKJOON] 백준 1085번: 직사각형에서 탈출 (Python) 문제 링크: https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 x, y, w, h가 주어진다. 출력 첫째 줄에 문제의 정답을 출력한다. 코드 x, y, w, h = map(int, inp.. 2021. 9. 13.

[BAEKJOON] 백준 4948번: 베르트랑 공준 (Python) 문제 링크: https://www.acmicpc.net/problem/4948 4948번: 베르트랑 공준 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼 www.acmicpc.net 문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수.. 2021. 9. 5.

[BAEKJOON] 백준 1929번: 소수 구하기 (Python) 문제 링크: https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. 코드 (1차 - 실패) A, B = map(int, input().split()) for i in range(A, B+1): e.. 2021. 9. 5.

[BAEKJOON] 백준 11653번: 소인수분해 (Python) 문제 링크: https://www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. 출력 N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다. 코드 num = int(input()) i = 2 while num > 1: if num % i == 0: num = num // i print(i) else: i += 1 문제 요약 정수 N을 더 이상 나눌 수 없을 때 까지, 나눌 수 있는 최소 숫자들.. 2021. 9. 3.

[BAEKJOON] 백준 2581: 소수 (Python) 문제 링크: https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 문제 자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오. 예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다. 입력 입력의 첫째 줄에 M이, 둘째 줄에 N이 주.. 2021. 8. 31.

이전 1 2 3 4 다음

728x90

티스토리툴바