리주의 프로그래밍 공부

우연히 문제를 알게 돼서 시도하다보니, 골드2 문제였다.. 난이도 보고 포기할까 싶었지만, 이왕 시작한거 끝을 보자는 마인드로 풀어냈다. (참고로 제출수가 적은 탓에 구글링해도 풀이가 다른 문제에 비해 많이 없다.) 접근방법 두 수를 받아서 한번에 풀라고 하지 않았다. 하나의 수에 대해 0~9까지 몇개히 문제를 알게 돼서 시도하다보니, 골드2 문제였다.. 난이도 보고 포기할까 싶었지만, 이왕 시작한거 끝을 보자는 마인드로 풀어냈다. (참고로 제출수가 적은 탓에 구글링해도 풀이가 다른 문제에 비해 많이 없다.) 접근방법 두 수를 받아서 한번에 풀라고 하지 않았다. 하나의 수에 대해 작거나 같은 모든 정수의 각 자리의 합을 구하는 함수를 작성한 뒤에, 그 함수를 두 번 호출해서 풀었다. (문제를 쪼개서 생각..

트리 문제를 풀기 위한 기본적인 틀, Node와 Tree 작성을 익히기 위해서 어제에 이어 트리 문제를 한번 더 풀었다. 이 문제에서 어려웠던 점은.. 입력을 마치는 방법이었다. 그건 검색을 통해서 Ctrl + z로 입력을 마칠 수 있다고 찾았다. Node와 Tree의 기본적인 생성을 마치고, 키 값이 들어오면 root부터 시작해서 작으면 왼쪽, 갈 곳이 없으면 왼쪽 노드로 생성 크면 오른쪽, 갈 곳이 없으면 오른쪽 노드로 생성 이라는 간단한 원리로 문제를 풀 수 있었다. import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import ..

기본적인 트리 문제였다. 하지만 제일 먼저 떠오른건 이차원 배열로 푸는 방법... 트리를 구현해서 다시 풀어봐야겠다. import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // [][0] : 왼쪽 자식 노드, [][1] : 오른쪽 자식 노드 int[][] arr = new int[n][2]; for(int i=0; i

Arrays.sort는 최악의 경우, 시간 복잡도가 O(n^2)이라 사용하지 않았는데, 다른 사람들의 풀이를 보니, 이 문제에서는 사용해도 됐던 것 같다. (Collections.sort는 Timsort를 사용하여 최악의 경우에도 O(n logn)을 보장한다. insert sort와 merge sort를 섞어쓴다고 한다.) + (Arrays.sort는 형에 따라 쓰는 알고리즘이 달라서 시간복잡도가 다르다고 한다. int형으로 쓴다면, 자바는 Quicksort를 사용해서 최악의 경우 O(n^2)을 가지고, Integer형으로 쓴다면, Mergesort로 O(n logn)을 가진다고 한다. 그렇다면 이 문제에서도 Integer로 쓴다면 걱정없이 Arrays.sort를 쓸 수 있을듯 하다.) 간단한 문제였음에..

방금 전에 올린 N과 M(2) 문제에서 하나만 수정하면 바로 맞추는 문제였다. (혹시나 15650 N과 M(2)를 풀지 않았다면 그거먼저 풀고오면 도움이 될듯하다.) [15650] N과 M (2) 다시 풀어보는 백트래킹 문제. 아직까지도 완벽히 숙지하지 못한 것 같다. (바로 N과 M 다른문제 풀러가야지) 우선 이 문제는 visited 배열이 필요가 없다. 왜냐하면 재귀적으로 호출할 때, +1을 해 leezu-prog.tistory.com dfs를 호출할 때, i+1에서 i로만 바꿔주면 된다. 이유는 중복가능하기 때문이다. 비내림차순은 dfs를 아래서부터 시작하면 자연스레 따라온다. import java.io.BufferedWriter; import java.io.IOException; import ja..

다시 풀어보는 백트래킹 문제. 아직까지도 완벽히 숙지하지 못한 것 같다. (바로 N과 M 다른문제 풀러가야지) 우선 이 문제는 visited 배열이 필요가 없다. 왜냐하면 재귀적으로 호출할 때, +1을 해주면 앞에 적힌 수보다 자연스레 커지기 때문이다. 그래서 방문 확인용 배열이 필요가 없다! 중복 체크할 이유가 사라지기 때문이다. 나는 이거를 다른사람이 설명해줄 때에도 이해하는데 꽤나 어려움을 겪었다ㅠㅠ.. (그래도 확실히 해놔야 다른 백트래킹 문제를 풀어볼 수 있으리라 생각했기 때문이다.) import java.io.BufferedWriter; import java.io.IOException; import java.io.OutputStreamWriter; import java.util.Scanner;..

얼핏 보면 2차원배열로 퀸을 놓으면 안되는 자리만 체크해주면 쉽게 풀릴듯하다. 그렇게 보고 푸는 아이디어만 생각하고 검색을 해봤다. 그런데... 다들 1차원 배열로 풀었다. 2차원으로 풀면 시간초과가 난다고... 그래서 다른 사람들의 풀이를 참고하였다. import java.io.IOException; import java.util.Scanner; public class Main { static int n; static int result = 0; static int[] map; public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); n = sc.nextInt(); map = new in..