본문 바로가기

분류 전체보기

 (265)
백준1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 트리를 이용한 bfs 문제였다. 트리의 단말 노드에서 다른 단말 노드로 이동하기까지 소요되는 비용이 가장 큰 루트를 찾아서 출력하면 ..
그리디 알고리즘 그리디 알고리즘이란 그리디 알고리즘이란 전에 선택했던 것과 미래에 다가올 선택에 관계없이 현재 가장 최고의 것을 선택하는 알고리즘이다. 직접적으로 명시된 제약조건을 빠르게 해결하는데 사용하고 순간순간 최적의 선택으로 솔루션에 도달한다. 그리디를 사용할 때는 항상 지금 사용하는 그리디 해결법이 최적인지 생각해야 한다. 그 순간에만 최적의 방법일 수 있고 다른 부분 문제에서는 최적의 방법이 아닐 수 있기 때문이다. 다음은 그리디 알고리즘으로 접근하는 것이 항상 옳은 해가 아니라는 예이다. 그리디 설계법 1. 그 순간에 최적 상태를 고려하여 원소들을 뽑아낸다. 2. 현재 사용한 방법이 다른 부분 문제에 대하여 최적인지 고려한다. 예제 다음은 정해진 시간동안 최대로 들을 수 있는 강의 수를 찾는 문제이다. 주어..
백준7569 - 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마 www.acmicpc.net 3차원 행렬을 이용한 bfs문제였다. 익은 토마토를 기점으로 안 익은 토마토를 찾아내면 되어서 bfs를 사용하였다. 처음에 토마토의 정보를..
백준6593 - 상범 빌딩 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서 www.acmicpc.net 3차원 행렬을 이용한 다익스트라로 해결한 문제이다. 6개 방향으로 이동이 가능하며 #인 지점은 이동하지 못한다. 처음에 S의 위치를 큐..
백준2665 - 미로만들기 https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 다익스트라를 이용하여 수행하였다. bfs를 이용하면 방문한 곳을 재방문하지 않기 때문에 다익스트라로 수행하여 풀었다. 과거에 내가 가려 하는 곳까지 뚫은 벽의 갯수보다 현재 내가 가려는 곳까지 벽의 갯수가 적으면 현재로 내가 가려하는 곳까지의 벽의 갯수를 갱신한다. 전에 풀었던 문제와 다르게 먼저 도달하는 여부와 상관없이 벽의 갯수만 카운팅하면 되어 큐를 사용하였다. #include #include #i..
백준1719 - 택배 https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다. 예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5는 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간 www.acmicpc.net M대 M으로 최소거리 찾는 방법이여서 플로이드 와샬을 선택했다. 입력받는 지점의 출발점을 지정해 두었다가 최소거리가 갱신되면 갱신된 지점의 ..
백준13023 - ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 주어진 숫자들 중에서 친구관계 4개를 찾으면 1을 출력하고 못 찾을 경우 0을 출력하는 문제다. 나는 DFS를 사용하여 풀었다. 길찾기와 다르게 모든 경로를 탐색하지 않고 친구관계 4개만 빠르게 찾으면 되는 문제이기 때문에 DFS를 이용하여 깊이가 4인 경우를 찾았다. 이차원 벡터를 이용하여 친구관계를 표현하였다. 이차원 배열을 사용할 수도 있었는 데 기업 코딩테스트에서 이차원 백터를 주어지고 문제를 풀라는 경우가 많아서 이차원 백터를 사용해 보았다. #include #include #define MA..
3. 분할정복 - 퀵 정렬 퀵 정렬이란? 퀵 정렬은 병합 정렬과 마찬가지로 분할정복을 이용하여 정렬을 한다. 퀵 정렬은 피벗을 이용한 정렬 방식이다. 피벗은 두 개의 집합을 나누기 위해 생성된 기준으로 피벗보다 작은 것은 왼쪽으로 피벗보다 큰 것은 오른쪽으로 정렬이 된다. 피벗은 어떤 수가 되어도 상관이 없다. 피벗을 기준으로 두 개의 집합을 나누는 분할의 과정을 거치면 다시 피벗을 기준으로 정렬을 한다. 다음은 퀵 정렬을 표현한 예이다. 시간복잡도 퀵 정렬은 두 개의 집합으로 분할하는 것과 피벗을 기준으로 정렬하는 것으로 정렬을 수행한다. 두 개의 집합으로 분리하는 시간은 항상 O(n)을 유지한다. 피벗을 기준으로 정렬하는 시간은 자료의 배치에 따라 평균적으로 O(logn)을 유지하고 최악의 경우는 O(n2)까지 시간이 걸린다...

티스토리툴바