날짜: 2022년 5월 13일 오후 2:37 오답: o 코드 Algorithm/81305.py at main · Junroot/Algorithm 풀이 문제 해석을 다르게 해야되는 과정이 어려웠다. 모든 간선을 잘라보는 것은 당연히 시간초과가 발생한다. 각 그룹의 인원을 L명 이하로 만들기 위해서 몇 개의 그룹이 필요한지 구하는 문제로 바꾸고, 이 그룹의 수가 처음으로 k가되는 L을 바이너리 서치로 풀어야된다. L의 범위가 (총 인원/ k)~(총 인원) 사이라는 것을 알면 바이너리 서치로 접근할 수 있다. 1번 소문제를 해결하기 위해서 dfs를 이용했다....

날짜: 2022년 5월 3일 오후 5:57 오답: o 코드 Algorithm/81304.py at main · Junroot/Algorithm 풀이 처음에 문제를 이해하는데 시간이 걸렸다. 똑같은 함정 방에 돌아가면 모든 간선의 방향이 원래대로 돌아가는 문제로 이해했다. 현재 방문했던 함정방으로 비트마스크로 표현하는 것까지는 쉽게 접근했다. 하지만 n의 크기가 1000이여서 int 범위 밖의 비트마스크 표현에 문제가 있었다. 이부분은 함정방이 10개이하이므로 좌표 압축을 통해 해결했다. 현재 노드와 이동할 노드에 함정 활성화가 모두 켜저있거나 모두 꺼져있으면 정방향, 하나만 켜져있으면 역방향으로 이동하도록 구현했다....

날짜: 2022년 5월 2일 오후 5:05 코드 Algorithm/81303.py at main · Junroot/Algorithm 풀이 가장 최근에 삭제된 행을 복구하는 기능을 쉽게 구현하기 위해서 처음에는 array를 만들어 soft delete 와 형식으로 구현하려고 했다. 하지만, 이럴 경우 삭제된 행이 많을 때 행을 이동하면 soft delete되어있는 행은 이동한 것으로 간주하면 안되므로 계산량이 늘어나는 문제가 있었다. 이를 해결하기 위해서 LinkedList를 만들어서 문제를 해결했다.

날짜: 2022년 5월 2일 오후 5:01 코드 Algorithm/81302.py at main · Junroot/Algorithm 풀이 대기실의 크기가 5*5로 고정이고 대기실의 개수 또한 5개로 고정이므로 시간복잡도를 크게 고려하지 않아도 해결이 가능하다. 응시자가 앉아 있는 자리를 기준으로 BFS를 통해 길이가 2인 지점 이내에 다른 응시자가 있는지 확인한다.

날짜: 2022년 5월 2일 오후 4:59 코드 Algorithm/81301.py at main · Junroot/Algorithm 풀이 문자열의 길이가 최대 50이므로 어렵지 않다. 문자열을 하나씩 확인해서 숫자로 바꾸면 된다.

하나 이상의 처리 단계를 가진 경우에는 스퀀스를 사용하라 시퀀스 처리 함수들을 사용하면, 데코레이터 패턴으로 꾸며진 새로운 시퀀스가 리턴된다. 컬렉션 처리 연산은 호출할 때 연산이 이루어지는 반면, 시퀀스 처리 함수는 최종 연산이 이루어지기 전까지는 각 단계에서 연산이 일어나지 않는다. 시퀀스의 지연 처리 장점 자연스러운 처리 순서를 유지한다. 최소한만 연산한다. 무한 시퀀스 형태로 사용할 수 있다. 각각의 단계에서 컬렉션을 만들어 내지 않는다. 순서의 중요성 시퀀스 처리는 요소 하나하나에 지정한 연산을 한꺼번에 적용한다. element-by-element order 또는 lazy order라고 부른다....

단위 테스트에만 전적으로 의존하면 시스템이 전체적으로 잘 작동하는지 확신할 수 없다. 통합 테스트는 무엇인가? 통합 테스트의 역할 아래 단위 테스트 세 가지 요구 사항중 하나라도 충족하지 못하면 통합 테스트의 범주에 속한다. 단일 동작 단위를 검증하고, 빠르게 수행하고, 다른 테스트와 별도로 처리한다. 단위 테스트는 도메인 모델을 다루는 반면, 통합 테스트는 프로세스 외부 의존성과 도메인 모델을 연결하는 코드(컨트롤러)를 확인한다. 다시 보는 테스트 피라미드 통합 테스트는 유지비가 많이 든다. 프로세스 외부 의존성 운영이 필요함 관련된 협력자가 많아서 테스트가 비대해짐 단위 테스트로 가능한 한 많이 비즈니스 시나리오의 예외 상황을 확인하고, 통합 테스트는 주요 흐름(happy path)과 단위 테스트가 다루지 못하는 기타 예외 상황을 다룬다....

