빠르고 꾸준하게

자료구조 & 알고리즘/프로그래머스(programmers)

[programmers] 가장 큰 정사각형 찾기

https://programmers.co.kr/learn/courses/30/lessons/12905# 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 이 문제는 완전 탐색으로 풀 수도 있겠지만, 시간 초과를 피하기는 쉽지 않을 것 같습니다. 1000 * 1000 조건에다가 중복되는 연산들이 많기 때문이죠. 중복되는 연산이 있다? 그렇다면 생각해볼 수 있는게 다이나믹 프로그래밍(DP)이였습니다. 어쨌든 3 * 3 정사각형이 만들어지기 위해서는 2 * 2 정사각형이 만들어져야 가능했으니까요. DP로 생각해보면, 먼저 현재 위치가 [i][j]라고 했을 때, [i-1][j], [i][j-1], [i-1][..

글/개발

[개발] Pass By Value vs Pass By Reference 란?

최근 첫 기술면접을 봤습니다. 면접은 무조건 여러 번을 봐야 한다는 말을 새삼 느끼게 되더군요. 면접 질문 중에 Pass by value, Pass by reference에 대해서 아시나요? 가 있었습니다. 이번 기회에 대해 제대로 알아보려고 합니다. 0. 자바스크립트(Javascript)에서의 Primitive Type(원시 타입) vs Reference Type (참조 타입) 각 언어마다 변수를 넘겨주는 방법은 다양합니다. 먼저 자바스크립트에서는 원시 타입과 참조 타입이라는 두가지 자료형이 있습니다. 원시 타입은 숫자(Number), 불린(Boolean), undefined, 문자열(String), null 이렇게 5가지가 있습니다. 참조 타입에는 객체(Object), 배열(Array), 함수(Fun..

CS & Network/운영체제(OS) & 컴퓨터구조

[운영체제(OS)] 페이징(Paging), 세그멘테이션(Segmentation) 이란?

저번 시간까지는 메모리 관리 방법 중 페이징에 대해서 알아보았습니다. 간단하게 정리해볼까요? 프로세스를 일정 크기인 페이지 단위로 잘라서 메모리에 적재하는 방법을 페이징이라고 하는데요. 페이지는 일정한 간격으로 자르는 단위였습니다. 하지만 기준 없이 일정한 간격으로 자르는 페이징 말고도 기준을 세워서 논리적인 내용 단위인 세그먼트로 자를 수 있는 세그멘테이션 방법이 있습니다. 이번 시간에는 세그멘테이션에 대해서 알아보려고 합니다. 0. 세그멘테이션이란? 세그멘테이션은 하나의 프로세스를 세그먼트의 집합이라고 생각합니다. 세그먼트란? 네트워크TCP/IP 4 계층을 공부할 때도 세그먼트라는 단어가 사용되었었는데요. 전송 계층에서 신뢰할 수 있는 통신을 구현하기 위해 header를 위에서 받은 데이터에 붙입니..

자료구조 & 알고리즘/백준(Baekjoon)

[백준]11404(파이썬) - 플로이드

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제는 제목을 읽으면 바로 떠오르는 풀이법이 하나 있죠. 바로 플로이드 워셜입니다. 플로이드 워셜은 다익스트라 알고리즘과 함께 최단거리를 계산하는 문제의 풀이법으로 유명한데요, 혹시 처음 들어보신분들은 아래 게시물을 한 번 읽고오시면 도움이 될 것 같습니다. 다익스트라 알고리즘(Dijkstra Algorithm)(feat.힙(heap)) 다익스트라 알고리즘 최단경로 알고리즘으로 특정 노드에서 ..