요르딩딩

순열 // 순서를 지키면서 n 개중에서 r 개를 뽑는 경우 // 사용 예시: perm(arr, output, visited, 0, n, 3); static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) { if (depth == r) { print(output, r); return; } for (int i=0; i

지금은 다양한 실전 감각을 위해 프로그래머스를 통해 문제를 풀어보고 있다. 일단 어려운것을 먼저 접하면, 다른 문제는 쉽게 느껴지기를 기대하며, 카카오코딩테스트를 풀어보는중이다. 이번 문제는 순열에 관련된 문제이다. 순열에 관련된 문제를 처음 접해보니 구현하기에 쉽지 않았다. 그리하여 순열관련 로직을 검색하여, 로직을 구현해 보았다. 참고 : https://bcp0109.tistory.com/14?category=848939 위의 블로그에 잘 정리된 내용을 참고하였다. 조합과 순열은 아직 어색하지만 많은 문제를 풀어보면 익숙해 지리라 믿는다. 모두 화이팅 import java.util.*; class Solution { static String[] output; static boolean[] visite..

문제 유형 1. 네트워크 문제 : List를 활용한 DFS (배열로는 단방향 이슈 해결하기 복잡) 2. 단어 한글자씩 변화 문제 : List를 활용한 BFS 3. 2차원 배열의 최단 경로 수 구하기 : DP(점화식) - 해당 위치의 경로 수 = 상측 경로 수 + 좌측 경로 수 4. 2차원 배열을 이용한 지도 문제 : DFS, BFS (상하좌우 이용) 치환 - 포함여부 확인 : st.contains(st) - 문자열 치환 : st = st.replace(",", "/") String[] arr = { "zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine" }; for(int i=0; i 리스트 List list = Arr..

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번문제는 조합을 구현하는 DP문제이다 이차원 배열을 사용하면 규칙을 쉽게 찾을 수 있다. 다만, 밑에 주의사항을 알아야 해결할 수 있다. 주의 : 숫자가 int,long 보다 커지기 때문에 BigInteger 사용해야함 사용법 : BigInteger[][] dp = new BigInteger[n+1][n+1]; BigInteger.valueOf(i); BigInteger.ONE; dp[i][j] = dp[i-1][j].add(dp[i-1][j-1]); 점화식 : dp[i][j] = dp[i-1][j].add(d..

이번문제는 예전에 못풀었던 문제라 다시 풀어보게되었다. 첫 시작할때 역시 규칙을 찾으려고 하였으나, 쉽지 않았다. 문득 든 생각이 모눈종이였다. 이차원배열에서 색종이가 놓이는 부분을 1로, 안놓이는 부분을 0으로 간주한다면, 겹치는 부분의 규칙을 생각할 필요없이 겹치면 그냥 1로 두면 되기 때문이다. 이 모눈종이의 힌트는 페이지 마지막에 초등부 문제라고 적혀있어서, 접근을 할 수 있었던거 같다. 난이도도 쉽고 초등부인데 왜 이렇게 어렵나 했다. import java.util.*; class Main { static int n, cnt = 0; static int[][] graph; public static void main(String[] args) { Scanner sc = new Scanner(Sys..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 이번문제는 DP 문제 중에서 난이도가 낮은 문제라고 생각된다. 규칙을 찾기도 쉽고, 구현하는것도 할만하기 때문이다. 다만, 처음에는 최대값을 생각하지 않고, 해당 날짜에서 순차적으로 선택했을때의 결과를 DP에 넣고, 그중 가장 큰 값을 반환하게 하였으나, 마지막 예제에서 잘못된 결과가 반환되는것을 보고, 잘못 생각한것을 알 수 있었다. 이문제에서의 포인트를 살펴보자. 여기서의 포인트는 역순으로 DP를 입력하는것이다. 그 이유는 현재 위치에서 선택할수 있는 최대금액을 뽑는것이고, 그것이 마지막에서 앞으로 갈 수록 도출한 결과를 중복해서..

이번문제 역시 DP 문제중 하나이다. 매번 풀때마다 느끼는 거지만 DP문제는 어려운것 같다. 많이 풀어보도록 해야겠다. 구현하는것은 어렵지 않으나, 점화식 및 규칙을 찾는 부분이 어렵게 느껴진다. 이번문제는 비슷하게 접근은 했으나, 규칙을 찾지 못해 풀이를 찾은 후 이해한 뒤 풀어보았다. 풀이는 아래 사진을 참고하면된다. 다음에 이와같이 DP문제가 나왔을때 이번 경험을 토대로 잘 풀 수 있었으면 좋겠다. 화이팅!!! import java.util.*; class Main{ static int n, m; static int[] coin, dp; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextIn..

역시 아직까지 DP문제는 조금 어렵게? 느껴지는것 같다. 처음에는 재귀를 사용하여 풀었느나, 시간초과가 나와 다른 방법을 찾아보던 중 DP를 사용하게 되었다. DP를 사용할때 헷갈렸던 부분은 해당 위치에 값을 넣을때 기준이 dp[i][j + value] += dp[i][j];// 오른쪽 dp[i + value][j] += dp[i][j]; // 아래 되는 부분이 이해가 안갔다. 내가 생각한 DP테이블은 해당 점을 지나가는 횟수가 해당점에 기록된다고 생각했다. 하지만, 기준은 해당점에 도달할 수 있는 경로의 수를 표시하는 거였다. 아래 내용을 바탕으로 나는 dp[1][1]을 4번 지나가니깐 4가 들어가야되는거 아닌가 생각했다. 하지만, 지나가는 횟수가 아니라, dp[0][0] -> dp[1][1]까지 갈수..