자바스크립트 방식은 최근에 웹 프론트 개발자로 이직하기 위해서 알고리즘을 하면서 사용해 보았다.
letarr=[];arr.sort([compareFunction]);
파라미터 compareFunction
정렬 순서를 정의하는 함수 이 값이 생략되면, 배열의 element들은 문자열로 취급되어 유니코드 값 순서대로 정렬된다. 이 함수는 두 개의 배열 element를 파라미터로 입력 받는다. 이 함수가 a, b 두개의 element를 파라미터로 입력받을 경우, 이 함수가 리턴하는 값이 0보다 작을 경우, a가 b보다 앞에 오도록 정렬하고, 이 함수가 리턴하는 값이 0보다 클 경우, b가 a보다 앞에 오도록 정렬한다. 만약 0을 리턴하면, a와 b의 순서를 변경하지 않는다.
리턴값 compareFunction 규칙에 따라서 정렬된 배열을 리턴한다. 이때, 원본 배열인 arr가 정렬이 되고, 리턴하는 값 또한 원본 배열인 arr을 가리키고 있다.
해당 문제는 탐욕(greedy) 문제로 현재 수행 하는것이 최선임을 정의하여 푸는 문제입니다.
그리디도 중요하지만 예외 처리가 중요한 부분이다.
링크 :
18185.라면 사기(small)
라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).
교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.
i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다. 최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.
입력(Input)
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력(Output)
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
1. 문제 풀이
그리디 알고리즘을 이용하는 문제인데, 구매 가능한 행동이 3가지이다. 그리고, i 번째 공장 i + 1 번째 공장, i + 2 번째 공장의 라면 개수에 따라서 구매 방식을 다르게 접근해야 한다.
하나의 공장에서 3원으로 구매하는것 보다 두 개의 공장에서 5원으로 구매하는것이, 세 개의 공장에서 7원으로 구매하는것이 효율적이라는것은 누구나 알 수 있다.
그래서 처음에는 현 위치 i에서 i + 1 번째와 i + 2 번째 공장과의 살 수 있는 최대한으로 묶어서 구매하는 방식으로 문제를 풀어 봤다.
3개씩 묶어서 구매
1 2 3 최소값인 1개씩 구매하여 0 1 2 을 만들면, 현 위치에서 구매 한 금액은 최소 값 1 * 7 = 7원
이는 i + 1 번째 값이 i + 2 번째 값보다 클 경우인데, 이 때에는 i 번째의 값과 [i + 1] - [i + 2] 의 값의 최소값 만큼 앞의 두개를 묶어서 사면 다음 구매에 더 싸게 구매가 가능하게 된다.
따라서 아래의 두 가지 방식으로 분기하여 그리디 방식으로 최대한 이익을 내서 구매를 한다면,
[i + 1] 공장의 라면 > [i + 2] 공장의 라면
[i], [i + 1] - [i + 2] 중의 최소값으로 선 구매 (2묶음)
[i], [i + 1], [i + 2] 중의 최소값으로 구매 (3묶음)
[i + 1] 공장의 라면 < [i + 2] 공장의 라면
[i], [i + 1], [i + 2] 중의 최소값으로 선 구매 (3묶음)
[i], [i + 1] 중의 최소값으로 구매 (2묶음)
[i] 의 남은 개수 구매
가장 최소의 금액으로 구매 할 수 있는 금액이 나오게 된다.
이것을 코드로 표현하겠습니다.
importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;importjava.util.StringTokenizer;publicclassRamyeon_18185{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbr=newBufferedReader(newInputStreamReader(System.in));StringTokenizerst=newStringTokenizer(br.readLine());intN=Integer.parseInt(st.nextToken());intfactory[]=newint[N+2];st=newStringTokenizer(br.readLine());for(inti=0;i<N;i++){factory[i]=Integer.parseInt(st.nextToken());}intanswer=0;for(inti=0;i<N;i++){if(factory[i]>0){// i + 1, i + 2 번 가게의 라면 유무를 확인// 현재 살 수 있는 가장 많은 라면을 산다.intmin=0;if(factory[i+1]>factory[i+2]){// i + 1의 수가 i + 2의 수보다 크면,// 맨 앞의 두개를 묶어서 먼저 사고, 세 개를 묶어서 사는게 싸다.// 이 때, [i] > [i+1] - [i+2] 의 값을 비교하여 최소값으로 구매min=Math.min(factory[i],factory[i+1]-factory[i+2]);answer+=min*5;factory[i]-=min;factory[i+1]-=min;min=Math.min(factory[i],Math.min(factory[i+1],factory[i+2]));answer+=min*7;factory[i]-=min;factory[i+1]-=min;factory[i+2]-=min;}else{// 반대는 세개 묶어 사고, 두개 묶어 사는게 싸다.min=Math.min(factory[i],Math.min(factory[i+1],factory[i+2]));answer+=min*7;factory[i]-=min;factory[i+1]-=min;factory[i+2]-=min;min=Math.min(factory[i],factory[i+1]);answer+=min*5;factory[i]-=min;factory[i+1]-=min;}answer+=factory[i]*3;factory[i]=0;}}System.out.println(answer);}}
해당 문제는 탐욕(greedy) 문제로 현재 수행 하는것이 최선임을 정의하여 풀어보았습니다.
링크 :
2212. 센서
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
입력(Input)
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력(Output)
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
기존의 깃이 공부하면서 썻던 내용들이라… 정리도 되어 있지 않았고 그래서 뭔가 지저분하게 되어 있는데 어디서부터 손을 대야 할지 감이 잡히지 않았다.
때문에 새로운 저장소를 만들고, github io를 이용하여 나의 블로그도 작성하면서 기존 프로젝트들의 내용 정리와 블로그 정리 두가지를 같이 하면서 옮기게 되었다.
블로그 작업 준비도 하면서 기존 프로젝트들을 옮기고 정리한다는게 쉬운 일은 아니지만 지금 목표로 하고 있는 일이 있기 때문에 시작을 할 수 있었던것 같고, 무엇보다도 새로 산 Macbook M1 Max를 잘 활용해 볼 수 있는 기회가 되지 않을까 생각하면서 작업하고 있다.
Ever since the introduction of Dark Mode, link styles have been a bit of an issue. Specifically, finding an accent color that worked on both light and dark backgrounds was the problem. With Hydejack 9, the link style has been revamped so that legibility is no longer tied to the choice of accent_color, giving you much more freedom in creating a unique design flavor for your site.
Ready for the Big Screen
The theme on which Hydejack is based was designed for a different era of the web. Hydejack has inherited many of its limitations, but over time I’ve made adjustments, such as centering the content column for better reading ergonomics.
With version 9, Hydejack takes full advantage of large displays. Whether it’s design indulgences such as oversized headlines, or quality of life improvements such as a floating table of contents, Hydejack now finds use for all that extra screen real estate1.
What’s in the Cards?
Hydejack 9 now lets you use content cards for both projects and posts. The cards have been redesigned with a new hover style and drop shadows and they retain their unique transition-to-next-page animations, which now also work on the blog layout. The new grid layout lets you do that.
Good images are key to making the most out of content cards. For that reason, a chapter on images has been added to the documentation.
Built-In Search
Hydejack now has Built-In Search. It even works offline. I’ve been prototyping many approaches and eventually settled on a fully client-side, off-the-main thread solution that perfectly fits the use case of personal sites and shows surprisingly good results2.
The new search UI is custom made for Hydejack and shows beautiful previews of your posts and pages, right on top of your regular content.
Together with the Auto-Hiding Navbar, your entire content library is now only a couple of keystrokes away.
Auto-Hiding Navbar
A navbar that’s there when you need it, and disappears when you don’t. Simple as that.
Sticky Table of Contents
Already a staple on so many sites on the web, this pattern is now also available in Hydejack. What’s unique about it is that it simply picks up the table of contents already created by kramdown’s {:toc} tag and transparently upgrades it to a fully dynamic version.
…and much more
Other noteworthy changes include:
Support for Jekyll 4
Choice between MathJax and KaTeX for math rendering
Use of jekyll-include-cache for drastically improved page building speeds
New variables configuration file — adjust content width, sidebar width, font size, etc…
…and the option to disable grouping projects by year.
Read the the CHANGELOG for the full scope of features and improvements made in Hydejack 9. Maybe just glance at it to confirm that it is indeed a pretty long list.
Even More to Come
New features for 9.1 are already lined up. Code block headers and code line highlights for even better technical blogging, as well as download buttons on the resume page for PDF, vCard, and Resume JSON are just around the corner.
Get It Now
The Free Version of Hydejack is now availabe on RubyGems and for the first time also on GitHub Packages. The source code is available on GitHub as always.
The PRO Version is scheduled to release on July 7th on Gumroad. Pre-Orders are open now:
If you are a fan of the old two-column layout, or don’t like modern design tropes such as mega headlines, Hydejack lets you revert these changes on a case-by-case basis via configuration options. ↩︎
Search was mainly tested for English and German. Please let me know about issues in other languages. While I’ve tried to find a multi-language solution, most showed drastically worse results for the English base case. If you’re technically inclined, you can adopt the code located in _includes/js/search-worker.js to your needs. ↩︎