- [ 기록/백준 ][백준 / 자바] 1008번 A/B2023-12-20 13:53:50https://www.acmicpc.net/problem/1008 1008번: A/B 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 두 정수 A와 B를 입력받은 다음, A/B를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 A와 B가 주어진다. (0 < A, B < 10) 1 3 출력 첫째 줄에 A/B를 출력한다. 실제 정답과 출력값의 절대오차 또는 상대오차가 10-9 이하이면 정답이다. 0.33333333333333333333333333333333 10-9 이하의 오차를 허용한다는 말은 꼭 소수 9번째 자리까지만 출력하라는 뜻이 아니다. 풀이 import java.util.Scanner; public class Main { public ..
- [ 공부/알고리즘 ][자료구조] 배열과 리스트2023-12-20 09:48:08배열과 리스트 배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스 값을 통해 참조할 수 있고 선언한 자료형의 값만 저장 가능 인덱스를 사용하여 값에 바로 접근할 수 있다. 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다. 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 구조가 간단하다. 리스트 노드*를 포인터로 연결한 자료구조 ArrayList, LinkedList, Stack, Vactor 등 *노드 : 값과 포인터를 묶은 것 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 값에 접근하는 속도가 느리다. 포인터로..
- [ 기록/백준 ][백준 / 자바] 11286번 절댓값 힙 - 우선순위 큐2023-12-19 22:43:10https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러 개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000..
- [ 기록/백준 ][백준 / 자바] 2164번 카드2 - 큐2023-12-19 21:33:30https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. ..
- [ 기록/백준 ][백준 / 자바] 1874번 스택 수열 - 스택2023-12-19 21:13:04https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수..
- [ 공부/알고리즘 ][알고리즘] 복잡도2023-12-19 20:14:44복잡도 알고리즘의 성능을 나타내는 척도 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘 공간 복잡도 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 시간 복잡도 시간 복잡도란 문제를 해결하는데 걸리는 시간과 입력의 함수 관계이다. 알고리즘의 시간 복잡도는 주로 빅-오 표기법을 사용하며 빅-오표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 간단하게 표현하자면 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석한 것 빅 오메가 : 최선일 때 빅 세타 : 보통일 때 빅 오 : 최악일 때 # 100 미만의 랜덤 숫자 n이 있고, n을 구하기 위해 100번 반복하는 반복문을 작성한 경우 빅 오메가 → n이 0인 경우이므로 1 빅 세타 → 평균치이므로 n/..
- [ 기록/백준 ][백준 / 자바] 2018번 수들의 합 5 - 투 포인터2023-12-19 00:37:282018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 문제 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한다. 이때, 사용하는 자연수는 N이하여야 한다. 예를 들어, 15를 나타내는 방법은 15, 7+8, 4+5+6, 1+2+3+4+5의 4가지가 있다. 반면에 10을 나타내는 방법은 10, 1+2+3+4의 2가지가 있다. N을 입력..
- [ 기록/백준 ][백준 / 자바] 11659번 구간 합 구하기 4 - 구간 합2023-12-18 22:48:4511659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 5 3 5 4 3 2 1 1 3 2 4 5 5 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다..