본문 바로가기
반응형

전체 글147

[백준] 2146번 - 다리 만들기 (Java) https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net N x N인 맵에서 여러 개의 섬이 있다. 각 섬을 연결하는 다리를 한 개만 건설한다고 할 때 가장 짧은 거리를 구하라. BFS탐색으로 각 섬은 탐색할 수 있다. 그런데 각 섬과 다른 섬과 가장 최소거리는 어떻게 구하지? 시간 제한 : 2초 메모리 제한 : 192MB 지도크기 : N 2022. 10. 2.
플러드 필(Flood Fill) 알고리즘 플러드 필은 다차원 배열에서 어떤 칸과 연결된 영역을 찾는 알고리즘이다. 그림판에서 색 채우기 명령으로 동일한 색을 전부 바꿔버리는 것과 동일하다. 플러드 필 문제는 BFS/DFS 알고리즘으로 풀 수 있다. [BFS의 풀이과정] 1. 시작하는 칸을 큐에 넣고 방문 표시를 한다. 2. 큐에서 원소를 꺼내어 그 칸에 상/하/좌/우로 인접한 4개의 칸에 대해 탐색을 한다. 3. 해당 칸을 이전에 방문했다면 무시하고, 처음 방문했다면 방문 표시를 하고 해당 칸을 큐에 넣는다. 4. 큐의 모든 원소가 빌 때까지 2를 반복한다. 5. 모든 칸이 큐에 1번씩만 들어가므로 시간복잡도는 칸이 N개일 때 O(N)이다. ※ 참고 : https://blog.encrypted.gg/941 2022. 10. 1.
[백준] 1662번 - 압축 (Java) 문자열을 순차탐색해서 ')'가 나올 때까지 계속 스택에 저장한다. ')'를 만나면 스택에 저장했던 문자들을 하나씩 꺼낸다. '('를 만나면 꺼낸 문자들을 문자열로 만들어서 괄호 앞의 숫자만큼 루프를 돌려서 문자열에 머지한다. 이걸 반복해서 괄호안의 문자들을 모두 정리한 후 남은 문자열을 다시 붙여서 최종 길이를 출력한다. import java.util.Scanner; import java.io.IOException; import java.util.Stack; import java.lang.StringBuilder; //[백준] 1662번 - 압축 (Java) public class Main { static char ch[]; static int str_len = 0; public void InputDat.. 2022. 9. 30.
[백준] 2493번 - 탑 (Java) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 레이저 신호는 탑의 왼쪽으로 쏘면, 그 탑보다 큰 탑에서만 수신할 수 있다. 각각의 탐에서 발사한 레이저 신호를 어느 탑에서 수신하는지 번호를 출력한다. i번째 탑보다 왼쪽에 있는 탑이 크면 수신이 가능하다. N의 범위가 2022. 9. 29.
[백준] 6198번 - 옥상 정원 꾸미기 (Java) https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net i번째 건물에서 볼 수 있는 건물의 수를 구해야 한다. 이중 루프를 돌려서 i번째 건물보다 작은 건물이 나오면 sum++를 해주면 되는데... 순차검색으로 풀면 타임 아웃이 발생한다. 문제는 N 2, 1->3, 1->4 (2) 0개 (3) 1개: 3->4 (4) 0개 (5) 1개: 5->6 (6) 0개 * i번째 건물을 볼수 있는 건물의 수 (1) 0개 (2) 1개: 1->2 (3) 1개:.. 2022. 9. 29.
[백준] 2775번 - 부녀회장이 될테야 (Java) https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 - a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합 2) 점화식 찾기 - DP[k][n] = DP[k-1][1] + ... + DP[k-1][n] 3) 초기값 정하기 - DP[0][1] ~ DP[0][14]까지 호실 번호와 동일한 사람수를 가진다. DP 테이블을 2중 배열을 사용해서 세로축은 층수, 가로축은 호실.. 2022. 9. 28.
[백준] 9095번 - 1,2,3 더하기 (Java) https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 메모이제이션을 좀 안다고 생각했는데 한 방 먹은 문제다. 1시간 동안 고민했는데 풀지 못했다. 알고 봤더니 1~3까지 숫자를 계산할 때 약간의 상상력을 보태야 하는데 그까지 생각이 미치지가 못했다. * DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1) DP 테이블 정의 - DP테이블은 1,2,3의 합으로 조합할 수 있는 경우의 수를 가진다. - 정수 n은 < 11이므로 DP[10+1]로 구성해서 값을 미리 구한 다.. 2022. 9. 28.
[백준] 1003번 - 피보나치 함수 (Java) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. DP 테이블의 성격 정의 - DP[N][2]로 생성해서 DP[i][0]에는 0의 출력 횟수, DP[i][1]에는 1의 출력 횟수를 저장한다. - N 2022. 9. 27.
[백준] 1463번 - 1로 만들기 (Java) https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP(Dynamic Programming) 문제 푸는 공식 3단계 1) DP 테이블 정의 2) 점화식 찾기 3) 초기값 정하기 1. 테이블 정의 DP[i] = 정수 i를 1로 만들때까지 걸리는 연산 횟수의 최소값 2. 점화식 찾기 DP[12]의 경우 a. 3으로 나눌 경우 -> DP[12] = DP[4] + 1 -> DP[x] = DP[x/3] + 1 b. 2로 나눌 경우 -> DP[12] = DP[6] + 1 -> DP[x] = DP[x/2] + 1 c. 1을 뺄경우 -> DP[12] = DP[11] + 1 .. 2022. 9. 26.
반응형

티스토리툴바