Persistence

집합 커버링 문제(set-covering problem) 근사 알고리즘 미국 50개 주에 방송을 하고 싶다. 이를 위해서는 방송국을 찾아가야 하는데, 이 방송국들은 각각 커버하는 주가 다르다. 방송국에 찾아가는 데는 비용이 드므로 방송국을 가장 적게 찾아가면서도 50개 주를 다 포함하게끔 하고 싶다. 이를 해결하기 위해 탐욕 알고리즘을 사용한다. (거의 정답에 가까운 답을 유추) 아직 방송하지 않은 지역 중 가장 많은 지역에 방송할 수 있는 방송국을 고른다. 이미 방송되고 있는 지역이 일부 포함되어 있어도 관계 없다. 모든 주에 방송이 될 때까지 반복한다. states_needed = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"]) # 방송하고자 하는 주의..

To do freeCodeCamp 알고리즘 2문제 Udemy JS Installing and Using Packages Intro to React.js create-react-app create-react-app2 Your First React Component 탐욕 알고리즘부분 들어가기 Today was... 리액트 문법은 생소하다. json.package, jsx, react component 등 새로운 것들을 많이 배웠다. 익숙해질 필요가 있을 것 같다. Opic에 대해서 걱정하지만 하기가 싫으니까 우선순위에서 밀려나서 결국 안하게 된다. 이런 경우, 매일 하려고 하는 건 무리다. 패기롭게 매일매일 하자고 했지만 개발자가 되기 위해 할 일의 우선순위에서도 밀리고, 그리고 개인적으로도 하기 싫어서 우..

To do Udemy JS: NPM 들어가기 Recursion 과제 freeCodeCamp 알고리즘 2개 Today was... 솔직히 우아한테크코스 코테를 떨어지니 자바에 대한 공부의욕이 떨어진 건 사실이다. 일단 자바스크립트 위주로 쭉쭉 진도를 나가고, OOP에 대해 부가적으로 공부를 하기로 한다. 일단 코드스테이츠 과제 언넝 끝내야겠다. 오픽은...언제...

To do 탐욕 알고리즘 공부 freeCodeCamp 알고리즘 문제 1개 풀기 오늘은 진짜진짜 트위틀러 하기!!!!! Today was... dom으로 트위틀러 과제하는게 (귀찮기도 하고) 어려웠다. 특히 css는 진짜 어렵다. 파워포인트로 쉽게 위치를 바꾸고 색깔을 바꿀 때에는 위치나 색깔을 맘대로 하는게 그렇게 어려운 줄 몰랐다..... 프론트엔드는 과연 가능한 것인가

Spinal Tap Case 문제 문자열을 spinal case로 변환하라. Spinal case란 소문자로 이루어지고 dash(-)로 연결된 문자열을 말한다. 예시 spinalCase("This Is Spinal Tap") should return "this-is-spinal-tap". Passed spinalCase("thisIsSpinalTap") should return "this-is-spinal-tap". Passed spinalCase("The_Andy_Griffith_Show") should return "the-andy-griffith-show". Passed spinalCase("Teletubbies say Eh-oh") should return "teletubbies-say-eh-oh..

To do 알고리즘 책(다익스트라 알고리즘, 탐욕탐색) OPic 1시간 freeCodeCamp 알고리즘 1문제 twittler Do Tomorrow 제발 트위틀러... ㅠㅠ

