본문 바로가기

전체 글239

[백준 *Java] - 이모티콘(14226) 이모티콘 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 .. 2022. 4. 27.
[백준 *Java] - BFS 스페셜 저지 (16940) BFS 스페셜 저지 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 👇 문제보기 더보기 문제 설명 BOJ 에서 정답이 여러가지인 경우에는 스페셜 저지를 사용합니다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식입니다. 오늘은 스페셜 저지 코드를 하나 만들어 보려고 합니다. 정점의 개수가 N이고, 정점에서 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있습니다. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다. 큐가 비어있지 않은 동안 다음을 반복한다 큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이.. 2022. 4. 25.
최단거리 문제에 대한 고찰 최단 경로 문제는 가중치 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻합니다. 반대로 가중치가 있는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미합니다. 알고리즘 공부하고, 코딩테스트 문제를 접하다보면? 가중치 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0과 1이 존재할 때 역시 BFS를 사용한다고 생각합니다. 그리고 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 합니다. 이번 주제에선, 왜 최단거리에선 DFS를 사용하지 않고 BFS를 사용하는 지? 와 간선이 0과 1일 때는 다익스트라 알고리즘을 사용하기보단, 0-1 알고리즘을 사용하는 지? 에대한 설명을 드릴 생각입니다. 최단 경로를 탐색할 때 D.. 2022. 4. 25.
너비 우선 탐색(Breadth-First-Search) BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search .. 2022. 4. 24.
[백준 *Java] - 트리의 지름(1167) 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 .. 2022. 4. 22.
트리의 지름 구하기 [증명] 트리의 지름 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은, 먼 두 정점을 연결하는 경로를 의미합니다. 선형 시간안에 트리에서 지름을 구하는 방법은 아래 Flow를 기억해두시면 좋습니다. 트리에서 임의의 정점 x를 잡습니다. 정점 x에서 가장 먼 정점 y를 찾습니다. (dfs / bfs 사용) 정점 y에서 가장 먼 정점 z를 찾습니다. (dfs / bfs 재사용) 이렇게 위 flow 대로 생각하면, 트리의 지름은 정점 y와 정점 z를 연결하는 경로가 됩니다. 여기서 이렇게하면 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 일컫게 됩니다. 증명을 하자면, 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하겠습니다. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y.. 2022. 4. 22.

티스토리툴바