728x90
반응형

코딩테스트 93

코딩테스트 : 큰 수 만들기

해당 문제는 주어진 수에서 k만큼 숫자를 지워서 가장 큰 수를 만드는 문제이다.이 문제는 어떤 조건에 숫자를 지워야 가장 큰 수를 만들 수 있는지 파악해야한다.큰 수는 길이가 같을 때 제일 큰 자리수의 숫자가 높을 수록 큰 수라고 볼 수 있다. 그렇다면 1231234에서 세 개를 지웠을 때 나올 수 있는 경우의 수는 모두 길이가 4인 숫자이다. 즉 천의 자리 수가 가장 높은 수가 큰 수이다.이것을 이용해 문제에 적용해보면 가장 앞의 수와 그 다음 수를 비교했을 때 다음 수가 더 크다면 큰 수를 만들기 위해서 가장 앞의 수 대신 그 다음 수가 가장 앞의 수가 되어야한다.ex) 1924→ 924만약 가장 앞에 수가 다음 수보다 더 크다면 가장 앞에 수는 현재까진 가장 큰 수 이다. 이후 2번째 수와 3번째 ..

코딩테스트 : 두 큐 합 같게 만들기

해당 문제는 두 큐의 합을 같게 만들어주는 문제로 queue의 특징을 이용해서 합이 같아질때까지 원소를 옮기는 문제이다.문제를 푸는 법은 간단한데 반복문으로 원소를 옮기면서 예외 처리를 한개씩 해주면 된다.#include #include #include using namespace std;int solution(vector queue1, vector queue2) { int answer = 0; queue q1; queue q2; long sum1 = 0; long sum2 = 0; //vector에 저장되어있는 정보를 queue로 옮긴다. for(int i =0; i q1.size() + q2.size()) //실패 반환 ..

코딩테스트 : 가장 큰 수

