본문 바로가기

전체 글69

[백준] 3273번 - 두 수의 합 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 n개의 정수로 이루어진 수열에서 수열의 요소인 Ai, Aj와 그외 주어지는 자연수 x에 대하여 Ai + Aj = x를 만족하는 (Ai, Aj)의 쌍의 갯수를 구하시오. 조건 수열의 요소를 Ai라고 할때 1 2023. 5. 29.
[JAVA] 변수의 기본형 타입(Primitive type)과 참조형 타입(Reference type) 처음 자바를 공부하게 되면 기본형 타입과 참조형 타입에 대해 배우게 된다. 개념 자체는 그리 어렵지 않지만 막연히 사용하다보면 이따금씩 두 타입의 차이점이 헷갈려서 종종 검색해볼 때가 있는데 개인적으로 열람할 용도로 정리할 필요성을 느꼈다. 기본형 타입(Primitive Type) 논리형(boolean), 문자형(char), 정수형(byte, short, in, long), 실수형(float, double)으로 구성된다. 특징은 아래와 같다. - 기본형 타입은 메모리의 스택(stack)영역에 저장된다. - 저장 공간에 실제 데이터 값을 가진다. - 참조형 타입과 다르게 객체가 아니기 때문에 null 을 가질 수 없다. - 산술 연산이 가능하다. 참조형 타입(Reference Type) 8가지 기본형 타입.. 2023. 5. 28.
[백준] 1976번 - 여행 가자 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1번부터 N번까지의 도시가 있을 때, 입력으로 i 번째 도시와 j 번째 도시의 연결 여부가 주어질 때 여행 계획의 모든 도시를 방문할 수 있는지 확인하는 문제이다. 따라서 도시가 정점이고 도시간의 연결 정보가 정점간의 간선인 그래프로 치환하여 접근할 수 있겠다. 추가로 도시간의 연결은 양방향성을 가지므로 무방향 그래프이고 여행 계획 순서대로 여행을 하는 동안 이미 방문한 도시를 중복해서 방문하는 것이 가능하다고 하였으므로 여행 계획에 있는 도시들이 하나의 연결 .. 2023. 5. 27.
[백준] 1991번 - 트리 순회 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이진 트리란 하나의 노드가 가질 수 있는 자식 노드의 수가 최대 2개로 제한되어 있는 트리구조로 자식 노드를 왼쪽 자식 노드와 오른쪽 자식 노드라고 부른다. 트리를 사용하는 경우 보통은 트리를 순회하며 찾고자 하는 값을 탐색하기 때문에 해당 자료구조를 사용하기 위해서 순회하는 방법에 대해서는 기본적으로 알아두면 좋다. 트리를 순회하는 방법은 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(pos.. 2023. 5. 25.
[알고리즘] 위상 정렬 순환 그래프와 비순환 그래프 정점 간의 연결관계를 표현하는 그래프가 내부에 순환 구간을 가지고 있으면 순환 그래프, 그렇지 않다면 비순환 그래프라고 한다. DAG(Directed Acyclic Graph) 비순환 방향 그래프라고 부른다. 명칭에서 유추해볼 수 있듯이 간선이 방향성을 가지는 비순환 그래프를 의미한다. 따라서 어느 한 정점으로부터 간선을 따라 출발하면 다시 해당 정점으로 돌아오는 경로는 존재하지 않는다. Topological Sort 위상 정렬이라고 부르며, 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 정해주고자 할 때 사용하는 알고리즘이다. 주변에서 볼 수 있는 예시로는 대학교에서 커리큘럼대로 강의를 수강하거나, RPG 게임 속의 스킬트리대로 스킬을 찍는 경우이다. 스킬 트.. 2023. 5. 24.
[백준] 6497번 - 전력난 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 문제는 전력난에 허덕이는 도시의 시장이 모든 길로 통하도록 하면서 최소 비용으로 가로등을 켤 때 절약할 수 있는 최대 액수를 구하라고 말한다. 문제 조건을 보면 도시는 항상 연결 그래프 형태이고 거리는 양방향 도로이다. 거리가 양방향 그래프이기 때문에 방향은 고려하지 않아도 되기에 무방향 그래프라고 생각해도 된다. 또한 도시상의 모든 길의 거리 합은 2^31 미터 보다 작다고 하였으므로 변수에 int 자료형을 사용해도 문제없다. 집을 정점, 집과 집 사이의 도로를 간선 그.. 2023. 5. 24.
[JAVA] EOF - 자바에서 테스트 케이스의 개수가 주어지지 않는 경우 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 백준 문제를 풀다보면 가끔 입력으로 주어지는 테스트 케이스 개수를 명시하지 않는 경우가 있다. 위의 문제가 바로 그런 경우인데, 이 경우 EOF를 사용할 수 있다. EOF End Of File의 약자로, 데이터 소스로부터 더 이상 읽을 수 있는 데이터가 없다는 것을 의미한다. 위의 경우 테스트 케이스가 한 줄로 이루어져 있을 뿐, 몇 개의 테스트 케이스가 주어질 것인지 명시되어 있지 않다. 이럴 때에는 입력을 받을 때 사용하는 클래스의 메소드 및 특성을 이용한다. 자바에서 입력을 받을 때 사용하는 Scanner와 BufferedReader 두 가지 클래스의 경우로 나누어 .. 2023. 5. 24.
[백준] 1717번 - 집합의 표현 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 유니온 파인드 개념을 이해하고 적용해볼 수 있는 문제이다. 유니온 파인드 개념은 아래 글을 참고하자. [알고리즘] 유니온 파인드(Union Find) Union Find - 유니온 파인드 - 그래프 자료구조에서 주로 사용하는 알고리즘 - 두 노드가 같은 그래프에 속하는지 판별 - 서로소 집합(Disjoin-Set)으로도 불린다. - 노드를 합치는 Uion 연산과 노드의 루 stonage.tistory.com 유니온 파인드는 .. 2023. 5. 24.
[알고리즘] 유니온 파인드(Union Find) Union Find - 유니온 파인드 - 그래프 자료구조에서 주로 사용하는 알고리즘 - 두 노드가 같은 그래프에 속하는지 판별 - 서로소 집합(Disjoin-Set)으로도 불린다. - 노드를 합치는 Uion 연산과 노드의 루트 노드를 찾는 Find 연산으로 이루어진다. - 트리 구조로 이루어진 자료구조 중 한 가지로 생각되기도 한다. 그래프에서 임의의 두 정점이 연결 그래프인지 확인하고 싶다면 그래프를 순회하며 두 정점이 연결 되어 있는지 확인해 볼 수도 있지만 많은 정점에 대해서 동일한 작업을 반복하면 오랜 시간이 걸릴 것이다. 그러나 그래프의 일부분을 일종의 트리로 보고 공통의 루트 노드를 같는 노드끼리 하나의 집합으로 본다면, 두 노드에 대한 부모 노드의 동일 여부만 알아도 그래프의 모든 정점을 순.. 2023. 5. 24.

티스토리툴바