알고리즘/백준
-
[백준] 2015번 : 수들의 합4 - 자바(JAVA)알고리즘/백준 2022. 7. 21. 00:01
https://www.acmicpc.net/problem/2015 2015번: 수들의 합 4 첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로 www.acmicpc.net 문제 해석 A [1], A [2],..... A [N]의 N개의 정수가 저장되어 있는 배열이 있습니다. 이 배열 A의 부분합이란 1
-
[백준] 2448번 : 별 찍기 - 11 - 자바(JAVA)알고리즘/백준 2022. 7. 20. 00:01
https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 문제 해석 주어진 규칙에 따라 별을 찍는 문제입니다. 첫 번째 줄부터 N번째 줄까지 별을 출력합니다 다음은 N = 24일 때 예시입니다. 삼각형 모양이며 중앙에는 역삼각형으로 비어있습니다. 문제 풀이 전 설계 유의미한 규칙을 찾아보려고 합니다. 공백을 기준으로 마지막 줄에는 공백이 0개 N-1번째 줄에는 공백기 1개 N-2번째 줄에는 공백기 2개 .... 두번째줄에는 공백이 N-2개 첫 번째 줄에는 공백이 N-1개 삼각형을 기준으로 전체 삼각형에서 ..
-
[백준] 9466번 : 텀 프로젝트 - 자바(JAVA)알고리즘/백준 2022. 7. 16. 00:01
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해석 프로젝트 팀원 수에는 제한이 없습니다. 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 합니다. 혼자 하고 싶어 한다면 자기 자신을 선택하는 것도 가능합니다. 예시로 한반에 7명의 학생들이 존재하고 학생들을 1번부터 7번으로 표현할 때 선택의 결과는 다음과 같습니다. 1 2 3 4 5 6 7 3 1 3 7 3 4 6 위의 결과를 통해 (3)과 (4 7 6)은 팀을 이룰 수 있지만 1,..
-
[백준] 1976번 : 여행 가자 - 자바(JAVA)알고리즘/백준 2022. 7. 14. 00:01
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 해석 N개의 도시가 존재하고 두 도시 사이에 길이 있을 수도 없을 수도 있습니다. 여행 경로가 가능한지 탐색하고자 합니다. 만약 도시가 5개 존재하고 A-B, B-C, A-D, B-D, E-A의 길이 존재합니다. 이를 그림으로 도식화 하면 다음과 같습니다. 위의 그림 예시에서는 모든 도시가 연결되어있기 때문에 어떤 여행계획이든 가능합니다. 문제 풀이 전 설계 위의 예시에서 봤듯이 모든 도시가..
-
[백준] 3687번 : 성냥개비 - 자바(JAVA)알고리즘/백준 2022. 7. 13. 00:01
https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 문제 해석 문제는 굉장히 간단하게 성냥개비의 개수가 주어지고 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수 와 가장 큰 수를 찾으면 됩니다. 다음은 숫자별로 필요한 성냥개비의 개수입니다. 0 : 6개 1 : 2개 2 : 5개 3 : 5개 4 : 4개 5 : 5개 6 : 6개 7 : 3개 8 : 7개 9 : 6개 문제 풀이 전 설계 테스트 케이스가 100개 주어지며 여기서 만들 수 있는 가장 작은 ..
-
[백준] 2536번 : 버스 갈아타기 - 자바(JAVA)알고리즘/백준 2022. 7. 8. 00:01
https://www.acmicpc.net/problem/2536 2536번: 버스 갈아타기 첫 번째 줄에 수직선의 수 m과 수평선의 수 n이 빈칸을 사이에 두고 주어진다 (1 ≤ m,n ≤ 100,000). 두 번째 줄에 버스의 수 k (1 ≤ k ≤ 5,000)가 주어진다. 세 번째 줄부터 k 줄에 걸쳐 각 줄에 버스의 www.acmicpc.net 문제 해석 2차원 평면상에 m개의 수직선과 n개의 수평선으로 이루어진 격자 형태의 도로망이 있습니다. 아래 그림은 7개의 수직선과 6개의 수평선으로 이루어진 도로망의 예시입니다. 가로 7 세로 6 이 도로망을 운행하는 버스들이 k개 존재하며 각 버스는 하나의 수평선 상의 두 교차점 사이 선분이나 수직선 상의 두 교차점 사이 선분을 왕복 운행합니다. 즉, 가..
-
[백준] 1981번 : 배열에서 이동 - 자바(JAVA)알고리즘/백준 2022. 7. 6. 00:01
https://www.acmicpc.net/problem/1981 1981번: 배열에서 이동 n×n짜리의 배열이 하나 있다. 이 배열의 (1, 1)에서 (n, n)까지 이동하려고 한다. 이동할 때는 상, 하, 좌, 우의 네 인접한 칸으로만 이동할 수 있다. 이와 같이 이동하다 보면, 배열에서 몇 개의 수를 www.acmicpc.net 문제 해석 n x n 배열이 존재하고 배열의 (1,1)에서 (n, n)까지 이동하려고 합니다. 이동할 때는 상하좌우로 1칸씩 이동할 수 있습니다. 이동하기 위해 거쳐 간 수들 중 최댓값과 최솟값의 차이가 가장 작아지는 경우를 구하세요 문제 풀이 전 설계 n의 범위는 최대 100 x 100으로 10,000입니다. 세 가지 풀이가 떠올랐습니다. 1. 파라메트릭 서치 배열의 각 ..
-
[백준] 7453번 : 합이 0인 네 정수 - 자바(JAVA)알고리즘/백준 2022. 7. 5. 00:01
https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 문제 해석 정수로 이루어진 크기가 같은 배열 4개가 존재합니다. A[a], B[b], C[c], D[d] 의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하세요 배열의 크기 최대(4000) 배열에 들어있는 정수의 최대는 2^28입니다. 문제 풀이 전 설계 시간 제한이 12초인 점이 가장 먼저 눈에 들어왔습니다. 또한 정수의 절댓값은 2^28인데 4개의 배열..