정신과 시간의 방

user-img

정신과 시간의 방

follow-img

Parametric Search (매개 변수 탐색), 쉽게 이해하기

1. Parametric Search 란?최적화 문제를 여러 개의 결정 문제 + 이분 탐색으로 변환시키는 문제 접근 방법이다. 여기서 3가지 키워드가 나왔는데, 이분탐색이 뭔지는 많은 사람들이 알테니, 최적화 문제와 결정 문제에 대해 먼저 설명하고 가겠다.(1) 최적화 문제문제의 조건을 만족하는 해의 범주가 존재하고, 그 중에서 최적의 답(최소값, 최대값 등)을 구하는 문제를 말한다. Thread Knots라는 문제를 예시로 들어보면, 해당 문제는 'n개의 매듭을 성공적으로 놓았을 때, 가장 가까운 두 개의 매듭 사이의 최대 거리를 출력하라'고 요구한다.그렇다면, 여기서 가능한 해의 범주는 n 개의 매듭을 각 Thread에 성공적으로 놓는 모든 경우이고,최적의 해는 가장 가까운 두 매듭 사이의 최대 ..

알고리즘-이론

[그림] 옥황상제

들어올린 턱, 웃는 모습 등, 미술 선생님의 도움을 받긴 했다..^^ 여튼 내 아이디어다 ㅎ 다음엔 동화책을 써봐야겠다. 기존의 동화책들이 요즘의 가치관과 너무 멀다는 생각이 든다. 나무꾼과 선녀라던가, 그런 것들...

내가 그린 그림

[후기] 3개월 지나서 적는 구름톤 11th

1. 합격 메일참여하게 되는 3번째 해커톤이었다. 지루한 취준 생활, 독서실에서 LED 빛만 세다가 합법적(?)으로 제주도에 갈 수 있는 기회를 받게 되어 너무 좋았다. 서류는 포트 폴리오, 제주도 사회에 도움되는 IT 아이디어, 내가 뽑혀야 하는 이유 3가지를 적어야 했다.구름톤에 관한 정보를 말하자면 30명만 뽑는다. 근데 여기에 지역인재 TO가 존재해서 제주도민이 아니라면, 확률이 더 낮아지는 듯 하다.프론트는 2배수, 나머지는 1배수로 6명씩 뽑는다.백엔드 개발자 6, 프론트 12명, 디자이너 6명, 기획자 6명 이렇게 온 것 같다. 그리고 현직자, 취준생, 대학생 비율도 1:1:1로 뽑은 듯 하다.2. 화요일 아침부터 시작... 부리나케 월요일 출발월요일 하루는 제주 라마단 시티 호텔에서 묶었다..

벨만 포드 알고리즘, 그림으로 쉽게 이해하기

1. 벨만포드 알고리즘이란?음수인 가중치가 존재하는 그래프에서도 최단 경로를 구할 수 있게 해주는 알고리즘.1️⃣ ONE TO ALL 알고리즘: 시작점을 고르면, 해당 정점에서 모든 정점까지의 최단 경로를 구할 수 있다.2️⃣ 음수 가중치가 있어도 괜찮아: 다익스트라는 안되지?3️⃣ 음수 사이클이 존재하는지도 확인 가능: 음수 사이클이 존재한다면, 사실 하나 이상의 정점으로의 최단 경로가 $- \infty $가 되기 때문에, 최단경로를 구하는 게 무의미해짐. 따라서 최단 경로를 구하는 게 무의미한지 여부도 파악 가능!음수 사이클가중치 그래프에서 정점 A에서 시작해서 A로 돌아왔는데 가중치의 합이 음수인 경우, 해당 사이클을 음수 사이클이라고 한다.해당 예시에서는 사이클을 돌수록 출발지에서 A,B,C까지의..

알고리즘-이론

항해 99 코테 스터디 5기 3일차 + [백준] 네트워크 복구 java 풀이

1. 문제 설명 📌문제 링크문제를 보며, 찾아낸 조건은 다음 3가지 였다.1️⃣ 최소 개수의 회선을 복구하라2️⃣ 모든 서로 다른 2 대의 컴퓨터가 교신이 가능해야 한다.3️⃣ 슈퍼 컴퓨터에서 다른 컴퓨터로의 통신 최소 비용은 복구 이전과 같아야 한다.문제를 풀며 느낀 점은,3️⃣ 때문에 1️⃣은 있으나 마나 한 조건이 되었다. 3️⃣을 만족시키려면 다익스트라를 활용해서, 최단 경로를 찾아야 하고, 그 최단 경로에 사용된 회선보다 개수를 더 줄일 수 없기 때문이다. (줄이면, 어떤 컴퓨터에는 슈퍼컴퓨터가 도달하지 못한다.) 2️⃣ 또한 다익스트라를 활용하면, 최소 슈퍼 컴퓨터를 매개로 모두 교신할 수 있기에 따로 구현해야 하는 조건이 아니다. 따라서 다익스트라를 하며 거쳐가 경로를 기억하는 문제이다...

