목록알고리즘 문제 풀이/BOJ (77)

영벨롭 개발 일지

[백준 BOJ][C++]2529번 부등호 풀이: DFS

https://www.acmicpc.net/problem/2529 2529번: 부등호 여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력 www.acmicpc.net 이 문제는 DFS로 해결할 수 있습니다. 최대, 최소 정수 두 가지만 뽑으면 되기 때문에, 최대 정수를 찾는 dfs, 최소 정수를 찾는 dfs 두 함수를 작성하여 빠르게 두 정수를 찾을 수 있습니다 . 때문에 문자열의 길이가 k라면 최대, 최소 정수를 찾은 것이므로 그 즉시 dfs를 종료합니다. [풀이 과정] 1. 괄호 정보를 저장하는 comp 배열에 괄호 입력 2. 9부터 max_dfs() 3..
알고리즘 문제 풀이/BOJ 2022. 4. 8. 17:05
[백준 BOJ][C++]14501번 퇴사 풀이: 브루트 포스 & 재귀

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이 문제는 브루트 포스, 재귀호출을 통해 해결할 수 있습니다. [풀이 과정] 1. pair 타입의 vector arr를 선언한다. (first는 일수, second는 이익) 2. arr에 정보를 입력한다. 3. arr의 index는 해당 날짜 - 1 을 의미하므로 날짜 + 일수가 n 보다 커지면 계산 X 4. 해당 날짜 + 일수는 다음 날짜를 의미하므로, 재귀함수의 종료조건으로 해당 날짜가 마지막 날짜거나, 다음 날짜가 n보다 같거나 크면 재귀함수를 종료한다. 5. 다음 날짜부터 n-1 날짜까지 날짜 + 일수가 n 보다 같거나 작다면..
알고리즘 문제 풀이/BOJ 2022. 4. 8. 16:27
[백준 BOJ][C++]1759번 암호 만들기 풀이: DFS

https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 이 문제는 DFS로 해결할 수 있습니다. [풀이 과정] 1. L과 C 입력 2. C개의 알파벳 입력하고 num에 저장 3. num을 오름차순으로 정렬 4. 모든 원소에 대해 순차적으로 dfs 실행 5. 현재 알파벳보다 다음에 위치한 알파벳에 대해 아직 방문 여부 체크 6. 아직 방문하지 않았다면 방문 표시 후, arr[depth]=다음 알파벳, 자음인지 모음인지 체크 후 dfs 호출후 방문 표시 해제 ..
알고리즘 문제 풀이/BOJ 2022. 4. 6. 16:15
[백준 BOJ][C++]2210번 숫자판 점프 풀이: DFS

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 이 문제는 DFS로 해결할 수 있습니다. 다른 dfs 문제와는 다르게 한 번 방문한 위치를 중복하여 방문할 수 있기 때문에 방문 체크는 하지 않지만, 이미 생성된 6자리 숫자에 대해선 방문 표시를 해야하므로 bool visit[1000000]을 선언해야 합니다. [풀이 과정] 1. 숫자판을 입력받는다. 2. 숫자판의 모든 좌표에 대해 dfs를 실행한다. ..
알고리즘 문제 풀이/BOJ 2022. 4. 6. 15:39
[백준 BOJ][C++]14889번 스타트와 링크 풀이: DFS

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이 문제는 DFS로 해결할 수 있습니다. 먼저 0~n-1의 index 중 n/2 길이의 조합을 탐색합니다. n = 4 일 때 0, 1, 2, 3 중 길이 2의 순열은 (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3) 총 6가지가 됩니다. (0, 1) 을 기준으로 계산을 한다고 가정하면, 우리는 s[0][1] + s[1][0] 과 s[2][3] + s[3][2] 의 차이를 계산해야하겠죠..
알고리즘 문제 풀이/BOJ 2022. 4. 5. 18:05
[백준 BOJ][C++]6603번 로또 풀이: DFS

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 = (5 - depth)라는 조건이 붙죠? n-1 : 숫자 배열의 마지막 index i : 탐색할 번호의 index n-1 - i : 탐색할 번호 다음에 남은 수들의 개수 5 - depth : 현..
알고리즘 문제 풀이/BOJ 2022. 4. 5. 16:43
이전 Prev 1 2 3 4 5 6 7 ··· 13 Next 다음