재원블로그 재원블로그

이 문제는 완전 탐색을 이용해서 풀었다. 처음에는 정말 온전히 완전 탐색을 이용해서 구현했다. 하지만 정답은 나오나 시간 초과가 떴다. 조금만 생각해보면 시간을 완전히 줄일 수 있다. N * N 체스판에 N개의 퀸을 놓는다. 퀸은 가로, 세로, 대각선 전체를 이동할 수 있기 때문에, N * N 체스판에 N개의 퀸을 놓으려면 모든 행에 하나씩 퀸이 있는 모습일 것이다. 이 점을 이용하면 시간을 굉장히 많이 줄일 수 있다. class Solution { int N; int[][] board; int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1}; int[] dx = {0, -1, -1, -1, 0, 1, 1, 1}; public int solution(int n) { N = n; board ..

이 문제는 스택을 이용해서 풀었다. 1부터 s 길이 - 1 까지의 부분 문자열 길이를 정하고, 그 부분 문자열에 대한 압축 연산을 수행하여 길이를 찾아내는 방식이다. 입력 s의 길이가 최대 1,000 이므로, O(n^2) 이하 알고리즘까지도 가능하다. 한 가지 주의할 점은 압축 후 마지막에 길이를 계산할 때, 10 이상의 count를 가진 경우 10은 두 자리 수이므로 2를 result에 더해줘야 한다. 이를 위해 String.valueOf() 를 통해 String으로 변환 후 length를 더해주는 것으로 정답을 구했다.= import java.util.*; import java.io.*; class Solution { final Stack st = new Stack(); public int solut..

이 문제는 구현 문제이다. 배열의 최대 크기가 100 x 100 이고, bulid_frame으로 주어지는 최대 길이가 1,000 이므로 최악으로 연산해도 1,000만이기 때문에 시간 초과가 나지 않는다. 문제에서 주어진 요구사항을 그대로 구현하면 된다. 기둥 요구사항 - 바닥 위 - 보의 한쪽 끝 부분 위 - 다른 기둥 위 보 요구사항 - 한쪽 끝 부분이 기둥 위 - 양쪽 끝 부분이 다른 보와 동시 연결 주의할 점은 유효성 검증에서 x - 1 부분을 가져올 때 x == 0 인 경우에는 런타임 에러가 나게 된다는 점이다. 이 부분에서는 요구사항에 따라 특이 케이스로 분리하면 정답이 나오게 된다. import java.util.*; import java.io.*; class Solution { static ..

이 문제는 누적 합을 이용해서 풀었다. 누적 합은 길이가 n인 arr 배열이 있다고 했을 때 sum[i] = arr[0....i] 까지의 합 으로 정의하여 구간 합을 빠르게 구하기 위한 테크닉이다. 누적 합을 이용한 테크닉이 하나 있는데 만약 i 부터 j 까지 전부 1을 더하고 싶을 경우 반복문으로 하는 것이 아닌 arr[i]++, arr[j + 1]-- 을 적용하고 나중에 일괄적으로 누적 합을 계산하면 원하는 결과가 나오는 방법이 있다. 이 방법을 사용하면 반복문으로 매번 하는 것보다 시간 복잡도가 많이 개선된다. 매 루프마다 정해진 구간에 반복문을 수행하는 게 아닌 나중에 일괄적으로 처리할 수 있기 때문이다. 이 문제 또한 이 방법을 생각하는 것이 핵심이었다. 그러나 이 방법으로 정답이 나오지 않아 ..

이 문제는 다이나믹 프로그래밍을 사용해서 풀었다. 다이나믹 프로그래밍을 사용하는 전형적인 문제이다. 요구사항으로 map이 1인 경우에는 차가 못 지나가고, 2인 경우에는 회전이 불가능하다. 2인 경우에는 매개변수로 주어지는 direction을 그대로 가져가면서 재귀 호출하면 간단하게 해결할 수 있다. import java.util.*; import java.io.*; class Solution { static final int MOD = 20170805; static final int RIGHT = 0; static final int DOWN = 1; int[][] map; int Y; int X; int[] dy = {0, 1}; int[] dx = {1, 0}; int[][][] dp = new in..

이 문제는 이진 트리의 탐색을 이용한 문제이다. 2차원 좌표로 점들이 주어지고, 이들을 이진 트리로 간주하여 전위, 후위 순회 결과를 찾는 문제이다. 중요한 점은 x좌표가 같은 것이 하나도 없다는 사실이다. 또한 이진 트리를 중위 순회하면 오름차순으로 정렬된다는 사실도 굉장히 중요하다. 이를 이용하면 x좌표로 오름차순 정렬한 노드들의 순서가 곧 중위 순회한 결과를 나타내게 된다. 그러면 문제가 중위 순회 결과가 주어졌을 때, 전위 및 후위 순회의 결과를 나타내는 문제로 바뀌게 된다. 일정 구간 안에서 가장 y좌표가 높은 노드가 루트임을 이용하여 문제를 쉽게 풀 수 있었다. import java.util.*; import java.io.*; class Solution { Node[] inorder; Lis..

이 문제는 그리디 알고리즘을 이용해서 풀었다. scores의 길이 범위가 [1, 100,000] 이므로 O(N log N) 이하의 알고리즘을 생각해야 한다. 나의 경우에는 근무 점수를 기준으로 내림차순, 같을 경우 동료 점수 기준으로 내림차순으로 정렬했다. 그 후 delete() 메소드를 통해 기준 미달인 사원을 추출하고, rank() 메소드를 통해 완호의 등수를 매기고 리턴한다. delete 메소드가 굉장히 중요한데, 기본 아이디어는 high라는 변수를 정하고 list를 순회하면서 동료 점수가 더 낮은 경우 삭제하고 만약 높다면 high에 새로 저장하는 것이다. 여기서 주의할 점은 점수에 중복이 가능하여 분기문이 추가된다는 것이다. 만약 입력이 [[4, 0], [2, 3], [4, 4], [2, 6]]..

## 너무 쉬운건 제외하고 헷갈릴 만한 부분만 추림 1장 - 자바 시작 - .java 파일 (소스 코드) -> .class 파일 (바이트 코드) - 컴파일 방식 - .class 파일 -> JVM 적재 - 인터프리터 방식 - JVM은 필요할 때 클래스 파일 로딩 -> 링크 과정이 없음 - JDK (Java Development Kit) : 개발에 필요한 자바 도구 모음 - JRE (Java Runtime Environment) : 자바 실행에 필요한 API 포함 - Java SE : 표준 배포판 - 데스크탑, 서버 응용 개발 플랫폼 - Java ME : 마이크로 배포판 - SE + 임베디드 개발에 필요한 API - Java EE : 기업용 배포판 - SE + 인터넷 기반 서버사이드 컴퓨팅 API 추가 2장..