#Popular Posts

[프로그래머스] Lv2 퍼즐게임챌린지 java 이해하기 쉬운 풀이!

cover-img

1. 문제 설명 📌문제 링크1번 퍼즐사용자의 레벨이 1이라 했을 때, 첫 번째 퍼즐은 사용자의 레벨 >= 퍼즐의 난이도 조건에 부합함으로 시간을 3분 드려서 퍼즐을 완료한다.2번 퍼즐사용자의 레벨 퍼즐의 난이도 이다.이 경우 문제의 요구조건처럼 직전 퍼즐을 (퍼즐의 난이도 - 사용자의 레벨) 만큼 다시 풀어야 한다. 그래서 2번 퍼즐을 푸는데는 1*3+4 = 7분의 시간이 든다.3번 퍼즐이것도 마찬가지로 사용자의 레벨 퍼즐의 난이도 임으로 (퍼즐의 난이도 - 사용자의 레벨)*4 + 2 = 10분 이 든다.따라서, 사용자의 레벨이 1이면 모든 문제를 푸는데 총 20분이 소요된다.문제에서는 limit 이라는 제한시간이 주어진다.제한 시간 안에 퍼즐을 다 풀 수 있는 최소 레벨이 몇인지 구하여라2. 접근 방..

99클럽 코테 스터디 5기 2일차 TIL + 프로그래머스 Lv4 가사 검색

cover-img

1. 문제 설명 📌문제 링크2. 구현 방법 🗃️KEY WORD: 트라이0️⃣ 중요한 처음 세팅!: Tri 구조를 만드는데 구성요소는 다음과 같다.(a) `기본적인 자식 노드`: HashMap로 구현 (자식 알파벳 이름, 그것의 객체)(b) `lenMap`: 현재 조회 중인 문자 뒤로 부터 전부 물음표라고 쳤을 때, 그 와일드카드를 만족하는 문자가 몇 개 있는지 세는 자료구조, HashMap로 구현 (문자열의 길이, 만족하는 문자 개수)1️⃣ 입력: 문자열 그대로 받는 Tri 하나, 문자열을 뒤집어서 받는 Tri 하나씩 만들어 각각 따로 따로 입력 받음입력받으면서, 매번 LenMap의 값을 갱신한다.2️⃣ 찾기: 와일드카드 ?를 만나기 전까지, 트라이를 깊게 들어간다. 반환값이 될..

99클럽 코테 스터디 1일차 TIL + [백준] 11657 타임머신 java 풀이

cover-img

1. 문제 설명 📌문제 링크벨만 포드 알고리즘 공부하고 한 번 써보라는 견본 문제이다.주어지는 간선 정보는 모두 단방향이다.2. 구현 방법 🗃️KEY WORD: BELLMAN-FORD ALGORITHM0️⃣ 형태로 모든 간선을 저장, 최소 비용 배열인 dist [] 선언.(N: 정점의 수, M: 간선의 수, dist 배열은 Long.MAX_VALUE로 초기화)1️⃣ 출발지를 1로 설정하고, N-1만큼 모든 간선을 돌면서 다음 구문을 실행한다.1️⃣-1) 현재 조회중인 간선의 출발지를 A, 도착지를 B, A➜B의 가중치를 C라고 할 때,dist[A] != ∞︎︎ && dist[B] > dist[A] + C이면, dist[B] = dist[A] + C로 최신화 해준다.2️⃣ 위 과정을 끝낸 후, 벨만 ..

[프로그래머스] Lv2 요격시스템 java 쉬운 풀이

cover-img

