본문 바로가기

분류 전체보기

 (86)
[Lecture 16] Automatic Memory Management / 가비지 컬렉션 #Automatic Memory Management 명시적(explicit) 메모리 관리(예: malloc() 및 free()를 통한)는 오류가 발생하기 쉽다. 이에 반해, 대부분의 현대 언어들은 자동 메모리 관리또는 가비지 컬렉션이라고도 불리는 "암묵적 메모리 관리" 형태를 제공한다 명시적 메모리 관리는 복잡하며, 다양한 오류가 발생할 수 있다: 메모리를 너무 일찍 해제하면 use-after-free 오류가 발생할 수 있다. 메모리 해제를 너무 늦게 하거나 전혀 하지 않으면, 메모리 누수(leak)의 위험이 있다. 자동 메모리 관리 시스템은 객체의 소유권과 수명을 식별하는 원칙적인 설계를 필요로 한다. 이는 API 설계를 복잡하게 만들 수 있으나, 프로그래밍에서 발생할 수 있는 여러 문제들(메모리 누수..
[Easy] 226. Invert Binary Tree / 구글 코딩 테스트 기출 문제 이번 문제는 구글 코딩 테스트로 굉장히 유명한 문제이다. 이 문제가 유명해진 데에는 한 가지 이유가 있다. 맥(Mac)을 사용하는 개발자라면 누구나 사용해 봤을 법한 Homebrew (MacOS 패키지 관리자)를 개발한 사람으로 유명한 Max Howell은 2015년 구글과 입사 면접을 보는데, 면접 문제에서 binary tree를 invert하는 문제가 나왔지만 결국 풀지 못해 면접에서 떨어지게 된다. 그 후에 Max Howell은 자신의 트위터에 "구글: 90%의 구글 엔지니어들은 네가 개발한 소프트웨어를 사용하지만, 너는 binary tree invert하는 것도 화이트보드에 풀지 못하기 때문에 꺼져라" 와 같은 글을 올리며 자신은 굉장히 많은 사람들이 사용하는 소프트웨어를 개발했지만 고작 코딩 테..
[Lecture 7] 멀티쓰레딩 - Introduction to Multithreading #멀티태스킹 우리가 새로운 게임이 출시되었을때, 게임웹사이트에 들어가 다운로드를 하는데 다운로드를 하는 동안 컴퓨터 전체가 멈춰있으면 어떨까? 오래전 컴퓨터들은 이러한 작업을 한번에 하나밖이 실행 하지 못했기 때문에, 여러작업을 동시에하는 현대 컴퓨터와는 달리 굉장히 불편했다. 하지만 현재 컴퓨터들은 프로세스 여러개를 한번에 돌릴수 있기 때문에 이러한 불편함을 없앨 수 있었다. 바로 이렇게 컴퓨터가 여러개의 프로세스, 작업을 동시에 여러 개 실행하는 것이 멀티 태스킹이다. CTRL - Shift - ESC를 눌러보면 얼마나 많은 프로세스들이 백그라운드에서 돌아가고 있는지 볼 수 있다. 여러 프로세스를 함께 실행시키는 작업은 동시적 (concurrency), 병렬적 (parallel), 또는 둘의 혼합으로..
[Lecture 9] 멀티쓰레딩 III - Semaphores / 세마포어 #식사하는 철학자 문제 / Dining philosophers problem위의 사진처럼, 5명의 철학자가 같이 식사를 하려고 모였다고 가정하자. 식탁에는 맛있는 스파게티가 올라와 있고, 각 스파게티 접시 사이에 포크가 하나 씩 있다. 하지만 이 모임에 있는 철학자들은 단순히 음식을 먹지 못한다. 이 철학자들이 음식을 먹기 위해선 다음과 같은 규칙을 따라야 한다.1. 일정 시간 생각을 한다.2. 왼쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.3. 오른쪽 포크가 사용 가능해질 때까지 대기한다. 만약 사용 가능하다면 집어든다.4. 만약 양쪽의 포크를 잡으면 일정 시간만큼 식사를 한다.5. 오른쪽 포크를 내려놓는다.6. 왼쪽 포크를 내려놓는다.7. 다시 1번으로 돌아가 반복한다.굉..
[Medium] 54. Spiral Matrix (Microsoft) #문제 설명 Leetcode 54번 문제는 m x n matrix 가 주어진다. matrix의 값은 1부터 n까지의 정수로 채워진다. 정수의 순서는 matrix에 나션형 모양으로 나열된다. 우리는 이 matrix를 나선형 (matrix[0][0] 에서 시작해서 오른쪽끝, 맨 아래, 맨 왼쪽, 위로를 matrix의 전체가 커버 될때까지 반복한다). 이 과정에서 각 index를 지날때마다, index에 있는 정수 값들을 list에 add해주면 된다, 그리고 그 list를 return해주면 된다. #문제 풀이 이 문제는 총 네가지 (오른쪽, 아래, 왼쪽, 위) traverse하는 경우가있기때문에, 그 index들을 tracking하는 variable를 만들고, 그 varible들 (matrix index)을 ..
[Medium] 973. K Closest Points to Origin (Facebook / Meta) #문제 설명 Leetcode 973번 문제는 x, y축 위의 좌표들이 배열로 주어지고, 정수 k가 주어진다. 이 문제에서는 (0,0) 에 가장 가까운 좌표 k개를 포함한 array를 return하는 문제이다. #문제 풀이 #풀이 1 class Solution{ public int[][] kClosest(int[][] points, int K) { Arrays.sort(points, (p1, p2) -> p1[0] * p1[0] + p1[1] * p1[1] - p2[0] * p2[0] - p2[1] * p2[1]); return Arrays.copyOfRange(points, 0, K); } } 모든 점을 원점까지의 거리에 따라 정렬한 다음 가장 가까운 상위 k개의 점을 얻는 풀이 이다. Time comp..
[Easy] 495. Teemo Attacking #문제 설명 Leetcode 495번은 리그 오브 레전드 캐릭터인 티모를 알고 있으면 이해하기 쉽다. 티모의 e 스킬은 티모가 상대 챔피언에게 평타를 때리면 평타를 때리면, 4초간 독 데미지를 상대에게 입힌다. 이 문제에서는 티모가 e스킬은 찍은 상태에서, 상대에게 평타를 치는 시간을 담은 배열과, 독 데미지의 지속시간이 주어진다 (실제 게임에서는 4초로 고정이지만). 또 한 가지 알아야 할것은 티모가 이미 독 데미지를 입은 상태의 상대에게 평타를 입힌다면, 독 데미지의 지속 시간은 리셋되고 상대는 다시 4초간 독데미지를 입어야한다. 예를 들어 티모가 2분40초에 평타를 입히고, 다시 2분 42초에 평타를 때리면 상대의 독데미지는 2분 46초에 끝날것이다. 이 문제는 주어진 배열과 독 데미지 지속 시간을..
[Medium] 378. Kth Smallest Element in a Sorted Matrix (아마존) #문제 설명 378번 문제는 정수 k와 n x n 정사각형 matrix가 주어지고, matrix의 각 칸에는 정수들이 담겨있다. 이 문제에서는 matrix안에서 정수 k번째로 작은 정수들을 전부 return해주면 된다. 예를 들어 [[1,5,9], [10,11,13] , [12,13,15]] 라는 2d 매트릭스가 주어지고 정수 k = 4가 주어지면, matrix안의 4번째로 작은 10을 return해주면 된다. #문제 풀이 class Solution { public int kthSmallest(int[][] matrix, int k) { PriorityQueue maxHeap = new PriorityQueue(Collections.reverseOrder()); for(int i = 0; i < matr..

티스토리툴바