명세 작성자는 개발자가 명세를 읽도록 유도할 필요가 있다. 명세서를 읽도록 사람을 유인하는 방법은 일반적으로 글쓰기 실력과 밀접환 관련이 있다. 규칙1: 재밌게 씁시다 명세를 읽게 유도하는 규칙 1번은 즐거운 경험을 누리게 만드는 것이다. 규칙2: 명세를 쓰는 작업은 머리가 돌아가도록 코드를 쓰는 작업과 유사하다 명세를 쓸 때 놓치기 쉬운 점은, 올바른 작성을 물론이거니와 이해하기 쉽도록 작성해야 한다는 점이다. 사람은 우선 동기부여가 되지 않으면 타인이 말하려는 내용을 이해하려 하지 않는다. 무언가를 해석하기 보다는 단지 순서대로 읽고 이해하기를 원한다....

이전 장에서는 REST를 사용한 동기화 통신을 알아봤다. 비동기 메시징은 애플리케이션 간에 응답을 기다리지 않고 간접적으로 메시지를 전송하는 방법이다. JMS로 메시지 전송하기 JMS(Java Message Service): 두 개 이상의 클라이언트 간에 메시지 통신을 위한 공통 API를 정의하는 자바 표준 JMS가 나오기 전에는 메시지 브로커들이 각자 나름의 API를 갖고 있어서, 애플리케이션의 메시징 코드가 브로커 간에 호화되지 않았다. 메시지 브로커: 클라이언트 간에 메시지 통신을 중개하는 역할 JMS를 사용하면 이것을 준수하는 모든 궇녀 코드가 공통 인터페이스를 통해 함께 작동할 수 있다....

랜 카드에서의 데이터 전달과 처리 웹 브라우저에 URL을 입력하고 엔터키를 누르면 일어나는 과정 TCP 3-way 핸드셰이크가 일어난다. HTTP request 메시지를 만든다. 전송 계층으로 전달된다. TCP 헤더가 붙어서 출발지 포트 넘버, 목적지 포트 넘버 등이 추가된다. (세그먼트) 네트워크 계층으로 전달된다. IP 헤더가 붙어서 출발지 IP, 목적지 IP 주소 등이 추가된다. (IP 패킷) 데이터 링크 계층으로 전달된다. 이더넷 헤더와 트레일러가 붙어서 출발지 MAC, 목적지 MAC 주소 등이 추가된다.(이더넷 프레임) 물리 계층으로 넘어가서, 랜 카드가 전기 신호로 변환 시킨다....

고차 함수 고차 함수: 다른 함수를 인자로 받거나 함수를 반환하는 함수 함수 타입 코틀린의 타입 추론으로 인해 변수 타입을 지정하지 않아도 람다를 변수에 대입할 수 있다. 반환 타입이 널이 될 수 있는 타입 var canReturnNull: (Int, Int) -> Int? = { x, y -> null } 함수 타입 전체가 널일 될 수 있는 타입 var funOrNull: ((Int, Int) -> Int)? = null 함수 타입에서 파라미터 이름을 지정할 수도 있다. 타입 검사 시 무시되고, 파라미터 이름이 꼭 함수 타입 선언의 파라미터 일므과 일치하지 않지만, 코드 가독성이 좋아지고 IDE 코드 자동 완성을 사용할 수 있다....

가상 메모리의 개요 가상 메모리 시스템 가상 메모리(virtual memory): 크기가 다른 물리 메모리에서 일관되게 프로세스를 실행할 수 있는 기술. 가상 메모리 시스템의 모든 프로세스는 물리 메모리와 별개로 0번지부터 시작하는 연속된 메모리 공간을 가진다. 논리 주소 vs 가상 주소 논리 주소는 물리 메모리에 존재하는 위치의 주소를 프로세스 관점에서 지정하는 방식이다. 가상 주소는 물리 메모리 공간이 아닌 가상의 주소 공간을 가진다. 가상 메모리에서 메모리 관리자가 사용할 수 있는 메모리의 전체 크기는 물리 메모리와 스왑 영역을 합한 크기다....

날짜: 2022년 3월 11일 오후 11:20 코드 Algorithm/77486.py at main · Junroot/Algorithm 풀이 위상 정렬을 사용했다. 위상 정렬을 사용하기 위해서 멤버 이름으로 id를 찾거나 id로 이름을 찾아야되는 경우가 있어서, dictionary를 2개 사용했다. 위상 정렬로 수수료를 계산할 때 2가지 문제가 있었다. 현재 멤버의 수익의 10%를 그대로 부모 멤버에게 주면 오답이 된다. 자신의 자식 멤버에게서 받은 수수료를 각각 10%씩 구하고 일의자리 아래는 버림해야되기 때문에, 자식으로부터 받은 수수료를 바로 더하지 않고, 리스트로 관리해야됐다....