1. 문제 설명 📌문제 설명문제 설명 생략2. 접근 방식 🗃️KEY WORD: GREEDY ALGORITHMGreedy 알고리즘은 매 선택의 순간에 당시 할 수 있는 최선의 선택을 하는 것이 전체 문제에서도 최적의 해를 구하는 것임을 가정하는 알고리즘이다.여기서는 미사일의 묶음을 끝지점 기준 오름 차순으로 정렬하고, 미사일 묶음의 최대한 끝지점에서 차례대로 요격해 나가면 최소한으로 요격 미사일을 사용하는 것이다. 해당 방법은 다음과 같은 이유로 유효하다.미사일을 만나면 무조건 요격해야 한다. 안하고 지나치는 경우는 없다.따라서 미사일을 만나면 최대한 겹치게 삭제해야 한다.하나의 미사일 묶음 A가 다른 미사일 묶음과 최대한 겹치는 경우는 A의 끝지점에서만 발생한다.예를 들어보겠다.다음과 같이 폭격 미사..

HTTP에서 Binary File을 전송하기 위한 방법 (MIME, Base64)

cover-img

1. HTTP에서 왜 일반적으론 Binary File을 전송할 수 없는가? (1) 파일 종류 구분 Binary 파일 텍스트 파일 저장하는 내용 문자와 숫자 모두 저장 문자만 저장 가능 데이터 읽을 때 적힌 그대로 읽는다 . 문자 -> 문자로 읽음, 숫자 -> 숫자로 읽음 숫자는 문자로 변환 해서 읽는다. 문자 -> 문자 숫자 -> 문자 데이터 쓸 때 적힌 그대로 쓴다. 문자 -> 문자 숫자 -> 숫자 숫자도 문자로 변환 했기 때문에 문자만 쓴다. 문자 -> 문자 예시 이미지, 동영상 파일, 프로그램 글로 적힌 것 (2)왜 HTTP 에선 Binary file을 못 읽는가? HTTP는 텍스트 기반의 프로토콜, 일반적으로 텍스트 파일을 읽기 위해 디자인 되었다. 따라서 바이너리 파일을 읽으려면 다른 방법이 필..

99클럽 코테 스터디 5기 4일차 + [백준] 1253 좋다. (2트)

cover-img

1. 문제 설명 📌문제 링크N개의 수가 주어지는데, 이 중 하나를 택해보자. (택한 수를 E라 부르겠다.)이 E를 나머지 N-1개 중 2개를 합해서 만들 수 있으면 좋은 수라고 부르겠다.이떄 좋은 수의 개수는 몇 개 인가?2. 구현 방법 🗃️KEY WORD: 마주보는 투 포인터1️⃣ N개의 수를 arr이란 배열에 입력 받아서 오름 차순 정렬한다.2️⃣ 포인터를 3개 두어보자. 각각의 의미는 다음과 같다.E = 좋은 수가 될지 안될지 확인하는 target을 가리키는 포인터 (0부터 점점 오른쪽으로 간다.)L = N개의 정렬된 수 중 제일 좌측을 가리키는 포인터 (점점 오른쪽으로 간다.)R = N개의 정렬된 수 중 제일 우측을 가리키는 포인터 (점점 왼쪽으로 간다.) 3️⃣L과 R이 서로 만날 때 까지 ..

#Notice

cover-img

왜 블로그 이름이 정신과 시간의 방인가요?

드래곤볼 Cell saga를 보셨나요?

해당 에피소드에서 주인공 일행은 막강한 적을 이기기 위하여 하루가 1년으로 변하는 정신과 시간의 방에 들어가 수련을 합니다.

이 블로그가 저에게 하루를 1년처럼 알차게 쓸 수 있는 공간이 되어 제 성장을 도와주길 바라는 마음에서 지었습니다 🤗

Home 깃허브

cover-img

D-day

생일까지

@dalcheonroadhead

취미생활 1 : 그림그리기

@jeonsoomin_brain

취미생활 2: 음악

#Review

cover-img

[후기] 3개월 지나서 적는 구름톤 11th

cover-img

SSAFY 프로젝트 아이디어 모음집! + 꿀팁 (SSAFY 프로젝트 우수상 총 4회 수상)

내가 그린 그림

cover-img

[그림] 옥황상제

들어올린 턱, 웃는 모습 등, 미술 선생님의 도움을 받긴 했다..^^ 여튼 내 아이디어다 ㅎ 다음엔 동화책을 써봐야겠다. 기존의 동화책들이 요즘의 가치관과 너무 멀다는 생각이 든다. 나무꾼과 선녀라던가, 그런 것들...

#tag cloud

항해99 프로그래머스 백준 개발자 취업 개발자 코딩테스트 코딩테스트 준비 알고리즘 99클럽 Java Read More →

티스토리툴바