문제 17070번: 파이프 옮기기 1유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의www.acmicpc.net풀이시작점(1, 2)에서 종료점(N, N)까지 갈 수 있는 방법을 구하는 문제BFS, DFS, DP 등 다양하게 해당 문제를 해결할 수 있는데DFS 방식과 DP로 해결해보았다. 파이프가 '가로'인 경우, 갈 수 있는 방향은 동쪽과 남동쪽파이프가 '세로'인 경우, 갈 수 있는 방향은 남쪽과 남동쪽파이프가 '대각'인 경우, 갈 수 있는 방향은 동쪽과 남쪽과 남동쪽이다. 이 점을 활용해서 다음으로 갈 방향을 쭉..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 부모 문자열(t)의 길이 - 자식 문자열(p)의 길이가 비교할 횟수이며 자식 문자열(p)와 비교할 문자열은 substring 메서드를 사용해서 뽑아냈다. substring 사용: 문자열.substring(시작 인덱스, 종료 인덱스 + 1) 코드 class Solution { public int solution(String t, String p) { int pLen = p.length(); int len = t.length() - pLen; long tgt = Long.parseLong(p); int..
문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제는 열 별로 2차원 배열을 탐색하면서 연결 요소의 크기를 찾는 문제인데 N과 M이 각 500이기 때문에 2차원 배열을 모두 탐색하면서 BFS를 돌게되면 시간초과가 발생한다. 2차원 배열 순회는 반드시 해야하는 부분이므로 BFS 탐색을 줄일 수 있는 방안을 찾아야 한다. 여러 방법이 있겠지만, 문제를 풀며 떠오른 방법은 visit 배열을 전역으로 선언하고 BFS를 돌며 연결 요소 내의 원소의 개수(= 집합내의 원소의 개수)가 파악이 되면 집합 내 원소들의 열 좌표를 바탕으로 집합 내의 원소의 ..
문제 25372번: 성택이의 은밀한 비밀번호 부산사이버대학교 학생 성택이는 엄마의 의뢰를 받아 주어진 문자열이 현관문 비밀번호에 사용 가능한지 알아내야 한다. 성택이는 공부해야 하므로 우리가 도와주자! 사용할 수 있는 비밀번호 www.acmicpc.net 풀이 입력 받은 문자열의 길이가 6 이상 9이하이면 yes 그렇지 않으면 no 출력 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder..
문제 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 풀이 주어진 여러 동전을 최소로 사용(중복 O)해서 K원을 만드는 문제이다. 일반적인 DFS 방식으로 접근한다면 시간초과가 발생하기 때문에 메모이제이션을 바탕으로 해결해야 한다. DP 중 탑다운(Top Down) 방식으로 접근해보았다. 입력 예제 : N = 2, K = 6, arr = [1, 3] 우리는 K=6원을 모으기 위한 최소 동전 개수를 알고 싶은 것이다. 이 값을 도출하기 위해선, 어떤 값을 알아야할까? 정답은 가지..
문제 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 주어진 N 개의 숫자 카드를 비교할 때 최소한의 비교를 할 경우 몇 번 해야 하는지 찾는 문제 -> 주어진 N 개의 수를 정렬하고 작은 숫자 카드 끼리 합을 구하면 된다. N 개의 숫자 카드를 정렬해야 하며, 자유롭게 값을 추가하고 빼기 위해서 우선순위 큐를 사용 풀이 순서 1. N 개의 입력 받는 수를 우선순위 큐에 저장하고 2. 큐 사이즈가 2 이상일 때 두 개를 빼서, 합한 값을 res에 저장 3. 합한 값은 다시 큐에 넣어줌(우선..
문제 3062번: 수 뒤집기 수 124를 뒤집으면 421이 되고 이 두 수를 합하면 545가 된다. 124와 같이 원래 수와 뒤집은 수를 합한 수가 좌우 대칭이 되는지 테스트 하는 프로그램을 작성하시오. www.acmicpc.net 풀이 입력 받은 수(a)와 a를 거꾸로 한 수(b)의 합(c)이 팰린드롬인지 구하는 문제입니다. 풀이 순서는 다음과 같습니다. 1. a를 토대로 거꾸로 순회하며 b를 구해줍니다. 2. a+b를 통해 c를 구해줍니다. 3. c를 문자열로 바꾼 뒤, 0번째 인덱스와, c.length()-1 인덱스에 각각 left, right 포인터를 두고 r > l 조건에 어긋날 때까지 while문을 돕니다. 이 과정에서 s.charAt(left) != s.charAt(right)일 경우 팰린드..
문제 S = [1, 2, 3, 4, 5, 6, 7]이 주어지고 한번씩만 써서 만들 수 있는 2개의 수(a, b)가 있을 때 a, b 곱의 최댓값을 구하는 문제입니다. 풀이 완전탐색으로 접근하면 괜찮을까 고민을 해보며 부분집합으로 문제를 해결하려고 했습니다. 이러면 답이 나오긴 하지만, (123, 4567) (4567, 123) 값과 같이 불필요한 중복 값이 존재하게 됩니다. 따라서 방문처리를 통해, 만들어지는 두 수 중에서 하나의 수(a)의 길이가 한 번만 완성되도록 구현했습니다. 코드 let arr = [1, 2, 3, 4, 5, 6, 7]; let N = arr.length; let v = [false, false, false, false, false]; let v2 = [false, false, f..
