간지나제의 기술블로그

programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 꽤 간단한 문제인데도 핵심을 잘 파악하지 못했다. 규칙을 찾는 문제라고 생각하고 규칙을 찾으려했는데 잘 찾아지지 않았다. 가로로 가능한 사각형만 셀 때 10, 9, 7, .. 이런식으로 되니까 뭔가 있지않을까라고 생각만했지 기울기..를 잘 생각하지 못했다. 수학이라고 생각하고 좌표로 바꿔 생각하면 정말 쉽게 풀 수 있는 문제. 그리고 형 변환에 대해..

programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 문제는 이해한대로 순서대로 풀었다. 문자를 1개, 2개, ... , 문자열의 갯수만큼 자를 수 있으니까 그만큼의 for문을 돌렸고 그만큼 자르는 함수를 만들어서 갯수가 가장 작은 답을 return하게끔 했다. 크게 세 부분으로 나눌 수 있을 것 같다. 기본적으로 전에 자른 str과 현재의 str을 비교해서 다르면 전에 있는 str을 StringBulder에 넣고 만약 ..

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 쉬운듯 하면서 잘 풀리지 않았던 문제. 처음 접근은 for문으로 index를 접근하려했지만 for문도 여러개이고 좋은 방법이 아닌 것 같고 다른 아이디어가 따오르지 않아 다른 블로그를 참조했다. 여러 해결방법이 있어보이지만 그나마 간단한 해결방법을 참조하였다. 1) public int solution(String skill, String[] skill_trees) { int answer = 0; for(int i=0; i

programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 알고나면 어렵지 않아보이지만 막상 접근하기 쉽지 않았던 문제였다. 일단, 접근 방법이 떠오르지 않아서 다른 사람의 풀이를 참조했다. n이 5억이다. 적어도 O(N)으로는 풀 수 없는 문제라는 얘기이다. 따라서, 규칙을 찾아서 풀어야하는데 일단 3으로 나눠본다. 나눴더니 어느정도 규칙이 보인다. 나머지가 0일 때 4, 1일 때 1, 2일 때 2이다. 여기까지는 생각했는데 두 자리 숫자가 되면 어떻게 되지에서 막혀버렸다. 풀이는 간단하다. 우리가 흔히 알고 있는 10진수를 2진수로 바꾸는 방법처럼 풀면 된다. 몫이 0이 될 때까지 나눈 후에 나머지를 ..

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 규칙찾기도 굉장히 어렵고 그것을 코드로 구현할 때도 2차원 배열이 아닌 1차원 배열로 중첩해서 푸는 방식이 인상적인 문제였다. 어떻게 푸는지 몰라서 블로그를 많이 참고했고 이해하기도 어려웠다. 2차원 배열로 했을 때 행렬을 만들게 되면 기본적으로 O(N^2)이상이 되기 때문에 시간초과가 날 것이다. 따라서, 아래와 같이 푼다면 이중 for문이지만 money.len..

programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 해석을 하면 탐색을 활용하여서 가장 깊은 leaf node가 몇 개 있는지 보라는 문제로 해석할 수 있을 것 같다. 처음에 dfs로 접근하려고 하니까 leaf node의 레벨이 각각 다를텐데 끝을 확인하기 어려울거라고 생각했다. 또, 전에 있는 노드가 연결되어 있는 부분은 가지 않아야 하니까(최단거리) 비교해야 하는게 좀 많아서 어렵게 느껴졌다. bfs를 잘 활용하지 않았어서 각 블로그를 참고했고 가장 이해하기 쉬운 블로그를 참고하여 풀게 되었다..

dp를 이해하는데 가장 기본이 되면서 중요한 문제가 아닐까 싶다. dp는 기본적으로 bottom-up 방식을 선호하는데 차례차례 적다보면 규칙이 보이기 때문이다. 이게 쉽게 찾아지냐 안 찾아지냐의 차이에 따라서 dp의 난이도가 결정되는 것 같다. 이 문제 같은 경우는 n-1과 n-2를 통해서 n을 찾는 문제이다. n-1 경우에 한 개를 더 붙인 경우, n-2 경우에 두 개를 더 붙인 경우라고 가정하고 풀면 n의 경우가 나오게 되는 걸 알 수 있다. 실제로 n=4의 경우의 수를 그려보고 n=3과 n=2의 경우를 그려보고 막대기를 갖다댄다면 4의 경우수만큼 그릴 수 있다. import java.util.*; import java.io.*; public class Main { public static void..

dp는 규칙을 찾아서 간결하게 푸는 문제인데 정리능력이 부족한건지 집중력 부족인지 잘 해결하지 못했다. 다른 블로그 참조해서 보려고 해도 이해가 전혀 가지 않아서 찾고 찾다가 아주 쉽게 풀어놓은 블로그가 있어서 그걸 보고 겨우 이해했다. 간결하게 테이블로 규칙을 찾아서 하나씩 해보는 연습이 필요할듯 싶다. 기초문제이지만 멘탈을 엉망진창으로 만들 수 있다는 걸 보여준 사례... public static final int MOD = 1000000000; static int N, K; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..