LimeCoding

위상 정렬이란?(What is Topological Sorting?) 위상 정렬의 뜻을 검색해보면 "DAG에 대한 위상 정렬은 정점 u에서 정점 v로 가는 방향이 있는 간선이 있을 때 모든 정점 u가 모든 정점 v 앞에 오도록 정점을 정렬하는 선형 정렬"이라고 나온다. 이 말이 쉽게 와닿지 않을 수 있다. 하지만 게임의 테크트리를 생각하면 어떤 말인지 쉽게 알 수 있다.  우리가 게임을 하다보면 어떤 기술을 열거나 건물을 건설할 때 요구 조건이 있는 것을 한번쯤은 봤을 것이다. 그리고 요구 조건을 충족할 때만 기술을 열거나 건물을 건설할 수 있다. 이때 각 건물과 기술들이 정점이 되는 것이고 요구 조건과 관련된 건물과 기술의 관계가 간선이라고 생각하면 된다.  그런데 위상 정렬 앞에 DAG란 조건이 붙어..

Assert 키워드란? 우리는 간단한 프로그램을 만들 때도 다양한 버그와 에러를 보게 된다. 예를 들어 입자 가속기 안에 있는 입자들의 속도를 구하는 프로그램을 만들었다고 해보자. 이 프로그램을 통해 입자의 속도를 측정했을 때 30만 km/s가 나온다면 이건 올바른 결과일까? 컴퓨터 내부에서는 계산을 통해 나올 수 있는 값이지만 논리적으로는 어떤 물체든 빛의 속도인 30만 km/s를 넘을 수 없다. 이와 같은 프로그램의 논리적 오류를 잡아내기 위해 사용하는 키워드가 바로 Assert 키워드이다. Assert 키워드는 JDK 1.4버전에서 처음으로 등장했다. 이 키워드는 내가 참이라고 생각하는 결과가 정말 참인지를 검증할 때 사용할 수 있다. 만약 참이면 문제가 없지만 거짓일 경우 AssertionErro..

이분 검색이란?(What is binary search?) 이전 포스팅에서 작성한 순차 검색은 최대 n이라는 시간이 걸리는 검색 방법이다. 그렇기에 n이 100만, 1000만이 되면 검색하는데 상당히 많은 시간이 소요된다. 이를 해결하기 위한 알고리즘이 바로 이분 검색이다. 이분 검색은 대표적인 분할 정복 알고리즘이다. 이러한 분할 정복 알고리즘은 반복문으로 고쳐주면 더 빠른 성능을 낼 수 있다. 이분 검색의 작동 방식은 다음과 같다. 배열의 중간 요소와 찾고자하는 값을 비교한다. 이때 찾고자하는 값이 배열의 중간 요소이면 값을 리턴하고 종료한다. 배열을 반으로 나눈다. 중간 요소를 기준으로 찾는 값이 작으면 왼쪽 배열을, 크면 오른쪽 배열을 탐색한다. 1~3을 반복한다. 이분 검색 알고리즘(Binary..

문제는 다음 링크를 통해 볼 수 있다. 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 풀이 이번 문제는 DP 문제이다. 문제에서 주어진 조건은 다음과 같다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 이번 문제에서 중요한 조건은 바로 2번 조건이다. 연속으로 3잔을 마실 수 없기 때문에 이 부분을 고려해야 한다. 먼저 와인이 1잔이 있을 때를 생각해보자. 와인이 1잔만 있다면 한잔을 마..

주말에 적을 예정이다

주말에 적을 예정이다.

이 부분은 주말에 추가적으로 적을 예정이다.

이번에 김영한님의 QueryDSL, JPA, Spring basic을 모두 수강한 기념으로 갑자기 생각난 아이디어로 사이드 프로젝트를 진행해 보려고 한다. 아마 계속 사이드 프로젝트에 대해 포스팅할거지만 현재 노션을 이용해 프로젝트를 진행해 보려고 하기 때문에 포스팅 속도가 느릴 수 있을 것 같다. 일단 오늘은 대략적인 개요를 만들어 봤다. 서평 및 독서 모임 서비스(가칭 책고라) 서비스 기획 배경 보통 혼자 책을 읽고 끝내는 경우가 많다. 그러나 학교 수업 중 독서 토론 수업에서 각자 책을 읽고 생각을 나누는 과정에서 내가 생각하지 못한 굉장히 다양하고 재미있는 생각들이 있다는 것을 알았다. 이후 독서 모임을 찾던 중에 “독서” 보단 “모임”에 치중되어 있다는 생각이 들었다. 그래서 마치 게임 매칭처럼..

지하철 창문 비가 추적추적 내리는 날 지하철을 타고 출근하는 난 창문을 통해 세상을 본다 달리는 지하철 창문에는 날카로운 칼자국이 하나 둘 그어진다 지하철이 멈추자 칼자국이 눈물로 변한다 오래묵은 사람들은 내리고 새로운 사람들이 들어온다 달리는 지하철 창문에는 다시 날카로운 칼자국이 하나 둘 그어진다 잔인한 세상 보지 말라며 창문을 흐린다 세상이 흐려진다 그 잔인한 세상이 궁금해 작은 글씨를 새겨 틈새로 세상을 다시 본다 2024-03-26 지하철 타면서 든 생각이다. 나에 대한 고민할 시간도 주지 않는다. 고민하면 도태, 일단 고르면 빠져나올 수 없는 늪. 정말 극단적인 세상이다. 누군가는 아니라고 할 수 있겠지만 지금까지 내가 겪어온 세상은 그런 것 같다. 그런데 계속 세상에 기대를 건다. "어딘가에..

문제는 다음 링크를 통해 볼 수 있다 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 풀이 이번 문제는 dfs문제이다 익은 토마토가 있는 위치에서 위, 아래, 왼쪽, 오른쪽, 앞, 뒤중 익지 않은 토마토를 찾아 익은 토마토로 바꿔주면 되는 문제이다. 간단한 순서는 다음과 같다. 현재 익은 토마토의 위치를 큐에 모두 저장한다 큐의 사이즈를 저장한다 큐에서 익은 토마토 위치 하나를 꺼내고 해당 위치로부터 익힐 수 있는 토마토의 위치를 큐에 넣고 익은 토마토로 변경한다. 3번을 2에서 ..