성장을 위한 기록장

[JAVA] 백준 11724 연결 요소 개수 - DFS

DFS ( 깊이 우선 탐색 )그래프 완전 탐색 방식 중 하나이다. 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.깊이 우선 탐색은 실제 구현 시 재귀함수를 통해 구현하므로 스택 자료구조를 이용한다. https://www.acmicpc.net/problem/11724 문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v)..

[JAVA] 백준 11268 절댓값 힙 - 우선순위 큐

https://www.acmicpc.net/problem/11286 문제절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.배열에 정수 x (x ≠ 0)를 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다..

https://www.acmicpc.net/problem/2164 문제N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.N이..

스택이란?배열에서 발전된 형태의 자료구조로, 삽입과 삭제 연산이 후입선출로 이루어지는 자료구조이다.후입 선출은 삽입과 삭제가 한쪽으로만 이루어지는 특징을 가지고 있다. top : 삽입과 삭제가 일어나는 위치push: top 위치에 새로운 데이터를 삽입함.pop: top 위치에 있는 데이터를 삭제하고 확인peek: top 위치에 있는 데이터를 확인 보통 스택은 깊이 우선 탐색과 백트래킹 문제에 유용하게 쓰인다.후입선출 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문이다. 왜 그럴까?? 재귀함수를 보면 조건이 만족할 때까지 함수를 호출하다가 함수 호출이 끝나면, 제일 마지막에 호출된 함수부터 계산하며 제일 처음 호출 함수까지 돌아온다.예를 들어, facorial 함수를 생각해보자. int facto..

https://www.acmicpc.net/problem/12891 범위를 구하고, 범위를 유지한채로 이동하면서 문제를 해결하는 알고리즘 방식이다.배열과 조건 체크 배열을 통해 슬라이딩 윈도우 문제를 풀어보자. 문제평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”는 DNA 문자열이 아니지만 “ACCA”는 DNA 문자열이다. 이런 신비한 문자열에 완전히 매료된 민호는 임의의 DNA 문자열을 만들고 만들어진 DNA 문자열의 부분문자열을 비밀번호로 사용하기로 마음먹었다.하지만 민호는 이러한 방법에는 큰 문제가 있다는 것을 발견했다. 임의의 DNA 문자열..

https://www.acmicpc.net/problem/1940 문제주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하..

투 포인터는 두개의 포인터로 알고리즘의 시간 복잡도를 최적화하는 방식이다.투 포인터는 조건에 따라 시작/끝 위치를 동적으로 조절해야 하는 경우나 합뿐 아니라 조건을 만족하는 구간을 찾아야할 때 유리한 알고리즘이다. https://www.acmicpc.net/problem/2018 문제어떠한 자연수 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가지가 있다...

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다. - Prefix sum(구간 합) : 구간 합이란 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다. - Partial sum(부분 합) : 부분 합이란 구간 합과 달리 처음부터 특정인덱스까지의 합을 의미한다. 즉 0~k 인덱스 사이의 값들의 합을 의미한다. 구간합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 배열 A 의 합 배열은 다음과 같다. S[i] = A[0] + A[1] + A[2] + A[3] + ...... + A[i-1] + A[i]; 합 배열은 기존의 배열을 전처리한 배열이라고 생각하면 된다. 이렇게..

배열이란?배열은 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.배열에는 인덱스를 통해 참조할 수 있기 때문에, 값에 바로 접근할 수 있다는 장점을 가진다.하지만, 배열에서 삽입이나 삭제를 할 때는 주변에 있는 값들을 이동시키는 과정이 필요하다.또한 배열의 크기는 선언할 때 지정하며 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 아래는 배열의 대표적이고 기본적인 문제인 백준 11720 문제이다. 매우 쉽다.https://www.acmicpc.net/problem/11720 문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.입력첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.출력입력으로 주어진 숫자..