다익스트라 알고리즘(Dijkstra's algorithm) 최단 시간 경로 너비 우선 탐색이 최단 경로(가장 짧은 단계)였던 반면, 다익스트라 알고리즘은 가장 빠른 경로 즉, 최단 시간 경로를 탐색한다. 다음과 같은 단계를 거친다. 가장 가격이 "싼" 정점을 찾는다. 가장 가격이 싼 정점이란 도달하는 데에 걸리는 시간이 가장 짧은 정점을 말한다. 이 정점의 이웃 정점들의 가격을 조사한다. 그래프 상의 모든 정점에 대해 이 일을 반복한다. 최종 경로를 계산한다. 예시 위 그래프에서 A까지 가는 시간은 6, B까지 가는 시간은 2이므로 B가 가장 싼 정점이다. 이 때 도착점까지 얼마 걸리는 지는 알 수 없으므로 무한대라고 한다. 정점 B의 이웃 정점의 가격을 조사한다. B에서 A를 가는 시간은 3이므로 출발..

너비 우선 탐색(Breadth-First Search) 그래프 연결의 집합을 모형화한 것 그래프는 정점(node)와 간선(edge)로 이루어진다. 이어진 정점을 이웃(neighbor)이라고 한다. 그래프에는 방향 그래프와 무방향 그래프가 있다. 무방향은 화살표가 없고 서로 상호 관계가 있다는 뜻이다. 너비 우선 탐색 그래프를 대상으로 하는 탐색 알고리즘이다. 다음과 같은 질문을 던지면 도움이 된다. 정점 A에서 B로 가는 경로가 존재하는가?(ex. 내 네트워크 중 바나나칩 판매상이 있는가?) 정점 A에서 B로 가는 최단 경로는 무엇인가?(ex. 누가 가장 가까운 바나나칩 판매상인가?) 네트워크를 통해 바나나칩 판매상을 찾으려고 한다고 가정했을 때, 내 친구부터 탐색하고, 친구 중에 없으면 친구의 친구를 ..

해시 함수 해시 함수에 관한 일반적인 사실 문자열을 받아서 숫자를 반환하는 함수. 문자열에 숫자를 할당(mapping)한다. 해시함수에는 일관성이 있어야 한다. "apple"을 넣을 때마다 항상 반환되는 숫자는 같아야 한다. 다른 단어가 들어가면 다른 숫자가 나와야 한다. 예컨대 어떤 값이 들어가든 "1"이 나오는 함수는 좋지 않다. 해시함수는 같은 이름에 대해 항상 같은 인덱스를 할당한다. 값이 저장된 위치(인덱스)를 정확하게 알려주므로 탐색을 할 필요가 없다.(ex. 이진탐색, 단순탐색) 그렇기 때문에 빅오표기법으로 O(1)의 시간이 걸린다. O(1)은 상수 시간(constant time)이라고 불린다. 이는 테이블의 크기에 관계없이 항상 똑같은 시간이 걸린다는 의미이다. (항목이 10억개라고 해서,..

To-do Opic 1시간 공부 유튜브 오픽노잼: 외국인에게 배우는 오픽, AL시리즈 오늘은 자기소개 문항 완성 & 연습 알고리즘 책(너비 우선 탐색, 다익스트라 알고리즘, 탐욕 탐색) 정보처리기사 접수 필라테스 가기 (extra) freeCodeCamp 알고리즘 문제 1개 풀기 (extra) twittler Today was... 내가 할 수 있는 것보다 계획을 과도하게 세운다는 느낌이 든다. 실제로 알고리즘책만 해도, 읽는 것이 문제가 아니라 정리하는 것이 오래 걸린다. 정리를 안할까 싶다가도, 익숙지 않은 내용이라 정리하지 않으면 금세 휘발되어 소용없어질 것 같은 생각이 든다. 그래서 좀 현실감 있게 조정하려고 하는데... 내가 원하는 만큼 하기 위해서는, 시간을 효율적으로 조직하고 좀 더 부지런해..

선택정렬(Selection Sort) 가장 많이 들은 노래 순으로 정렬하기 노래 리스트 전체 중에서 가장 감상 수가 높은 노래를 하나 뽑아서 새로운 리스트 첫 줄에 작성한다. 이 때 원래의 리스트에서는 그 곡을 삭제한다. 나머지 리스트 전체 중에서 가장 감상 수가 높은 노래를 뽑아서 새로운 리스트 두번 째줄에 작성한다. 이 역시 원래 리스트에서는 삭제한다. 이를 계속 반복하면 원래의 리스트가 비워졌을 때에 새로운 리스트에는 감상 수가 높은 순으로 노래가 정렬된다. 이렇게 n개의 노래를 정렬하려면 빅오 표기법으로 O(n^2)만큼의 시간이 걸린다. 첫 번째 실행에서는 n개의 항목을 단순 탐색하므로 O(n)의 시간이 걸린다. 첫 번째 시행 후 원래의 리스트에서 항목이 한 개 지워지므로 다음 탐색은 O(n-1)..

분할정복(Divide-and-Conquer) 분할정복전략은 다음과 같이 동작한다. 가장 간단한 경우로 기본 단계를 찾는다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾아낸다. 배열의 모든 원소를 합하는 sum함수를 재귀를 사용하여 만들기 기본 단계 찾기: 원소가 하나이거나 원소가 없을 때에 sum을 구하는 것은 매우 간단하다. sum([7]); // prints 7 sum([]); // prints 0 그러므로 원소가 하나이거나 없을 때의 합계를 구하는 것이 기본 단계가 된다. 주어진 문제를 작게 줄여서 기본 단계가 되도록 하기 sum([2,4,6])은 2 + sum([4,6]) 과 같다. sum([4,6])은 4 + sum([6])과 같다. sum([6])은 6이다. // 기본 단계 ..

To-do Hello Coding 그림으로 개념을 이해하는 알고리즘 읽고 정리(분할 정복, 퀵정렬, 빅오 복습, 해시테이블, 너비 우선 탐색, 다익스트라 알고리즘) OPic 1h 공부 Today was... 여행에서 다녀온 뒤로 약간의 슬럼프. 그렇지만 아주 조금씩이라도 매일매일 하는게 중요하다고 생각한다. 오픽을 2주 정도 준비하고 시험을 치려고 한다. 매일 1h 씩 투자할 생각이다. 기왕 하는거니 AL을 목표로 잡겠다. 정보처리기사도 접수할 생각이다. 멀티캠퍼스 수업에 들어가기 전에 시간이 좀 있을 때에 필기 공부를 해놓는게 수월할 것 같아서이다. 티스토리는 마크다운을 지원하기 시작했는데, 코드블럭 내의 코드가 너무 안 예쁘다... 그래도 기존에 타이포라로 쓸 때처럼 복붙은 안해도 되니까 편해졌다. ..

To-do Hello Coding 그림으로 개념을 이해하는 알고리즘 읽기 고용센터에서 준 과제(?)하기 Today was... 어제 귀국한 뒤 오늘은 두통이 너무 심하다. 한국 미세먼지... 멀티캠퍼스 4차산업혁명 선도인력양성 과정에 등록하기 위해 내일배움카드를 발급받으러 고용센터에 다녀왔다. 뭔가 이것저것 과제를 주었다. Do Tomorrow Udemy 강의 듣기

문제 첫 번째 글자가 자음일 경우 문자의 맨 뒤로 보낸다. 앞글자가 모음이 될 때까지 반복한 뒤에 "ay"를 붙인다. 첫 번째 글자가 모음일 경우 문자 맨 뒤에 "way"를 붙인다. 예시 translatePigLatin("glove") should return "oveglay". 내가 푼 답 function translatePigLatin(str) { if((/[aeiou]/).test(str[0])) { return str + "way"; } if(!(/[aeiou]/).test(str)) { return str + "ay"; } while(!(/[aeiou]/).test(str[0])) { var result = str.substring(1) + str[0]; str = result; } return..