https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 난이도 : 골드 3 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 이분 탐색, 너비 우선 탐색, 분리 집합 설명 N개의 섬들은 M개의 다리를 통해 서로 연결 되어있습니다. 각 다리에는 중량 제한이 있고, 중량 제한을 초과할 경우 다리가 무너집니다. 한 번에 이동할 수 있는 중량의 최댓값을 구하는 문제입니다. 가장 빨리 떠오른 생각은 브..

https://www.acmicpc.net/problem/10216 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 기하학, 분리 집합 설명 통신 범위가 직/간접적으로 겹치는 부대는 하나의 부대처럼 행동합니다. 즉, 통신범위가 겹치는 그룹을 모두 같은 그룹으로 묶어 몇 개의 그룹이 나오는지 구하는 문제입니다. 그룹화와 서로 다른 그룹의 개수를 구한다는 점에서 분리집합과 유니온 파인드를 사용할 수 있을 것 같습니다. 분리 집..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. (1 ≤ Ai ≤ 10, www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프이론, 그래프탐색, 분리집합 설명 친구의 친구는 나에게도 친구이므로, 한 친구만 만들면 해당 친구가 속한 그룹은 모두 내 친구가 되므로, 그룹 당 친구비가 가장 적은 친구와 친구를 맺으면 됩니다. 접근방법 1. 분리집합 (유니온 - 파인드)를 사용해 각 친구관계를 그룹화한다. 2. 각 ..

https://www.acmicpc.net/problem/13905 13905번: 세부 첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄 www.acmicpc.net 난이도 : 골드 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 분리 집합, 최소 스패닝 트리 설명 한 섬에서 다른 섬으로 가지만, 다리(간선)가 버틸 수 있는 문제가 한정되어 있어, 가중치의 최솟값이 최대가 되야 합니다. 가중치의 최솟값이 최대가 되야 한다... 이게 무슨 말인가 싶긴 하지만, 위 그래프를 예시로 들 때, 1번 집에서 5번 집으로 가..

https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net 난이도 : 플래티넘 4 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 분리 집합 설명 문명은 인접한 칸으로 세력을 넓힙니다. 세력을 넓히면서 한 칸을 서로 차지하려 할 때 혹은 서로 맞닿을 때 두 문명은 합쳐집니다. 한 칸을 서로 차지하려 할 때는 BFS 탐색 중 쉽게 알 수 있으나, 인접할 경우에는 4방향 BFS를 한 번 더 돌려 확인할 수 있습니다..

이번에 알아볼 것은 굉장히 유명한 자료구조 삼대장들인 스택(Stack), 큐(Queue), 데크(Deque) 입니다. 스택 (Stack) 스택은 자료구조의 맨 위에서만 삽입과 삭제가 일어나는 자료구조 입니다. 포인터가 맨 위를 가르키고 있어, 데이터의 가장 위에서만 삽입과 삭제가 일어나지요. 가장 나중에 들어간 원소가 가장 빨리 나오는 LIFO(Last in - First out) 구조 입니다. PUSH를 통해 원소를 삽입, POP을 통해 원소를 꺼냅니다. 이는 쌓아놓은 접시와 비슷합니다. 접시를 쌓을 때는 보통 가장 윗 접시부터 꺼내 쓰곤하죠? 컨트롤 + z를 눌러 뒤로가기를 하는 것도, 브라우저의 뒤로가기도 스택의 예시 중 하나입니다. 자바의 Stack 클래스 출력 : 10, 10, 5, 3 자바에서..

이번에 알아볼 것은 그래프 탐색의 대표적인 방법인 그래프의 표현 방법인 인접 리스트와 인접 행렬입니다. 그래프와 트리에 관한 내용은 이전 포스팅을 참고해주세요. https://uknowblog.tistory.com/357 [자료구조] 그래프(Graph)와 트리(Tree) - 점과 선의 예술 그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어 uknowblog.tistory.com 그래프의 연결 표현 : 인접 배열과 인접 리스트 그래프의 연결을 표현하는 방법에는 인접 배열과 인접 리스트가 있습니다. 이름처럼 배열을 썼느냐, 리스트를 썼느냐의 차..

그래프(Graph) 그래프란 무엇일까요? 점과 선이요. 가장 간단하면서 가장 잘 나타낸 말인 것 같습니다. 이산 수학과 컴퓨터 공학에서 말하는 그래프는 각각의 정점(Node, Vertex)이 간선(Edge)으로 이어진 형태입니다. 그래프의 시초 위 두 개의 그림은 다들 수학시간때 한 번씩 본 그림일텐데요. '쾨니히스베르크 다리 건너기' 문제입니다. 쾨니히스베르크(현 러시아 칼리닌그라드) 중앙에는 섬이 있는데, 7개의 다리를 단 한 번씩만 모두 건널 수 있느냐? 라는 문제입니다. 이걸 단순화 시킨게 아래의 그림인데, 각 육지를 점, 다리를 선으로 나타낸 것이 그래프의 시초 중 하나라고 추측되고 있습니다. 참고로 위 문제는 '한 번씩 모두 건널 수 없다'라는 것이 수학적으로 증명되었으며, 자세한 내용은 오일..

https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 난이도 : 실버 4 태그 : 자료구조, 문자열, 스택 설명 모든 왼쪽 괄호는 오른쪽 괄호와 맞아야 합니다. [](), [()] 등은 맞지만, ([], ([)] 등은 맞지 않습니다. 스택을 활용하기 좋은 문제일 것 같네요. [()]을 예로 들겠습니다. 첫 번째 글자 : [ stack에 문자를 넣습니다. 현재 스택 : [ 두 번째 글자 : ( stack이 비어있지 않으나, 가장 ..

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 난이도 : 실버 2 태그 : 자료구조, 스택, 연결리스트 시도 1 간단히 생각해보면, 스택이나 리스트 하나를 만들어두고 커서의 위치를 담을 cursorIdx 변수를 만들어 특정 위치에서 add 혹은 remove를 하면 쉽게 풀릴 것 같네요 import java.util.StringTokenizer fun main() = with(System.`in`.bufferedReader()) { val wor..