IT 방랑기

그래프가 주어졌을 때 시작 노드에서부터 종료 시점까지 최단 경로를 구할때 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘은 반드시 음수 사이클이 존재하지 않아야 한다. 만약 음수 사이클이 발생할 수 있다만 벨만 포드 알고리즘을 이용해야 한다. 다익스트라는 시작점으로부터 cost에 대한 min heap을 이용하여 가장 cost가 적은 순서대로 계속해서 길을 찾아보며 만약 도착 노드를 발견하는 순간 종료된다. 코드를 보자. 이 소스코드는 백준 최단 경로를 기반으로 하고 있다. #include #include #include #include using namespace std; typedef pair pii; #define ff first #define ss second #define mp(x, y) ma..

알고리즘에서 가장 기본이 되는 탐색 알고리즘인 DFS와 BFS에 대하여 정리한다. DFS는 깊이 우선 탐색으로 그래프가 주어졌을 때 함수 스택을 이용하여 현재 노드와 연결된 노드로 탐색하며, BFS는 너비 우선 탐색으로 큐를 이용하여 현재 노드와 연결된 노드들을 탐색한 다음 연결된 노드들에 연결된 노드들을 차례로 탐색한다. 그래프 V와 E가 주어졌을 때 배열으로 노드를 방문하였는 여부를 저장하여, 다시금 방문하지 않도록 강제한다. 그래프가 아래와 같이 주어졌다고 하자. A - B1 - C1 - B2 - C2 - B3 - C3 DFS는 A에 연결된 B1노드, 그리고 B1노드에 연결된 C1노드를 바로 탐색하기 때문에 트리의 순회에 자주 이용된다. 반면 BFS는 A노드에 연결된 모든 노드 B1, B2, B3를..

트리 순회는 가장 기본적인 알고리즘인 DFS에 바탕을 두고 있다. DFS는 함수 스택을 이용한 재귀 호출로 구현하며, 스택이라는 특징을 바탕으로 트리를 순회할 수 있다. 트리 순회는 트리의 특성과 DFS를 묻는 가장 기초적인 내용이다. 트리 순회 방법으로는 전위 / 중위 / 후위 순회가 있으며, 이는 각각 부모와 좌, 우의 자식 노드가 있을 때, 어느 노드부터 출력할 것인가에 대한 방식이다. 전위 순회는 [부모 / 좌 / 우] 순서이며, 중위 순회는 [ 좌 / 부모 / 우 ] 그리고 후위 순회는 [ 좌 / 우 / 부모 ] 순서로 출력한다. 즉 부모(루트)의 출력 순서에 따라 나뉘게 된다. 이러한 순서를 출력하는 것은 DFS의 출력 위치에 따라서 간단하게 구현할 수 있다. DFS(X)는 루트 X에 대하여 ..

1. 문제 문제 n(1≤n≤100)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 각 버스는 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 대해서 도시 A에서 B로 가는데 필요한 비용의 최소값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비..

1. 문제 문제 두 개의 바구니에 사과와 오렌지가 있다. 첫 번째 바구니에는 사과 A개와 오렌지 B개가 있으며 두 번째 바구니에는 사과 C개와 오렌지 D개가 있다. 당신은 한 바구니에 있는 과일 하나를 집어서 다른 바구니로 옮길 수 있다. 이런 식으로 과일을 옮길 때, 한 바구니에는 사과만 있게 하고 다른 쪽에는 오렌지만 있게 하려고 한다. 앞서 말한 조건을 만족하도록 과일을 옮길 때, 과일을 옮기는 최소 횟수를 구하는 프로그램을 작성하여라. 입력 첫 번째 줄에는 첫 번째 바구니에 있는 사과와 오렌지의 수 A, B가 주어진다. (0 ≤ A, B ≤ 1,000) 두 번째 줄에는 두 번째 바구니에 있는 사과와 오렌지의 수 C, D가 주어진다. (0 ≤ C, D ≤ 1,000) 출력 사과와 오렌지를 옮기는 최..

