본문 바로가기

Algorithm8

특정 거리의 도시 찾기(백준 18352) 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다. 입력 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (.. 2022. 11. 1.
[C언어] 중복제거한 배열 출력 중복된 값을 제거한 배열을 출력하는 코드를 간단하게 적어보았다. include int main(){ int arr[10] = { 10,9,9,8,7,7,7, 6,5, 1 }; int b[10]; // 중복을 제거한 데이터를 담을 배열 int i, n = 1; b[0] = a[0]; // 첫 데이터를 a[0]의 데이터를 삽입 // 중복이 되지 않는 값만 a[i]에서 걸러서 b[n]에 삽입하고 [n++]연산으로 한칸 전진한다. for (i = 1; i < 10; i++) if (arr[i] != b[n - 1]) b[n++] = arr[i]; // 버블 정렬 for(i = 0 ;i 2022. 10. 21.
박스포장 문제 마트에서 장을 보고 박스를 포장하려고 합니다. 박스를 포장하는 데는 폭이 너무 좁습니다. 그렇기에 한 줄로 서 있어야 하고, 들어온 순서대로 한 명씩 나가야 합니다. 불행 중 다행은, 인원에 맞게 포장할 수 있는 기구들이 놓여 있어, 모두가 포장을 할 수 있다는 것입니다. 짐이 많은 사람은 짐이 적은 사람보다 포장하는 시간이 길 수밖에 없습니다. 뒷사람이 포장을 전부 끝냈어도 앞사람이 끝내지 못하면 기다려야 합니다. 앞사람이 포장을 끝내면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다. 만약, 앞사람의 박스는 5 개고, 뒷사람 1의 박스는 4 개, 뒷사람 2의 박스는 8 개라고 가정했을 때, 뒷사람 1이 제일 먼저 박스 포장을 끝내게 되어도 앞사람 1의 포장이 마칠 때까지 기다렸다가 같이 나.. 2022. 9. 30.
재귀(recursion) 재귀란 자기 자신을 정의하면서 자기 자신을 재참조하는 방법을 의미한다. ex) 1부터 num까지의 합을 구하는 재귀함수 #include #include using namespace std; int sum(int num){ if(num == 0) { return 0; } return num + sum(num-1); } 위에서 보는 것처럼 재귀함수는 자기 자신을 호출하면서 계속해서 반복된다. 재귀함수로 표현할 수 있는것들은 반복문으로 모두 표현이 가능하다. 그렇다면 왜 재귀함수를 쓰는것일까? - 재귀함수는 반복문의 비해서 가독성이 좋다. - 변수의 사용이 줄어든다. 다른 장점도 있겠지만 내가 생각하는 장점은 가독성이 좋아서 사용하는 것 같다. 코드는 짜는 사람뿐만이 아니라 나중에 유지보수하는 다른 사용자도 .. 2022. 9. 29.

티스토리툴바