R+7

문제n x n 격자 벽면에 기둥과 보를 설치하거나 삭제하면서, 매 작업 후 남아 있는 모든 구조물이 조건을 만족해야 하는 문제. 기둥은 바닥 위에 있거나, 아래에 기둥이 있거나, 보의 한쪽 끝 위에 있어야 한다. 보는 한쪽 끝이 기둥 위에 있거나, 양쪽 끝이 다른 보와 연결되어 있어야 한다. 명령은 [x, y, a, b] 형태로 주어지고, a는 기둥/보, b는 설치/삭제를 의미한다. 최종적으로 남은 구조물을 x 오름차순, y 오름차순, 기둥 먼저 정렬해서 반환해야 한다. 조건 자체가 복잡해서, 설치와 삭제 각각의 경우를 미리 전부 따지려 하면 코드가 쉽게 꼬이는 구현 문제다.회고처음에는 명령을 그대로 따라가면서 모든 경우의 수를 직접 나누려고 했는데 (먼저 b가 1이면 설치, 0이면 삭제로 나누고, 그..

문제링크 (문제 설명이 말로 하기가 까다로워서, 직접 문제에 들어가 GIF를 보는 것이 이해가 더 빠르다) n x n 크기의 2차원 배열을 특정 규칙에 따라 채운 뒤, 이를 1차원 배열로 펼쳤을 때 left부터 right까지의 구간만 반환하는 문제. n은 최대 10^7까지 주어지고, right - left는 10^5 미만으로 제한된다. 처음 보면 2차원 배열을 직접 만들어야 할 것 같지만, n^2 크기의 배열을 만드는 순간 시간과 메모리 양쪽에서 바로 터지는 문제로, 결국 전체 배열을 만드는 것이 아니라 특정 인덱스가 원래 2차원 배열의 몇 행 몇 열인지 계산해서 값을 바로 구해야 하는 문제다. 회고솔직히 처음에는 '설마 바로 값을 찍어야 하는 문제는 아니겠지'라고 생각했는데, 그게 정답이었다. 제한 조..

문제N x N 격자의 시계들(0:12시, 1:3시, 2:6시, 3:9시)이 상하좌우 연동되어 돌 때, 모든 시계를 12시(0)로 맞추기 위한 최소 조작 횟수를 구하는 문제. 시계 하나를 돌리면 본인 및 상하좌우 시계가 함께 90도(1칸)씩 돌아가고, 0(12시), 1(3시), 2(6시), 3(9시) 이며, 4번에 1바퀴 회전. 제한 조건은 N이 2 이상 8 이하.회고풀다가 막혔다. 처음에는 주변 시계가 0이 아닌 곳을 찾아 돌리는 탐욕적(Greedy) 방식을 사용했지만, 너무 많은 경우의 수가 존재하는데다 애초에 돌려서 상하좌우가 0이 아닌 상태가 되더라도 전체를 맞추기 위해 돌려야 하는 경우가 존재했다. 이러한 문제를 푸는데는 정석적인 방법으로 라이츠 아웃(Lights Out) 퍼즐의 해결 방법을 도입..

Today I LearnedCookie웹 브라우저가 사용자 컴퓨터에 저장하는 최대 4KB 크기의 작은 텍스트 데이터 파일. 서버가 HTTP 응답 헤더(Set-Cookie)를 통해 브라우저에 데이터를 전달하면 브라우저는 이를 저장해 뒀다 이후 해당 도메인으로 보내는 모든 HTTP 요청 헤더에 자동 포함해 서버로 다시 전송. 대체로 사용자 로그인 상태 유지(세션 관리), 웹사이트 개인화 설정 저장, 사용자 트래킹 등에 사용한다. 그래서 '쿠키 수집 및 사용 동의' 팝업창이 뜨는 사이트가 많은 것도 이러한 이유. (주로 어떤 페이지에 오래 머무는지, 어떤 상품을 클릭했는지 기록을 수집한다) 다만 매 요청마다 서버로 전송되기 때문에 불필요한 네트워크 트래픽을 유발할 수 있고, JavaScript로 접근이 가능해..

Today I Learned인증(Authentication)과 인가(Authorization)개발에서 'Auth'는 철자가 비슷한 인증(Authentication)과 인가(Authorization) 두 가지 개념을 통칭. 시스템 보안을 구성하는 가장 기초적인 두 축이다. 인증은 '사용자가 누구인지 증명하고 확인하는 절차'고, 인가는 그 인증된 사용자가 '특정 자원에 접근, 조작 가능한지 검증하는 절차'다. 쉽게 말하면 "너 누구..?"랑 "너 뭐 돼?"다. 인증은 항상 먼저 진행되고, 인가는 인증이 완료된 후 진행된다. 실패 시 HTTP 상태 코드는 각각 401 Unauthorized (미인증 상태)와 403 Forbidden (인증은 되었으나 권한 없음)이다. OAuth(Open Authorizatio..

문제출발 지점부터 도착 지점까지 놓인 바위 중 n개를 제거해 각 지점 사이 거리 최솟값 중 가장 큰 값을 구하는 문제. 도착 지점까지의 거리 (distance)는 1부터 10억. 바위 개수는 5만 개로 조건이 주어진다. 각 바위가 [2, 14, 11, 21, 17] 로 주어지고 n이 2라고 가정하면, [2, 14]를 제거했을 때 각 바위 사이 거리는 [11, 6, 4, 4]가 되고, 거리의 최솟값은 4가 된다. 다른 값과 비교했을 때 이 값이 제일 크므로 답은 4. 회고이게 왜 이분 탐색인가..? 생각이 가장 먼저 들었고, 어떻게 접근해야 문제를 풀 수 있을지 한참 고민. 도착 지점까지의 거리가 10억이라는 부분에서 힌트를 얻었어야 하는 문제였다. 애초에 바위 개수가 5만 개인 상황에서 n개를 전부 빼보..

Today I LearnedJava와 JVMJava는 프로그래밍 언어. _한 번 작성하면 어디서나 실행된다(Write Once, Run Anywhere)_는 철학을 기반으로 만들어짐. 코드를 컴파일하면 기계어가 아니라 바이트코드로 변환되고, 이 바이트코드를 JVM(Java Virtual Machine)이 해석해서 실행하는 구조다. 그래서 Windows에서 짠 Java 코드가 Linux 서버에서도 그대로 돌아간다. 이 부분은 상당히 편리. 프레임워크프레임워크는 애플리케이션의 뼈대(구조)를 미리 짜놓고, 개발자에게 그 빈칸(비즈니스 로직)만 채우게 하는 방식의 도구다. 내가 필요할 때 불러다 쓰는 라이브러리와 다르다. 프레임워크는 본인이 흐름을 쥐고 있고 내 코드를 필요할 때만 불러주는 식이다. 전자는 내가..

앞으로 알고리즘 관련 문제 풀이 모음 + 개념 포스팅을 한눈에 찾기 위한 메인 인덱스 페이지. 새 글 작성할 때마다 이 곳에 링크와 간단 팁을 업데이트할 예정이다.1. 개념 정리그래프 문제 해결 방안2. 문제 풀이No.문제명주요 알고리즘바로가기001징검다리이분 탐색보러가기002고고학 최고의 발견완전 탐색보러가기

분기 설정알고리즘 문제 중 그래프가 나왔을 때, 우리가 생각해 볼 접근법을 설정한다면 다음과 같다.1. 이동: 최단 거리나 최소 비용을 구하는가?간선 비용이 모두 같음(또는 비용 없음): BFS간선 비용이 다름모두 양수: 다익스트라음수 포함됨: 벨만-포드한 지점이 아니라 '모든 지점 간'의 거리: 플로이드-워셜2. 연결: 모든 노드를 하나로 묶거나 그룹화하는가?최소 비용으로 전체를 하나로 연결: MST (크루스칼, 프림) 필수 조건: 무방향 그래프이어야 하며, 사이클이 없어야 함같은 그룹/네트워크인지 확인하거나 두 그룹을 합침: 유니온-파인드 (얘는 여기 뿐 아니라 여러 군데 사용됨)3. 작업의 선후 관계가 있거나 사이클을 찾아야 하는가?순서 정하기, 선수 과목, 선행 조건: 위상 정렬 필수 조건: 방향..

Today I Learned웹소켓(WebSocket)이란 하나의 TCP 접속 위에서 클라이언트와 서버 간 지속적인 양방향(Full Duplex) 실시간 통신을 가능케 하는 네트워크 기술이다. 양방향이기 때문에 클라이언트 측의 요청(request)이 따로 없어도 서버가 데이터를 보낼 수 있고, 한 번 연결이 성립되면 명시적으로 연결을 끊기 전까지 실시간으로 연결이 유지된다(stateful). 연결을 설정하는 초기 단계에만 HTTP 통신을 사용하고 그 후로는 데이터를 프레임 단위로 교환하기 때문에 오버헤드를 방지할 수도 있다. ※ 왜 HTTP는 무거운가?: 무상태성(stateless)을 지향하기 때문에 매 요청마다 필수 메타 데이터를 헤더에 통째로 담아 보내야 하기 때문에 담기는 정보가 매우 많고, 이를 매..