본문 바로가기
728x90

전체 글69

[백준] 14252번 공약수열 문제풀이 https://www.acmicpc.net/problem/14252 14252번: 공약수열 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘 www.acmicpc.net 문제) 서로 다른 양의 정수로 이루어진 크기가 N인 집합 A가 주어진다. 영선이는 집합에 새로운 양의 정수를 추가하려고 한다. 이때, 집합에 있는 수를 정렬한 결과에서 인접한 두 수의 공약수가 1을 넘으면 안 된다. 그러기 위해서 수를 최소 몇 개 추가해야하는지 구하는 프로그램을 작성하시오. 입력) 첫째 줄에 N이 주어진다.(1 2023. 8. 9.
[백준] 13412번 서로소 쌍(c) 문제풀이 https://www.acmicpc.net/problem/13412 13412번: 서로소 쌍 두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다. 어떤 자연수 N이 서로소 www.acmicpc.net 문제) 두 자연수 A, B의 최대공약수를 GCD(A, B)라고 할 때, A와 B가 서로소면 GCD(A, B) = 1이다. 두 자연수 A, B의 최소공배수를 LCM(A, B)라고 할 때, A와 B가 서로소면 LCM(A, B) = A x B이다. 어떤 자연수 N이 서로소인 두 자연수 A, B의 최소공배수라고 할 때, A, B로 가능.. 2023. 5. 9.
[자료구조] 덱(Deque) - 코딩기록 덱 덱은 앞서 포스팅에서 올렸던 스택과 큐를 합친 버전이라고 할 수 있다. 스택이나 큐는 한쪽에서만 삽입과 삭제가 가능했다면 덱은 양쪽 끝에서 삽입과 삭제가 모두 가능하게 만든 큐이다. 터널과 비슷하다고 할 수 있다. 덱은 스택이나 큐처럼 사용할 수 있기 때문에 활용도가 높은 자료구조이다. 덱의 기능 이제 덱STL을 활용해 기능들을 살펴보겠다. push_front(x) : 덱의 앞에 x를 추가 push_back(x) : 덱의 뒤에 x를 추가 pop_front() : 덱의 원소 중 맨 앞 원소를 삭제 pop_back() : 덱의 원소 중 맨 뒤 원소를 삭제 front() : 덱의 맨 앞 원소를 반환 back() : 덱의 맨 뒤 원소를 반환 empty() : 덱이 비어있으면 1(true), 비어있지 않으면 .. 2023. 5. 5.
[자료구조] 큐(Queue) - 코딩기록 큐(Queue) 큐는 이전 포스팅에서 설명했던 스택과 약간 다른 점이 있는 자료구조이다. 이전에 설명했던 스택은 LIFO(후입선출)구조였지만 큐는 FIFO(First - In - First - Out) 선입선출 구조이다. 즉, 먼저 집어 넣은 데이터가 먼저 나오는 것이다. 1번, 2번, 3번 데이터가 차례로 들어오고 이 순서대로 나간다고 생각하면 된다. 맨 오른쪽에 있는 화살표에 해당하는 구간이 삽입연산이 수행되는 곳인 리어(rear)이고 맨 왼쪽에 있는 화살표에 해당하는 구간이 삭제연산이 수행되는 곳인 프론트(front)이다. 큐의 기능 이제 큐STL을 활용해 큐의 기능들을 살펴보겠다. push(x) : 원소 x를 큐의 맨 뒤에 추가 pop() : 큐의 맨 앞 원소 삭제 empty() : 큐가 비어있으.. 2023. 5. 4.
[백준] 10773번 제로(c++) 문제풀이 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 0을 부를 때마다 가장 최근에 재민이가 쓴 수를 지운다는 것은 스택에서 삭제 연산에 해당하는 말이다. 이 말을 통해 자료구조인 스택을 문제에 적용해야 한다는 것을 파악할 수 있다. 만약 0을 말하지 않았다면 수를 받아 적어야 하므로 스택에 삽입 연산을 실행해야 한다. 스택에 저장되어 있는 원소들의 합을 구해야 하므로 스택의 사이즈(원소의 개수)만큼 반복문을 실행시.. 2023. 5. 3.
[자료구조] 스택(Stack) - 코딩기록 자료구조 자료구조에 대해 간단히만 짚고 넘어가겠다. 자료구조의 정의는 컴퓨터과학에서 효율적인 접근과 수정을 가능하게 해주는 자료의 조직, 관리, 저장을 의미한다. 자료구조를 통해 데이터를 효율적으로 저장, 관리할 수 있고 메모리를 절약하거나 시간을 단축할 수 있다. 우리가 흔히 말하는 알고리즘과는 약간의 차이가 있다. 자료구조는 이름처럼 데이터를 저장하기 위한 구조이고 알고리즘은 자료구조에 있는 데이터를 활용해 문제를 해결하는 방법이라고 할 수 있다. 즉, 자료구조를 잘 익혀두면 문제를 더 효율적으로 해결할 수 있을 것이다. 이 포스팅에서 다룰 것은 자료구조에서 선형구조 중 하나인 스택이다. 스택 스택은 '쌓다'라는 뜻을 가지고 있다. 이 말처럼 스택을 이해할 때 탑을 상상하면 편하다. 다음과 같은 탑이.. 2023. 5. 3.
728x90

티스토리툴바