본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

분류 전체보기580

힙(Heap) 고득점 kit 풀이 완료, 후기 힙으로 우선순위 큐를 구현한다면, 삽입과 삭제가 모두 O(logn)으로 이루어진다. 시간복잡도 계산 시 logn은 거의 상수로 봐도 무방할 정도다. 완전히 상수는 아니지만 n과 비교해도 엄청난 차이임을 알 수 있다. 삽입, 삭제가 원활하게 이루어져야 하는 프로그램에서는 힙구조 우선순위 큐를 이용하면 매우 좋다. C++에서 priority_queue 라이브러리를 사용하는 방법에 대해 포스팅해둔 글이 있으니 참고하면 좋을 것이다. 구조체의 특정 요소(변수)를 기준으로 우선순위를 정하는 방법도 같이 설명해두었다. kimcoder.tistory.com/110?category=887628 삽입, 삭제 모두 O(logn)!! STL priority_queue 소개 priority_queue는 큐에 데이터가 삽입, .. 2020. 10. 8.
[Heap, 난이도 중상] 프로그래머즈, 디스크 컨트롤러 본인이 짠 소스 코드의 전체적인 처리 과정은 이렇다. 1. 작업 길이가 짧은 작업을 우선으로 하는 우선순위 큐에 모든 작업들을 push한다. 2. 우선 순위 큐의 top은 가장 작업 길이가 짧은 작업인데, 현재 시간을 기준으로 아직 디스크에 들어오지 않은 작업이라면 당장 실행할 수 없으므로 임시 저장벡터에 빼둔다. 당장 실행할 수 있는 작업이 나올 때 까지 반복해준다. 3-1. 당장 실행할 수 없는 작업이 하나도 없을 수도 있다. 이 때는 앞으로 제일 먼저 들어오는 작업들중 작업 길이가 짧은 작업을 실행해주면 된다. 현재 시간은 이 작업이 끝나는 시간으로 바꿔주면 된다. 3-2. 당장 실행할 수 있는 작업이 있다면 우선 순위 큐의 top에 해당하는 작업을 수행해주고, 현재 시간은 3-1과 마찬가지로 이 .. 2020. 10. 8.
[그래프, 난이도 중] 프로그래머즈, 순위 n명이 있고 일부의 승패 관계를 알 수 있을 때, 어떤 조건에서 자신의 정확한 순위를 알 수 있는지 알아내야 한다. 본인이 해결한 방법은 이렇다. 전체 인원 수는 n명이고 자신이 이기는 사람(우위)을 a명이라고 하고 자신을 이기는 사람(열위)을 b명이라고 하자 이 때 a+b=n-1 식이 성립해야 한다. 예를 들어 총 10명이 있다고 하자. 자신이 7명은 확실히 이길 수 있고 2명에게는 확실히 패배한다. 그렇다면 순위는 10위~4위(7명) 2020. 10. 8.
[그래프, 난이도 중] 프로그래머즈, 가장 먼 노드 노드 번호와, BFS의 깊이 변수를 가지는 구조체 node를 만들고 BFS를 수행했다. 큐에 담을 인접 노드가 하나도 없는 노드(이미 방문한 노드들 뿐)는 단일 노드라는 의미이므로, 이 노드는 가장 먼 노드의 후보가 된다. 아래 소스 코드에서 finished라는 bool 타입의 변수는, 큐에 담을 인접노드가 하나 이상 있는가의 여부를 판단한다. 가장 먼 노드의 후보로 꼽힌 노드들의 depth를 모아서 이들중 최댓값을 찾고, depth가 최댓값인 요소가 몇개 있는지 계산하면 문제가 해결된다. 테스트 케이스 9개 모두 통과 #include #include #include using namespace std; struct node{ int num; int depth; }; queue q; vector a[20.. 2020. 10. 7.
[Heap, 난이도 중하] 프로그래머즈, 더 맵게 scoville의 길이 제한이 1,000,000인 것을 보아 힙을 쓰지 않으면 통과할 수 없는 문제라는 것을 알 수 있다. 이 문제 역시 힙의 원리로 돌아가는 priority_queue 라이브러리로 해결하면 쉽게 풀 수 있다. 삽입, 삭제 모두 시간 복잡도가 O(logn)이기 때문에 최고의 시간 복잡도로 해결할 수 있는 것이다. 오름차순으로 정렬하여, pop할 때 가장 작은 원소가 나오게 하였고 이렇게 덜 매운 순위 1,2위를 뽑아서 주어진 공식에 맞게 새로운 스코빌 지수를 계산하여 pq에 push해주는 과정을 반복했다. pq의 top은 최소 스코빌지수를 나타내므로 pq.top()이 K이상일 경우 반복문을 종료하고, pq.top()이 K미만인데 pq에 원소가 1개 이하라면 더 이상 섞을 수 있는 상태가 .. 2020. 10. 7.
[React] Router 실습 (+배포 완료, 소스코드 공유) React로 간단한 웹을 만들어보았는데, 제작하면서 확연히 느낀 React의 특징이 있었다. 가독성이 좋음 - 컴포넌트들을 여러 파일로 쪼개서 조립하는 원리여서 소스코드가 복잡하지 않다. 유지보수에 좋음 - 위의 이유로 중복 코드도 많이 줄일 수 있고, 좋은 가독성에 따라 물론 유지보수도 훌륭하다. 속도가 매우 빠름 - 일반 웹사이트들끼리 링크로 넘나들때의 로드 시간은 1초정도 걸리는데에 반해, React Router은 컴포넌트만 가져오는 식이라 눈깜짝할새에 로드된다. 웹사이트 주소 jooyeokkim.github.io/React-SimpleProject-Algorithm/ React App jooyeokkim.github.io 깃허브 소스코드 github.com/jooyeokkim/React-Simpl.. 2020. 10. 7.
[Node.js] 파일 조회/읽기/parse (File path 간단 설명) 1. 파일 조회 fileread.js에 대한 설명 number의 폴더에 있는 파일들의 목록을 확인하려고 한다. number폴더는 fileread.js의 상위 폴더에 있으므로 폴더 경로를 '../number' 로 지정한다. 그리고 파일시스템 모듈을 가져온 후, readdir함수로 다음과 같이 해당 폴더의 파일 이름 리스트를 배열로 반환시켜준다. var f = '../number'; var fs = require('fs'); fs.readdir(f,(error,filelist)=>{console.log(filelist)}); 2. 텍스트 파일 읽기 fileread.js 에 대한 설명 require('fs') 로 파일 시스템 모듈을 가져온다. readFile함수로 인해 lable.txt에 있는 텍스트가 dat.. 2020. 10. 6.
Greedy(탐욕법) 고득점 kit 풀이 완료, 후기 다이나믹 알고리즘은 이전에 계산했던 값들을 기반으로 현재의 값을 계산해 나가는 알고리즘인 반면, 탐욕(그리디) 알고리즘은 현재의 순간 가장 최적이라고 판단한 경우를 선택하는 알고리즘이다. 다이나믹 알고리즘과 다르게 그 순간에서의 최선의 경우에만 신경 쓰므로 욕심쟁이 알고리즘이라고도 불리는 것이며, 항상 최적의 답이 될거라는 보장은 없다. 그리디는 정렬을 필요로 하는 경우가 많으며, 종종 큐, 스택, DFS등 다른 알고리즘과도 연계된다. 프로그래머즈의 그리디 고득점 kit 문제들은 6문제 모두 어느정도 밸런스가 맞았다. "체육복"을 제외 하고는 적당히 난이도를 갖춘 문제들이었다. 문제 모음 [난이도 중] 단속 카메라 kimcoder.tistory.com/97?category=879354 [난이도 중하] 체.. 2020. 10. 5.
[그리디, 난이도 중] 프로그래머즈, 큰 수 만들기 문자열로 주어진 정수에서 k개의 수를 제거해서 만들 수 있는 가장 큰 수를 계산하는 문제이다. 백준에서 이런 유형의 문제를 풀었던 기억이 있었던 덕에 금방 해결할 수 있었다. 본인의 접근법은 스택의 원리를 이용하는 것이다. 순서대로 정수를 벡터에 넣으며, 기존 벡터의 마지막 인덱스 값(스택 상에선 top)이 현재 push한 정수보다 작을 경우 이 마지막 인덱스 값을 제거해주는 과정을 반복한다. 제거할 때마다 k의 카운트는 1씩 감소시켜야 한다. 해당 규칙으로 입력값의 정수들을 모두 벡터에 넣었음에도 불구하고 수를 k만큼 제거하지 못했을 경우도 있다. 이 과정까지 잘 수행 했다면 벡터의 요소는 ex) (5,4,3,2,1), (7,5,3,2,1), (9,9,7,7,5,5) 같이 내리막수일 것인데, 남은 k가.. 2020. 10. 5.

티스토리툴바