👩🏻‍🌾

Branch and Bound - Backtraking과 같이 state-space tree를 사용한다. - 트리를 탐색하는 방식에 제한을 두지 않는다. - 오직 최적화 문제에만 사용된다. BFS와 Best-First Search를 사용해서 탐색을 진행하는데 이번 포스팅에서는 Best-First Search로 0-1 Knapsack Problem을 해결하는 방식에 대해 작성하도록 하겠습니다. 0-1 Knapsack Problem using Best-First Search Basic Idea - 노드가 promising한지로 결정하기보다는 bound를 사용해서 다음으로 확장할 노드를 선택 - 노드의 bound로 우선순위가 정해지는 priority queue를 사용 1. item을 모두 넣지 않았을 떄, b..

Backtracking 해를 찾는 도중 막히면 이전 단계로 돌아가서 해를 찾아가는 기법 Backtracking을 사용하는 3가지 예시를 보자. 1. N-queens problem - N x N 크기의 체스보드판에 N개의 퀸들을 서로 위협하지 않게 배치하는 문제 4 queens problem일 때 16개의 자리 중 4자리를 뽑는 경우 : C(16, 4) = 1820 두 퀸이 같은 행, 열 또는 대각선에 위치할 수 없으므로 배제할 수 있는 경우 : 4 x 4 x 4 x 4 = 256 : i행 j열에 퀸이 위치 처음 시작할 때와, 에만 퀸이 위치할 때 -> 하위 노드에서 답을 발견할 가능성이 있으므로 promising , , 에 퀸들이 위치할 때, 같은 열에 위치하므로 답이 될 수 없으므로 nonpromisi..

Greedy Algorithm -매 순간 가장 좋아보이는 것을 고르는 방법 General Greedy Approach - 빈 집합으로 시작하여 집합 인스턴스에 대한 답을 나타낼 때까지 집합에 아이템을 순서대로 추가 선택 절차 ( = Selection Procedure) 그리디 기준에 따라 집합에 추가할 다음 아이템을 선택 타당성 확인 ( = Feasibility Check) 인스턴스에 답을 제공하는 방식으로 집합을 완료할 수 있는지 여부를 확인 답 확인 ( = Solution Check) 새 집합이 인스턴스에 대한 답을 구성하는지 여부를 결정 Minimum Spanning Trees 정의 Undirected Graph Connected Graph Acyclic Graph Tree Spanning Tree..

Dynamic Programming이란?최적화 문제를 풀기 위한 수학적인 알고리즘. 문제를 작은 부분 문제로 나누고, 중복되는 부분 문제의 해를 저장하여 중복 계산을 피할 수 있고, 작은 부분 문제의 해를 조합하여 전체 문제의 해를 구하는 방법(=Bottom-Up) 4가지의 예시를 통해 Dynamic Programming에 대해 자세히 알아보자.1. The Binomial CoefficientC(n, k) = C(n-1, k) + C(n-1, k-1) for 0

포스팅을 하기에 앞서 여담 하나를 얘기하자면,더보기인프런에 리액트 강의들이 꽤 많고 각각의 강의들은 해당 강의를 수강하면 최소 1개에서 많게는 4-5개의 프로젝트를 완성할 수가 있다. 내가 수강 중인 리액트 강의는 '감정 일기장' 프로젝트를 만들 수 있는데 수많은 강의들 중 내가 이 강의를 선택한 이유가 좀 황당하다.대학교 1학년 땐가 앱스토어 인기 유료 앱에 'MOODA'란 감정을 기록해서 일기를 작성할 수 있는 앱이 있었다. 앱 아이콘과 상세 화면 사진을 봤을 때, UI가 상당히 아기자기(아기자기한 거에 마음이 약한 편)하여 구매하게 되었고 2년 동안은 꽤 잘 사용한 거 같다.여튼, 그래서 졸업작품에서 리액트를 사용하게 돼서 처음 사용해보는 터라 리액트 강의를 찾아보고 있었고, 해당 강의를 발견하게 ..

자바 스크립트는 코드가 작성된 순서대로 작업을 처리하기 때문에 이전 작업이 진행 중일 때는 다음 작업을 수행하지 않고 기다린다. (= 즉, 먼저 작성된 코드를 먼저 다 실행하고 난 뒤, 그 뒤에 작성된 코드를 실행함) ➡️ 동기 방식의 처리 이런 동기적 처리의 단점은 위 사진의 taskB처럼 하나의 작업이 너무 오래 걸리는 경우, 오래 걸리는 작업이 종료되기 전까지 모든 작업이 올스탑 되기 때문에 전반적인 작업의 흐름이 느려진다는 점이 있다. ➡️ 동기 처리 방식의 문제점 그렇다면 코드를 실행하는 일꾼 Thread를 여러개 사용하는 방식인 'MultiThread' 방식으로 작동시키면 위 사진처럼 작업 분할이 가능하니까 오래 걸리는 작업이 있어도 다른 일꾼 Thread에게 작업을 지시하면 되니까 괜찮지 않..

1️⃣ 문제 설명 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. 2️⃣ 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. 3️⃣ 출력 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. 👩🏻‍💻 작성한 코드 import sys import heapq input = sys.stdin.readline n = int(input()) pos = list(map(i..

1️⃣ 팝업창 표시하기 alert(내용)// 알림창 표시 confirm(내용)// 확인창 표시 ⬅️ [확인] 버튼과 [취소] 버튼이 있어서 사용자가 어떤 버튼을 클릭했는가에 따라 다르게 동작 가능 ⬅️ 확인 버튼 누르면 사진처럼 true 반환, 취소 버튼 누르면 false 반환 prompt(내용)// 사용자가 간단한 값을 입력할 수 있는 창 ⬅️ 입력값 반환 prompt(내용, 기본값)// 기본값 지정 가능 2️⃣ 콘솔창에 내용 표시 console.log(내용)// 콘솔 창에 결과 표시 3️⃣ 웹 브라우저 창에 내용 표시하기 document.write()// 웹 브라우저 창에 결과 표시, DOM을 이용해서 원하는 위치 지정

이 문제를 풀면서 처음으로 내장함수 enumerate()를 사용해봐서 개념 정리를 위해 포스팅하게 됐다. ✅ enumerate() 함수란? 리스트의 원소에 순서값을 부여해주는 함수 기본적으로 인덱스와 원소로 이루어진 튜플(tuple)로 만들어준다 -> 예시 코드로 확인해보자 nums = ["apple", "banana", "pear","strawberry","grape"] for i in enumerate(nums): print(i) 위 코드를 실행 시, 아래와 같이 인덱스와 원소를 튜플 형태로 출력해준다. 이때, 인덱스와 원소를 각각 다른 변수에 할당하고 싶다면 아래 코드와 같이 언팩킹을 해주면 된다. nums = ["apple", "banana", "pear","strawberry","grape"] ..

프로그래머스에서 해당 문제를 풀다가 swapcase()란 내장함수를 처음 알게 돼서, 대소문자 관련 내장함수를 정리하고자 해당 문제 풀이를 포스팅하게 됐다. ✅ 대소문자 관련 내장함수 upper() 문자열을 모두 대문자로 변환 lower() 문자열을 모두 대문자로 변환 isupper() 해당 문자가 모두 대문자인지 확인하여 boolean형으로 결과 반환 islower() 해당 문자가 모두 소문자인지 확인하여 boolean형으로 결과 반환 swapcase() 대문자는 소문자로, 소문자는 대문자로 변환 💡예제 코드 str1 = "StudyIng PyThoN" str2 = "it is all lower" print('case1', str1.upper()) print('case2', str1.lower()) p..