코린이의 소소한 공부노트

2차원 평면 위의 점 N개가 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. - 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) - 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 2. 출력 - 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 3. 예제 4. 코드 import java.io.*; import java.util.*; class Main{ public static void main(String[] args) throws IOException{ Bu..

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오. 1. 입력 - 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. - 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) - 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. 2. 출력 - 첫째 줄부터 N개의 줄에 점을 정렬한 결과를 출력한다. 3. 예제 4. 코드 import java.io.*; import java.util.*; class Main{ public static void main(String[] args) throws IOException{ Bu..

1. 개념 정리 1) 이진 인덱스 구조를 활용하여 구간 합 문제를 효과적으로 해결해 줄 수 있는 자료구조 2) 펜윅 트리(Fenwick Tree)라고도 불린다. 3) 세그먼트 트리보다 구현하기 편하고 속도가 빠르다. - 세그먼트 트리는 필요한 리프 노드만 채우기 때문에 불완전 트리지만, 인덱스 트리는 리프 노드를 모두 채워서 만들기 때문에 인덱스를 활용할 수 있다. - 데이터의 개수가 N개일 때, 세그먼트 트리를 만들기 위해 필요한 공간을 통상 4*N만큼 준비했었다면 인덱스 트리를 만들 때는 N만큼만 준비하면 된다. 4) 인덱스는 1부터 사용하고, 인덱스를 활용하면 해당 인덱스의 값이 몇 개의 데이터의 합인지 알 수 있다. - 8비트로만 간단히 예시를 들어보면, 3과 -3을 비트 and 연산을 해보면 다..

1. Input 1) int[] height - height[i] == i번째 위치의 벽의 높이 - 벽의 간격과 두께는 모두 1이다. 2. Output 1) 두 벽을 골라 물을 채울 때 가장 많이 채울 수 있는 물의 양을 반환 3. Constraint 1) n == height.length 2) 2

1. Input 1) int[] nums 2. Output 1) nums의 부분 배열에서 요소 1개를 삭제했을 때 1로만 이루어진 가장 긴 부분 배열의 길이를 반환 2) 그런 배열이 없다면 0을 반환 3. Constraint 1) 1 Output: 5 Input: nums = [1,1,1] -> Output: 2 설명: - [0, 3] 구간의 부분 배열에서 2번째를 삭제하면 [1,1,1]이 된다. - [1, 6] 구간의 부분 배열에서 4번째를 삭제하면 [1,1,1,1,1]이 된다. - [0, 2] 구간의 부분 배열에서 아무거나 1개 삭제하면 [1,1]이 된다. 5. Code class Solution { public int longestSubarray(int[] nums) { int max = 0; fo..

1. Problem - 주어진 트리에서 두 노드 node1, node2의 최소 공통 조상을 찾아보자. - 최소 공통 조상(Lowest Common Ancestor, LCA)는 특정한 두 노드의 공통된 조상 중 가장 가까운 조상을 말한다. - 이진 트리가 아니어도 적용되는 알고리즘이다. - 다이나믹 프로그래밍을 이용하는 알고리즘이다. 2. Input 1) int[][] graph - graph[i][j]: i는 j의 부모 노드 2) int n - 노드의 개수 3) int node1 4) int node2 3. Output 1) node1과 node2의 최소 공통 조상 4. Explanation 1) 트리에 있는 모든 노드에 대해서 각 노드의 깊이(depth)를 구한다. 2) 모든 노드에 대해서 각 노드의 ..

1. Input 1) String s 2. Output 1) s의 부분 문자열 중에서 같은 문자가 없는 가장 긴 부분 문자열의 길이를 반환 3. Constraint 1) 0 Output: 1 Input: s = "pwwkew" -> Output: 3 5. Code 1) 첫 코드 import java.util.*; class Solution { public int lengthOfLongestSubstring(String s) { int answer = 0; for(int i=0 ; i

1. Input 1) ListNode l1 - 첫 번째 숫자를 일의자리부터 거꾸로 나타낸 ListNode 2) ListNode l2 - 두 번째 숫자를 일의자리부터 거꾸로 나타낸 ListNode 2. Output 1) 첫 번째 숫자와 두 번째 숫자의 합을 일의자리부터 거꾸로 나타낸 ListNode를 반환 3. Constraint 1) 각 linked list의 노드 수의 범위는 [1, 100]이다. 2) 0 Output: [8,9,9,9,0,0,0,1] 설명: - 342 + 465 = 807 - 9,999,999 + 9,999 = 10,009,998 5. Code /** * Definition for singly-linked list. * public class ListNode { * int val; *..

1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 1. Input, Output, Example - n × n 배열에 1부터 n^2 까지 정수를 인덱스 [0][0]부터 시계방향 나선형으로 배치한 이차원 배열을 반환 2. Constraint 1) 1 ≤ n ≤ 30 3. Code class Solution { public int[][] solution(int n) { int[][] ans = new int[n][n]; int number = 1, x = 0, y = 0, change = 0; while(number

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 한다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 한다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있다. 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸이다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있다. 집어 올린 인형은 바구니에 쌓이게 되는 데, 이때 바구니의 가장 아래 칸부터 인형이 순서대로 쌓이게 된다. 다음 그림은..