CS/OS
[운영체제/OS] Blocking / NonBlocking, Sync / Async
0. 들어가면서 이번 포스팅에서는 Blocking/Non-Blocking(블록킹, 논블록킹)과 Sync/Async(동기, 비동기) 개념에 대해 정리해보고, 각각의 개념이 어떻게 쓰이는지를 정리해보려고 합니다. 아래 두 영상에서 이 개념들을 정말 잘 설명해주신 것 같아서 해당 영상을 참고해서 정리했습니다. 꼭 한 번 시청해보세요! 멍토의 Blocking vs Non-Blocking, Sync vs Async 우의 Block vs Non-Block & Sync vs Async 1. Blocking, Non-Blocking, Sync, Async 먼저 Blocking, Non-Blocking, Sync, Async 네 가지 개념에 대해 이해해보겠습니다. Blocking: 다른 작업을 하는동안 자신의 작업에 ..
Java & Kotlin
[Java] LinkedList, ArrayList를 구현하는 방식과 이에 따른 성능 비교해보기
0. 들어가면서 LinkedList, ArrayList는 자바 List 인터페이스를 구현한 클래스들입니다. 그리고 List 인터페이스는 Collection를 구현하고 있고, Collection는 최상위의 Iterable을 구현하고 있습니다. 이러한 계층 구조의 상속과 분리는 특정 클래스들의 공통점과 차이점으로 인한 결과라고 볼 수 있는데요. 이번 시간에 살펴볼 ArrayList, LinkedList 역시 List를 구현한 클래스들로 보면 공통점이 있지만, 서로 분리된 클래스라는 점에서는 분명 차이점이 존재하는 클래스들입니다. 그래서 이번 포스팅에서는 ArrayList와 LinkedList에 대해 정리해보고 각각의 클래스가 어떤 상황에서 사용하기 적합한지 직접 성능을 테스트해보려고 합니다. 1. Array..
Algorithm
[BOJ] 백준 12100 2048(Easy) - Python/Java
문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 해설 배열의 회전이나 변환, 슬라이싱을 얼마나 잘할 수 있는지를 보는 문제 같았습니다. 문제에서 요구하는 시뮬레이션 상황을 구현하기 위해서는 배열의 원소들을 상하좌우로 미는 함수를 구현해야 하는데요. 배열을 적절히 인덱싱해서 상하좌우에 해당하는 함수를 각각 구현할 수도 있지만, 저는 왼쪽으로 미는 함수 하나만 구현해놓고 배열의 전치(Transpose)와 대칭(Mi..
Algorithm
[BOJ] 백준 16973 직사각형 탈출 - Python/Java
문제 https://www.acmicpc.net/problem/16973 16973번: 직사각형 탈출 크기가 N×M인 격자판에 크기가 H×W인 직사각형이 놓여 있다. 격자판은 크기가 1×1인 칸으로 나누어져 있다. 격자판의 가장 왼쪽 위 칸은 (1, 1), 가장 오른쪽 아래 칸은 (N, M)이다. 직사각형의 가장 www.acmicpc.net 해설 일반적인 너비우선탐색(BFS) 문제가 약간 변형된 문제입니다. 보통 격자점이 주어지고 너비 우선 탐색을 하는 문제에서는 이동(탐색)하는 주체가 단위 격자점의 크기와 동일한데요. 이 문제에서는 격자점의 일부를 이루는 직사각형이 이동(탐색)을 하는 주체로 설정된 것입니다. 따라서 기존의 BFS 문제를 풀 때와 달리 아래와 같이 고민해야 하는 부분이 생깁니다. 1) ..
Algorithm
[BOJ] 백준 15681 트리와 쿼리 - Python/Java
문제 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 해설 해당 문제의 해설은 문제에서 주어지는 [힌트] 부분에 상세하게 제시되어 있어서 이 내용을 따라서 구현하기만 하면 정답을 구할 수 있습니다. 그래도 간단하게나마 제 해설을 적어보겠습니다. 1. 이 문제에서는 노드들을 그래프 형태로 입력받은 뒤, 트리의 루트 노드가 주어지기 때문에 루트를 기준으로 DFS를 수행하면 트리 구조를 ..
Algorithm
[BOJ] 백준 2482 색상환 - Python/Java
문제 https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net 해설 이 문제에서 중요한 조건은 색상들이 "원형"으로 놓여져있다는 것인데요. 원형 배열에서는 맨 앞의 원소와 맨 마지막 원소가 서로 인접해있기 때문에, 이 둘의 관계를 적절히 처리해주는 것이 문제를 푸는데 핵심적인 열쇠가 됩니다. 저는 이 문제를 해결하기 위해 다음의 두 케이스를 나누어 생각하고, 두 케이스에서 구한 답을 총 경우의 수에 더해서 정답을 냈는데요(원형 배열에서 아래와 같이 두 가지 케이스로 나누어 문..
Algorithm
[BOJ] 백준 1013 Contact - Python/Java
문제 https://www.acmicpc.net/problem/1013 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 해설 이 문제의 포인트는 정규표현식 (100+1+ | 01)+ 을 통해 앞에서부터 문자열 매칭을 시도하면 '틀린다'는 것입니다. 그 이유는 기본적으로 Greedy한 선택이 이 문제의 정답을 보장하지 않기 때문인데요. 예를 들어 100011001 이라는 문자열을 보겠습니다. 정규표현식을 통해 앞에서부터 최대한 많은 문자열을 매칭시키면 아래와 같은 결과가 나옵니다. [정규표현식 이용]..
Java & Kotlin
[Java] 제네릭(Generics)에 대해 생각해보기
0. 들어가면서 이번 포스팅에서는 자바 제네릭(Generic)에 대한 기본적인 내용부터 제가 궁금했던 부분들이나 고민해보면 좋을 부분들을 정리하려고 합니다. 제네릭은 공부할수록 범위도 많고 제대로 쓰는 것이 정말 어렵겠구나를 느껴서 차근차근 더 공부를 해야 할 것 같긴 합니다. 우선 시작해보겠습니다. 1. 제네릭을 쓰는 이유 제네릭(Generic)은 JDK 1.5 버전에 처음 도입된 기능으로 객체의 타입 안정성을 높여주고 형변환의 번거로움을 덜어주었습니다. 이 말의 의미를 직접 느껴보기 위해 아래 코드를 보겠습니다. 우선 저는 인텔리제이 IDE를 쓰고 있는데, IDE는 위처럼 ArrayList라는 현재 제네릭 클래스로 정의된 클래스에 대해 제네릭을 선언해주지 않으면 노란 밑줄을 그어줍니다. 제네릭을 써야..
Algorithm
[BOJ] 백준 2533 사회망 서비스(SNS) - Python/Java
문제 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 해설 트리에서의 DP를 이용해서 해결할 수 있는 문제입니다. 일반적으로 일차원 배열이나, 이차원 배열에 관한 DP를 풀 때는 반복문을 순회하면서 이전값을 현재값을 구하는 데 활용하는데요. 트리는 이러한 구조가 현재 노드와 자식 노드가 갖는 서브트리로 치환되어 나타난다는 점에서만 그 형태가 다르다고 볼 수 있습니다. 따라서, 기본적으로 트리를 활용한 DP를 적용하기 위해서는 DFS 탐색을..
Spring & Springboot
@OneToMany 관계에서 Fetch Join의 사용과 페이징 처리 문제
1. 상황 회원(Member)과 주문(Orders), 주문상품(OrderItem), 상품(Item)이라는 네 개의 엔티티를 중심으로 @OneToMany 관계에서 Fetch Join의 사용과 페이징 처리 문제에 대해 다뤄보겠습니다. 우선 간단한 엔티티 설계와 요구사항을 살펴보겠습니다. 회원(Member)은 여러 주문(Orders)을 가질 수 있으며, 하나의 주문(Orders)은 여러 개의 주문상품(OrderItem)을 가질 수 있습니다. 주문상품은 해당 상품의 수량과 가격을 가지고 있는 엔티티이며, 상품은 단순히 상품 정보만을 가진 엔티티입니다. 하나의 상품(Item)이 여러 주문상품(OrderItem)에 나타날 수 있으며, 주문상품을 통해 상품을 조회하기 때문에 단방향 연관관계를 갖습니다. 그리고 아래는..
