본문 바로가기

Develop/알고리즘9

알고리즘 | 백트래킹 | Java 백준[Silver II] 외판원 순회 2 - 10971 [Silver II] 외판원 순회 2 - 10971문제 링크성능 요약메모리: 12984 KB, 시간: 100 ms분류백트래킹, 브루트포스 알고리즘, 외판원 순회 문제제출 일자2024년 9월 29일 16:28:03문제 설명외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획.. 2024. 9. 29.
알고리즘 | 백트래킹 | Java 백준[Silver I] 부등호 - 2529 [Silver I] 부등호 - 2529문제 링크 성능 요약메모리: 26648 KB, 시간: 132 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 9월 28일 12:51:50문제 설명두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. A ⇒ 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 3 1 7 0이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계.. 2024. 9. 28.
알고리즘 | DFS | Java 백준[Silver II] 유기농 배추 - 1012 [Silver II] 유기농 배추 - 1012문제 링크성능 요약메모리: 13552 KB, 시간: 96 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색제출 일자2024년 9월 28일 00:27:07문제 설명차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 .. 2024. 9. 28.
알고리즘 | 백트래킹 | Java 백준[Silver II] 꽃길 - 14620 [Silver II] 꽃길 - 14620문제 링크성능 요약메모리: 15184 KB, 시간: 108 ms분류브루트포스 알고리즘제출 일자2024년 9월 27일 21:13:56문제 설명2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다.진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므로 진아는 다음해 식목일 부터 꽃길을 걸을 수 있다.하지만 진아에게는 꽃의 씨앗이 세개밖에 없었으므로 세 개의 꽃이 하나도 죽지 않고 1년후에 꽃잎이 만개하길 원한다.꽃밭은 N*N의 격자 모양이고 진아는 씨앗을 (1,1)~(N,N)의 지점 중 한곳에 심을 수 있다. 꽃의 씨앗은 그림 (a)처럼 심어지며 1년 후 꽃이 피면 그림 (b)모양.. 2024. 9. 27.
알고리즘 | 백트래킹 | Java 백준[Silver I] 스타트와 링크 - 14889 [Silver I] 스타트와 링크 - 14889문제 링크성능 요약메모리: 15176 KB, 시간: 268 ms분류백트래킹, 브루트포스 알고리즘제출 일자2024년 9월 15일 17:46:41문제 설명오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Si.. 2024. 9. 15.
알고리즘 | 조합론 | Java 백준[Silver III] 다음 순열 - 10972 [Silver III] 다음 순열 - 10972문제 링크성능 요약메모리: 20068 KB, 시간: 224 ms분류조합론, 수학제출 일자2024년 9월 14일 02:22:06문제 설명1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.1, 2, 31, 3, 22, 1, 32, 3, 13, 1, 23, 2, 1입력첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.출력첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전.. 2024. 9. 14.

티스토리툴바