1. 문제 문제 문제는 매우 간단하다. N을 N번 출력하는 프로그램을 작성하여라. 다만, 답이 길어지는 경우 답의 앞 M자리만 출력한다. 입력 첫 번째 줄에는 N, M이 주어진다. (1 ≤ N, M ≤ 2016) 출력 N을 N번 출력한다. 만약 답이 길어지면 답의 앞 M자리를 출력한다. 예제 입력 복사 20 16 예제 출력 복사 2020202020202020 힌트 [출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음] 2. 해답 이 문제는 기본적인 언어 활용 능력을 묻는 문제로, 입력 받은 숫자 n을 n번 출력하되, 최대 m개의 글자만 출력하는 것이다. 이때 숫자 n을 문자열로 받게되면, m개의 글자까지만 출력하는 것을 손쉽게 제어할 수 있다. #inclu..

1. 문제 문제 고려대학교에 입학한 새내기 호돌이는 안암역을 지나다가 한 붕어빵 장수를 만났어요. “안녕, 안녕, 안녕하십니까, 아저씨! 붕어빵 두 개 주세요.” “안녕을 세 번 외쳤으니 붕어빵 세 개!” 붕어빵 두 개의 값을 내고 세 개를 받은 호돌이는 기분이 좋았어요. 호돌이가 붕어빵 하나를 꺼내어 한 입 물었는데…. 너무 뜨거워서 그만 붕어빵을 떨어뜨리고 말았어요ㅠㅠ 붕어빵은 자유 낙하운동을 하면서 땅에 떨어졌는데 신기하게도 좌우가 뒤집힌 모양으로 착지했답니다. 호돌이가 붕어빵을 한 입 물기 전의 모양이 입력으로 주어지면, 땅에 떨어졌을 때에는 어떤 모양일지 출력하세요. 입력 첫째 줄에는 두 개의 정수 N과 M(0≤N,M≤10)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 붕어빵의 모양이 주어집니다..

1. 문제 문제 ACM-ICPC 대회의 대회장은 R행 C열의 직사각형 형태로 좌석이 배치되어 있다. 대회가 시작하기 전에는 참가자들이 아무것도 만지면 안 되기 때문에 진행자는 'Do not touch ANYTHING!!!'을 연신 외친다. 하지만, 진행자가 성대결절에 걸리면서 'Do not touch ANYTHING!!!'을 외칠 수 없는 처지가 되었다. 따라서 주최측은 CCTV를 설치하여 참가자들을 감시하려고 한다. 이때, 각 CCTV는 N행 N열의 직사각형 영역의 좌석을 촬영할 수 있다. 모든 좌석을 전부 촬영하도록 CCTV를 배치할 때, 최소 몇 개의 CCTV가 필요할까? 입력 첫 번째 줄에 좌석의 세로 크기, 가로 크기 R, C와 한 대의 CCTV가 수용할 수 있는 범위 N이 주어진다. (1 ≤ ..

1. 문제 문제 양의 정수 n이 주어졌을 때, 이를 이진수로 나타냈을 때 1의 위치를 모두 찾는 프로그램을 작성하시오. 최하위 비트(least significant bit, lsb)의 위치는 0이다. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. (1 ≤ T ≤ 10, 1 ≤ n ≤ 10 6 ) 출력 각 테스트 케이스에 대해서, 1의 위치를 공백으로 구분해서 출력한다. 위치가 낮은 것부터 출력한다. 예제 입력 복사 1 13 예제 출력 복사 0 2 3 힌트 [출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음] 2. 해답 이 문제는 정수를 어떻게 이진수로 표현하고 있는지, 그리고 비트와이즈 ..

1. 문제 문제 창영이는 메모장에 '.', '\', '/'을 이용해서 도형을 그렸다. 각 문자는 그림에서 1*1크기의 단위 정사각형을 나타낸다. '.'은 빈 칸을 나타내며, '/'는 정사각형의 왼쪽 아래 꼭지점과 오른쪽 위 꼭지점이 연결된 선분을, '\'은 왼쪽 위 꼭지점과 오른쪽 아래 꼭지점이 연결된 선분을 나타낸다. 창영이가 그린 도형의 넓이를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 h와 w가 주어진다. h는 그림의 높이, w는 너비이다. (2 ≤ h,w ≤ 100) 다음 h개 줄에는 창영이가 메모장에 그린 다각형이 주어진다. 창영이가 그린 다각형은 1개이고, 변과 변이 서로 교차하는 경우는 없고, 자기 자신과 접하는 경우도 없다. 출력 첫째 줄에 다각형의 넓이를 출력한다. 예제 입력 복사 ..