날짜: 2022년 3월 23일 오후 10:09 코드 Algorithm/77485.py at main · Junroot/Algorithm 풀이 시뮬레이션 문제기 때문에 복잡한 알고리즘은 필요없다. 나는 움직여야되는 방향이 같은 숫자끼리 묶어서 한번에 움직이도록 처리했다. 다른 사람 풀이 다른 사람 풀이를 보니 stack을 활용했다. 시계방향으로 숫자들을 stack에 넣으면서 stack의 제일뒤보다 한 칸앞의 숫자로 행렬의 값을 변경하면 시계방향으로 한 칸씩 이동한 모습이 된다. 최소값은 stack 내부의 최소값만 생각하면 되므로 훨씬 깔끔했다.

편집 시간: 2022년 2월 16일 오후 4:02 코드 Algorithm/7662.py at main · Junroot/Algorithm 풀이 실패한 풀이: Node 클래스 만들기 최대 힙과 최소 힙을 두 개 마련해두고, 삭제 될 때 해당 숫자가 삭제되었다고 표시만 하면되기 때문에, 힙의 각 노드들을 아래와 같이 클래스로 만들어 deleted 필드를 두려고했다. class Node: def __init__(self, data): self.data = data self.deleted = False 하지만 한 가지 문제가 있었다. heapq 라이브러리는 최대 힙을 만들 수 없다. 그래서 일반적인 힙 문제에서는 음수를 취하여 힙에 추가하는데 현재는 최소 힙과 최대 힙이 노드를 공유하고 있어야되기 때문에 불가능하다....

편집 시간: 2022년 3월 31일 오후 9:53 코드 Algorithm/7579.py at main · Junroot/Algorithm 풀이 처음에는 아래와 같은 방식으로 dp로 풀려고 했다. 아래에서 f(i, m)의 정의는 0번째부터 i번째까지 앱으로 메모리 m을 비우기위한 최소 cost를 뜻한다. $$ f(i, m) = min(f(i-1,m-m_i)+c_i,f(i-1,m)) $$ 하지만, m의 범위가 10,000,000 까지기때문에 이 방법을 사용할 수 없다. 그래서 i와 cost를 사용해서 dp로 접근해봤다. $$ f(i,c)=max(f(i-1,c-c_i)+m_i,f(i-1,c)) $$ c의 범위는 0에서 10000까지라서 최대 100 * 10000번 계산으로 계산할 수 있다....

편집 시간: 2022년 2월 9일 오후 6:43 코드 Algorithm/7576.py at main · Junroot/Algorithm 풀이 bfs를 이용해서 모든 토마토를 탐색하면 된다. 시간을 출력해야되기 때문에 큐에 시간 정보도 같이 저장했다. 다른 방법으로는 현재 큐에 담겨있는 값들을 같은 시간에 방문하는 토마토라고 해두고, 그 개수만큼만 루프를 돌면 주기가 한번 돌았다고 계산하면 된다. 모든 토마토가 익었는지 확인해기 위해서 마지막에 박스 전체를 확인해봐도 되고, 익지 않은 토마토의 개수를 카운팅해도 된다.

날짜: 2022년 6월 21일 오전 11:00 코드 Algorithm/72416.py at main · Junroot/Algorithm 풀이 DP를 이용해서 문제를 풀었다. 점화식을 구하는 과정이 이 문제의 가장 어려운 부분이다. get_min_cost(leader_index): leader_index의 하위 직원들의 최소 비용 리더를 워크샵에 참여 시키는 경우: 해당 리더가 팀장으로 속해있는 팀의 팀원들을 기준으로 다시 계산. 리더가 속해있는 팀의 팀원이 워크 샵에 참여시키는 경우: 해당 팀원이 팀장으로 속해있는 팀은 계산할 필요가 없어진다. 이 점화식을 이용해 계산을 하고 메모이제이션을 적용하면 제한 시간내에 해결할 수 있다....

날짜: 2022년 5월 30일 오후 3:02 코드 Algorithm/72415.py at main · Junroot/Algorithm 풀이 여러개의 소문제로 나눠서 해결했다. 카드 쌍을 지우는 순서를 모두 탐색해보는 백트래킹 A위치에서 B위치로 이동하는 최단 경로 구하기 1번은 재귀함수를 이용해서 구현하면되고, 2번은 bfs를 사용했다.

날짜: 2022년 6월 1일 오후 9:38 오답: o 코드 Algorithm/72414.py at main · Junroot/Algorithm 풀이 틀린 풀이 시간이 최대 99시간 59분 59초로 360000초 까지 밖에 없다는 것을 인지했지만, 모든 로그를 360000크기의 배열에 값을 더해주는 것은 360000 * 300000 라는 시간복잡도가 발생할 것으로 보여 이 방법을 사용하지 않았다. 그래서 처음에는 로그들을 시작시간으로 정렬하여 시작 시간마다 누적 재생시간을 계산했는데 이 방법은 누적 재생시간을 매번 새로 계산해야돼서 시간 초과가 발생헀다. 맞는 풀이 결국 다른 사람 풀이를 봤는데, 처음에 언급한 방법을 활용하는 것이었다....