해당 문제는 주어진 숫자들을 이용해 만들 수 있는 가장 큰 수를 만드는 문제로 앞 자리가 클 수록 앞에 배치하면 되는 문제이다.해당 부분은 복잡하게 느껴질 수 있지만, 문자열로 단순히 생각하면 쉽게 해결할 수 있다.문자열을 정렬 시키면 가장 앞에 문자부터 비교하며 같다면 다음 문자끼리 비교하는 식으로 정렬한다. 그렇다면 숫자를 문자열로 바꾼다면 어떻게 정렬이 되겠는가[3,30,34,5,9]를 내림차순으로 정렬시킨다면 9 5 34 30 3으로 정렬된다. 하지만 가장 큰 수를 만드려면 9 5 34 3 30 으로 정렬이 되야한다.때문에 내림차순으로 정렬하며 커스텀 함수를 sort에 넣어줘서 3, 30을 정렬할 때 사전순으로 더 큰 수를 뽑아야한다.(ex. 303 Sort에 대한 자세한 내용은 아래 블로그에서..

코딩테스트 : [1차] 프랜즈4블록

해당 문제는 2*2블럭이 같으면 해당 블럭을 삭제하고 삭제할 블럭이 없을 때까지 게임을 이어가는 문제로 구현해야될 것은 2가지이다.같은 블럭이 2*2인지, 같다면 블럭의 갯수를 체크하고 파괴밑에 블럭이 없다면 중력을 받아 블럭이 떨어짐.#include #include #include using namespace std;//같은 블럭으로 2*2인지 확인하는 함수bool hit(vector>>& v, int i, int j, int& count){ //블럭 파괴 여부 bool check = false; //확인할 블럭이 board안에 있는지 체크 if(j + 1 board) { int answer = 0; //어떤 블럭인지, 해당 블럭의 파괴여부 vector>> v..

LRU(Least Recently Used) - 캐시 교체 알고리즘

1. 개요LRU는 캐시 교체 알고리즘 중 하나로, 캐시에서 가장 오래전에 사용된 데이터를 우선적으로 삭제하는 방식이다.주로 메모리나 디스크 캐시에서 사용됩니다.2. 작동 원리이 알고리즘은 캐시 크기 제한이 있을 때 가장 오래된 데이터를 제거하여 새로운 데이터를 넣을 수 있는 공간을 확보하려고 합니다.가장 오래된 데이터를 제거하는 이유는 한번 사용된 데이터는 이후에도 사용될 확률이 높기 때문에 접근 속도가 빠른 캐쉬에 저장하고 가장 오래된 데이터를 삭제한다.캐시에 남아있는 데이터에 접근하는 경우가 메모리에 접근해서 데이터를 사용하는 것 보다 빠르기 때문에 이러한 방식을 사용한다.3. 동작 방식캐시 히트 (Cache Hit): 캐시에 이미 요청된 데이터가 있으면, 해당 데이터를 최신 데이터로 업데이트합니다...

코딩테스트 : [1차] 캐시

해당 문제는 LRU(Least Recently Used) 알고리즘을 사용하는 문제로 정해진 크기 만큼의 공간에 데이터를 저장하며 새로 들어오는 데이터가 저장되어있다면 맨 앞으로 빼고 아니라면 맨 뒤 데이터를 삭제하고 맨 앞에 추가하는 알고리즘이다. LRU의 자세한 설명은 아래 주소에서 확인할 수 있다.https://jinho082008.tistory.com/28첫 번째 시도#include #include #include using namespace std;int solution(int cacheSize, vector cities) { int answer = 0; vector temp; //만약 캐쉬 값이 0이라면 모든 실행시간이 5이므로 크기에 5를 곱함 if(cacheSiz..

코딩테스트 : 2 x n 타일링

해당 문제는 n이 증가함에 따라 나오는 결과 값의 규칙을 찾아내고 이를 이용해 답을 찾는 문제이다.이 문제는 n만큼의 가로 길이를 채우는 방법의 경우의 수를 구하는 문제로 2*1의 블록은 세우거나 눕혀서 채울 수 있다. 때문에 한 블럭당 가로 길이는 1,2 둘 중 한개로 결정된다.그렇다면 해당 문제의 규칙은 무엇일까? n을 한개씩 올려보면 쉽게 규칙을 찾을 수 있다.규칙 찾기더 진행해보면 알겠지만 n = (n - 1) + (n - 2)로 변화한다. 즉 n은 피보나치 수열로 결정된다.구현 방법#include #include using namespace std;int solution(int n) { int answer = 0; if(n == 1) return 1; if(n..

코딩테스트 : 오픈채팅방

해당 문제는 주어지는 record에서 상태, 아이디, 닉네임을 추출해서 알맞게 사용하는 문제로 3가지 정보 분리 후 차례대로 문제를 해결하면 쉽게 풀 수 있다.#include #include #include #include using namespace std;vector solution(vector record) { vector answer; //State와 id를 저장 vector> v; //string : id, string : name map m; //for문이 끝나면 최종 id와 그에 맞는 name이 저장된다. for(string str : record) { //공백을 기준으로 문자열을 나누어준다. stringstr..

중복을 방지해주는 자료구조 Set

set은 중복을 허용하지 않는 자료구조이다. 즉 set에 중복된 값을 넣을 시 한 번만 저장된다. set은 2가지 종류가 있는데 set과 unordered_set이다. unordered_set은 unordered_map과 마찬가지로 순서를 보장하지 않는 set이다. 일반적인 set은 순서를 보장해주며 자동으로 정렬된다. 때문에 for문을 통해 원소를 추출 시 순서대로 추출할 수 있다. set과 unordered_set은 내부 구조의 차이가 있는데 이로 인해 정렬 여부와 속도가 차이난다. 이러한 특징 덕분에 set은 안정적으로 O(log N)을 보장하며 unordered_set은 O(1) ~ O(N)의 시간 복잡도가 나온다.SetUnordered_set 때문에 정렬이 필요한 경우엔 set을 정렬은 필요 없..

코딩테스트 : 숫자 변환하기

해당 문제는 원하는 숫자를 가장 빠른게 찾는 문제로 주어진 규칙을 가지고 원하는 숫자를 빠르게 찾는 알고리즘을 만들어야한다.첫 번째 시도#include #include #include using namespace std;int solution(int x, int y, int n) { int answer = 0; //int : 현재 연산 값, int : 연산 횟수 queue> q; //초기 값 x, 연산 횟수는 없으니 0 q.push(make_pair(x, 0)); //q에 원소가 없을때까지 같은게 안 나왔다면 값이 없다는 뜻 while(!q.empty()) { //같은 값이 나왔다면 if(q.front().first == y)..

728x90
반응형