본문 바로가기

알고리즘 문제풀이

 (29)
[백준 2602] 돌다리 건너기 - Java 문제링크: https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 � www.acmicpc.net 문제설명 문제접근 이 문제는 완전탐색으로 접근할 수 있지만, 성능이 매우 나빠져 시간초과가 발생합니다. 동적계획법을 사용하면 O(NM) 시간만에 문제를 해결할 수 있습니다. (N = 다리의 길이, M = 두루마리의 길이) DP[다리][현재 다리 위치][두루마리 위치] = 현재 다리 위치에서 해당 두루마리 위치까지 이동 가능한 모든 경우의 수를 담습니다. 점화식은 다음과 같습니다. (악마의 돌다..
[백준 2146] 다리 만들기 - Java 문제링크: https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제설명 문제접근 다리를 놓으려면, 다리의 시작지점과 끝지점을 알아야 합니다. 그러기 위해서는 섬들을 식별할 수 있어야 합니다. 따라서 각 섬들을 먼저 식별하고, 섬들과 붙어 있는 지역(1과 인접한 0)을 체크해 줍니다. 체크를 한 후, 2중 for 문으로 배열을 순회하며, 체크한 부분에서 시작해 다른 섬으로 이어지는 최소 경로를 BFS로 찾습니다. 체크했던 모든 지역에서 BFS를 진행한 후..
[백준 17406] 배열 돌리기4 - Java 문제링크: https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 문제설명 문제접근 조합 + 시뮬레이션 문제입니다. 회전연산을 모두 사용하는 조합 중에 나올 수 있는 배열 A의 값의 최솟값을 찾으면 됩니다. 코드에서 수행해야 하는 작은 기능들이 많으므로 각각을 함수로 구현해 사용하면 덜 복잡하게 구현할 수 있습니다. 주의사항 조합을 탐색할 때마다 배열을 새로 복사해 주어야 합니다. 그래야 현재 회전연산의 결과가 다른 조합..
[프로그래머스 lv3] 경주로 건설 - Java 문제링크: https://programmers.co.kr/learn/courses/30/lessons/67259 코딩테스트 연습 - 경주로 건설 [[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]] 3800 [[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]] 2100 [[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[ programmers.co.kr 문제설명 문제접근 BFS로 풀었습니다. 주의할 점은 어떤 방향으로 이동하냐에..
[백준 1107] 리모컨 - Java 문제링크: https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net 문제설명 문제접근 타겟 N을 기준으로 채널을 위아래로 각각 이동하며 숫자 버튼을 눌러서 만들 수 있는지 확인합니다. 이동한 채널이 숫자 버튼만을 눌러서 이동이 가능하다면 채널 N에서 현재 채널까지 이동한 횟수(위아래 버튼을 누른 횟수) + 현재 채널을 숫자버튼을 눌러 이동할 때 필요한 버튼 입력횟수를 더해 반환합니다. 만약 타겟 N에서 시작채널 100 까지 이동했을 ..
[백준 1182] 부분 수열의 합 - Java 문제링크: https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제설명 문제접근 0번째 인덱스부터 차례로 해당 인덱스의 값을 더하는 경우와 더하지 않는 경우 두 가지로 나눠 탐색을 진행하면 풀 수 있습니다. 이 때 중복 확인을 방지 하기 위해 더하지 않는 경우는 타겟 S와 비교하지 않고 넘어갑니다. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23..
[LeetCode] PalindromicSubstrings - Java 문제링크: https://leetcode.com/problems/palindromic-substrings/ Palindromic Substrings - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes..
[LeetCode] Group Anagrams - Java 문제링크: https://leetcode.com/problems/group-anagrams/ Group Anagrams - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 Given an array of strings, group anagrams together. Example: Input: ["eat", "tea", "tan", "ate", "nat", "bat"], Output: [["ate","eat","tea"], ["nat","tan"], ["b..

티스토리툴바