CS/Algorithm
Leetcode - Validate Binary Search Tree
문제https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree - LeetCodeCan you solve this real interview question? Validate Binary Search Tree - Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: * The left subtree of a node contains only nodes with keys sleetcode.com 풀이root부터 시작하여 왼쪽 서브트리는 계속 작아져야 ..
CS/Algorithm
Leetcode - First Bad Version
문제https://leetcode.com/problems/first-bad-version/description/ First Bad Version - LeetCodeCan you solve this real interview question? First Bad Version - You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed baseleetcode.com 풀이먼저 n이 2^31 - 1 이하이기 때문에 오버플로우에 주의해야..
CS/Multicore & GPU
[Multicore] 효율적인 Matrix Multiplication - 멀티쓰레드와 캐시
0. Matrix Multiplication 아래는 N * N 크기의 행렬 A, B를 곱하여 그 결과인 N * N 행렬 C를 구하는 과정입니다. 결과로 나오는 C 행렬의 (i, j)번째 값을 계산하기 위해서는 위 그림처럼 A 행렬의 i번째 행과 B행렬의 j번째 열의 원소들을 곱해야 합니다. 위 과정을 코드로 보면 아래와 같으며 두 개의 N * N 행렬의 곱셈에 드는 시간 복잡도는 O(N^3)임을 알 수 있습니다. for i = 1 to n for j = 1 to n for k = 1 to n C(i, j) = C(i, j) + A(i, k) * B(k, j) 자, 그러면 위 연산을 어떻게 멀티쓰레딩을 통해 병렬로 처리할 수 있을까요? 앞으로 몇 가지 방법에 대해 소개를 할텐데, 각 방법이 동작하는 방식과..
CS/Multicore & GPU
[Multicore] 쓰레드의 Workload 관리와 Thread Pool에 대해
1. 쓰레드의 Workload 밸런스 8개의 쓰레드를 가지고 천 만개의 원소를 가진 배열의 각 원소에 대해 특정한 연산(더하기나 빼기 등)을 하는 작업을 한다고 해보겠습니다. 그러면 우리는 각 쓰레드에 10,000,000 / 8 = 1,250,000 개의 원소에 대한 연산을 할당하고, 쓰레드가 작업을 마치면 결과를 모아서 다음 과정을 이어나갈 수 있습니다. 하지만 실제 멀티쓰레드 환경은 언제나 위와 같이 각 쓰레드가 동일하거나 비슷한 수준의 작업량을 할당받는 보장이 없습니다. 어떤 쓰레드는 다른 쓰레드보다 훨씬 더 많은 작업을 처리해야 할 수 있고, 또 다른 쓰레드는 정말 적은 양의 작업을 마치고 다른 쓰레드들이 끝나길 기다려야 할 수 있죠. 위 그림은 시간에 따른 4개 쓰레드의 작업 진행 상황입니다. ..
CS/Multicore & GPU
[Multicore] Race Condition과 Locks
1. 들어가면서 멀티쓰레딩에서 Race Condition과 Lock은 가장 기초적이면서 중요한 개념입니다. 멀티쓰레딩이라는 개념을 단순하게 정의해봐도, 여러 개의 쓰레드가 공유되는 자원을 바탕으로 분산 처리를 하는 것이기 때문입니다. 그래서 이번 포스팅은 운영체제 시간에 배웠던 Race Condition과 Lock 개념을 되짚어보고, 코드를 통해 좀 더 구체적으로 공부해보려고 합니다. 먼저 아래는 Race Condition과 Lock의 정의입니다. [1] Race Condition A race condition occurs when two threads access a shared variable at the same time. The first thread reads the variable, and t..
CS/Algorithm
[BOJ] 백준 16929 Two dots - Python/Java
문제 https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 해설 이 문제에서 정의하는 싸이클을 판단하는 기준은 여러가지가 있는 것 같습니다. 저같은 경우에는 [1] '시작 노드와 연결된 간선(최대 4개)에 대해 동일한 간선을 이용하지 않고 다시 시작 노드로 돌아올 수 있다면, 싸이클이 형성된다' 라고 생각했습니다. 그런데 다른 분들의 풀이를 보니 [2] '시작 노드에 대해서는 방문 체크를 하지 않은 채 DFS 탐색을 하다가, 그 경로의 길이..
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: 다른 작업을 하는동안 자신의 작업에 ..
CS/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..
CS/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) ..
CS/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를 수행하면 트리 구조를 ..
