티스토리

IT-World

검색하기

블로그 홈

IT-World

nyxveil4.tistory.com/m

I am a student interested in computer science.

구독자: 0

방명록 방문하기

주요 글 목록

[Algorithm] BAEKJOON 16953번: A → B (Python) https://www.acmicpc.net/problem/16953 문제정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.2를 곱한다.1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자. 입력첫째 줄에 A, B (1 ≤ A 출력A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다. 풀이그리디 알고리즘을 사용해서 B에서 A로 변환하는 과정에서 각 단계에서 가능한 두 가지 연산 중 최적의 연산을 선택하여 해결하였다. Python 소스 코드def min_operations(A, B): operations = 0 while B > A: if B % 10 == 1.. 공감수 1 댓글수 1 2024. 9. 15.
[Algorithm] BAEKJOON 11000번: 강의실 배정 (C++) https://www.acmicpc.net/problem/11000 문제수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.)수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si 출력강의실의 개수를 출력하라. 풀이그리디 알고리즘과 우선순위 큐를 활용해서 가장 빨리 끝나는 수업을 효율적으로 추적하여 해결하.. 공감수 0 댓글수 0 2024. 9. 15.
[Algorithm] BAEKJOON 1946번: 신입 사원 (C++) https://www.acmicpc.net/problem/1946 문제언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입.. 공감수 8 댓글수 8 2024. 9. 14.
[Algorithm] BAEKJOON 1789번: 수들의 합 (C++) https://www.acmicpc.net/problem/1789 문제서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. 출력첫째 줄에 자연수 N의 최댓값을 출력한다. 풀이그리디 알고리즘을 사용하여 해결하였다. 최대한 많은 수의 자연수를 포함시키는 것이 목표이므로 가장 작은 수부터 순서대로 더하는 것이 가장 효과적인 전략이다. C++ 소스 코드#include using namespace std;int main() { unsigned long long S; cin >> S; unsigned long long sum = 0; int N = 0; fo.. 공감수 0 댓글수 0 2024. 9. 14.
[Algorithm] BAEKJOON 2217번: 로프 (Python) https://www.acmicpc.net/problem/2217 문제N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력첫째 줄.. 공감수 1 댓글수 1 2024. 9. 14.
[Algorithm] BAEKJOON 1541번: 잃어버린 괄호 (Python) https://www.acmicpc.net/problem/1541 문제세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다. 출력첫째 줄에 정답을 출력한다. 풀이수식을 마이너스 기호 기준으.. 공감수 0 댓글수 1 2024. 9. 14.
[Algorithm] BAEKJOON 1485번: 정사각형 (C++) https://www.acmicpc.net/problem/1485 문제네 점이 주어졌을 때, 네 점을 이용해 정사각형을 만들 수 있는지 없는지를 구하는 프로그램을 작성하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 네 줄로 이루어져 있으며, 점의 좌표가 한 줄에 하나씩 주어진다. 점의 좌표는 -100,000보다 크거나 같고, 100,000보다 작거나 같은 정수이다. 같은 점이 두 번 이상 주어지지 않는다. 출력각 테스트 케이스마다 입력으로 주어진 네 점을 이용해서 정사각형을 만들 수 있으면 1을, 없으면 0을 출력한다. 풀이네 점이 정사각형을 형성하기 위해서는 모든 변의 길이가 같아야 하고, 대각선의 길이가 같아야 한다는 점을 이용하여 해결하였다. C++ 소.. 공감수 0 댓글수 0 2024. 9. 11.
[Algorithm] BAEKJOON 1463번: 1로 만들기 (C++) https://www.acmicpc.net/problem/1463 문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이다이나믹 프로그래밍 기법을 활용해 최소 연산 횟수를 저장하는 배열인 dp 배열을 사용하여 해결하였다. C++ 소스 코드#include #include using namespace std;int main(.. 공감수 0 댓글수 0 2024. 9. 6.
[Algorithm] BAEKJOON 1927번: 최소 힙 (Python) https://www.acmicpc.net/problem/1927 문제널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. .. 공감수 1 댓글수 1 2024. 9. 3.
[Algorithm] BAEKJOON 1003번: 피보나치 함수 (C++) https://www.acmicpc.net/problem/1003 문제다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }}fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.fibonacci(2)는 fibonacci(1) (두 번째.. 공감수 0 댓글수 0 2024. 9. 2.
[Algorithm] BAEKJOON 7576번: 토마토 (C++) https://www.acmicpc.net/problem/7576 문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 .. 공감수 0 댓글수 0 2024. 8. 31.
[Algorithm] BAEKJOON 10026번: 적록색약 (C++) https://www.acmicpc.net/problem/10026 문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBBGGBBBBBBRRBBRRRRRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1.. 공감수 0 댓글수 0 2024. 8. 29.
[Algorithm] BAEKJOON 9372번: 상근이의 여행 (C++) https://www.acmicpc.net/problem/9372 문제상근이는 겨울방학을 맞아 N개국을 여행하면서 자아를 찾기로 마음먹었다. 하지만 상근이는 새로운 비행기를 무서워하기 때문에, 최대한 적은 종류의 비행기를 타고 국가들을 이동하려고 한다.이번 방학 동안의 비행 스케줄이 주어졌을 때, 상근이가 가장 적은 종류의 비행기를 타고 모든 국가들을 여행할 수 있도록 도와주자.상근이가 한 국가에서 다른 국가로 이동할 때 다른 국가를 거쳐 가도(심지어 이미 방문한 국가라도) 된다. 입력첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고,각 테스트 케이스마다 다음과 같은 정보가 주어진다.첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000.. 공감수 0 댓글수 0 2024. 8. 24.
[Algorithm] BAEKJOON 14241번: 슬라임 합치기 (Python) https://www.acmicpc.net/problem/14241 문제영선이와 효빈이는 슬라임을 합치는 게임을 하고 있다. 두 사람은 두 슬라임을 골라서 하나로 합쳐야 한다. 게임은 슬라임이 하나 남았을 때 끝난다.모든 슬라임은 양수 크기를 가지고 있다. 두 슬라임 x와 y를 합쳤을 때, 합친 슬라임의 크기는 x+y가 된다. 또한, 슬라임을 합칠 때 마다 두 사람은 x*y 점수를 얻게 된다.영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 구하는 프로그램을 작성하시오. 입력첫째 줄에 슬라임의 개수 N (2 ≤ N ≤ 100)이 주어진다.둘째 줄에는 슬라임의 크기가 주어진다. 크기는 100보다 작거나 같은 자연수이다. 출력첫째 줄에 영선이와 효빈이가 얻을 수 있는 점수의 최댓값을 출력한다. 풀이.. 공감수 0 댓글수 0 2024. 8. 23.
[Algorithm] BAEKJOON 20044번: Project Teams (C++) https://www.acmicpc.net/problem/20044 문제코딩 프로젝트 수업을 가르치는 수찬이는 프로젝트 팀을 가능하면 공정하게 구성하려고 한다. 프로젝트 팀 하나는 두 명의 학생으로 구성되는데, 각 학생들의 코딩 역량은 모두 다르다. 각 학생은 한 팀의 팀원이어야 한다. 공정성을 높이기 위해 수찬이는 팀원 코딩 역량의 합을 최대한 일정하게 유지하려고 한다. 학생들이 코딩 역량이 주어졌을 때 수찬이가 팀을 구성하는데 도움이 되는 프로그램을 작성하라.문제를 간단하게 하기 위해, 학생 수는 2n이라 가정하자 (n은 양의 정수). 각 학생 si의 코딩 역량은 양의 정수 w(si)로 나타내면 한 i번째 팀 Gi의 코딩 역량은 w(Gi) = ∑s∈Giw(s)로 나타낼 수 있다. 작성할 프로그램 .. 공감수 0 댓글수 0 2024. 8. 22.
[Algorithm] BAEKJOON 17390번: 이건 꼭 풀어야 해! (C++) https://www.acmicpc.net/problem/17390 문제숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!!L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다. 입력첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다. Ai 는 수열 A의 i 번.. 공감수 0 댓글수 0 2024. 8. 19.
[Algorithm] BAEKJOON 21919번: 소수 최소 공배수 (Python) https://www.acmicpc.net/problem/21919 문제행복이는 길이가 N인 수열 A에서 소수들을 골라 최소공배수를 구해보려고 한다.행복이를 도와 이를 계산해주자. 입력첫째 줄에 수열 A의 길이 N이 주어진다. (1≤N≤10,000)그 다음줄에는 수열 A의 원소 Ai가 공백으로 구분되어 주어진다. (2≤Ai≤1,000,000)답이 2의 63승 미만인 입력만 주어진다. 출력첫째 줄에 소수들의 최소공배수를 출력한다.만약 소수가 없는 경우는 -1을 출력한다. 풀이수열 A의 모든 원소에 대해 소수 판정을 먼저 해준 다음 파이썬의 math 라이브러리에 있는 최소 공배수 함수인 lcm 함수를 활용하여 해결하였다. Python 소스 코드import mathN = int(input())A = .. 공감수 0 댓글수 0 2024. 8. 17.
[Algorithm] BAEKJOON 21921번: 블로그 (Python) https://www.acmicpc.net/problem/21921 문제찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. 입력첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다. 출력첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에.. 공감수 0 댓글수 0 2024. 8. 16.
[Algorithm] BAEKJOON 15719번: 중복된 숫자 (C++) https://www.acmicpc.net/problem/15719 문제1부터 N - 1까지의 정수가 하나씩 정렬되지 않은 채로 저장되어 있는 어떤 수열 A가 있다. 수열 A에 임의의 정수 M(1 ≤ M ≤ N – 1)을 넣어 크기가 N인 수열로 만들었을 때, 임의의 정수 M을 찾는 프로그램을 작성하라. 입력첫째 줄에 수열의 크기 N(2 ≤ N ≤ 10,000,000)이 주어진다.둘째 줄에 수열 A의 원소인 N개의 정수가 주어진다. 입력으로 주어지는 정수는 모두 1보다 크거나 같고, N-1보다 작거나 같은 정수이며 문제의 답인 M을 제외하고는 모두 서로 다른 정수이다. 출력M을 출력하라. 풀이처음의 접근법은 입력받은 모든 숫자를 배열에 저장하고 개수가 2개인 수를 찾으려고 한 것이었지만 문제의 N.. 공감수 0 댓글수 0 2024. 8. 16.
[Algorithm] BAEKJOON 1312번: 소수 (Python) https://www.acmicpc.net/problem/1312 문제피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다. 입력첫 번째 줄에 A와 B(1 ≤ A, B ≤ 100,000), N(1 ≤ N ≤ 1,000,000)이 공백을 경계로 주어진다. 출력A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다. 풀이처음에는 소수점 관련 함수를 이용하여 풀어야 하나 생각했는데 주어진 N 조건의 범위가 매우 큰 것을 보고 수학적 원리를 이용해야 한다는 것을 알았다.단순히 어렸을 때 배웠던 나눗셈의 원리, 즉 나머지에 10을 곱하고 다시 나누는 것을 반복하.. 공감수 1 댓글수 0 2024. 8. 16.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.