JArchive 프로그래밍 일기

이중우선순위큐 문제링크 

리뷰 

최소값 삭제와 최대값 삭제를 위해 매번 큐의 정렬을 다시 할 수 는 없다. 그래서 우선순위큐 2개를 뒀다. 

우선순위큐의 기본 정렬은 less라서 오름차순이다. 

오름차순 정렬하는 최소값 큐 min_pq

내림차순 정렬하는 최대값 큐 max_pq 

큐 사이즈를 관리하는 변수가 0이 되면, 큐 2개 다 비워줘야하는데! 이 부분을 빠뜨려서 다른 분 코드를 참고했다. 

1. priority_queue 2개 사용한 코드 

#include <string>
#include <vector>
#include <queue>
using namespace std;

priority_queue<int, vector<int>, greater<>> min_pq;
priority_queue<int, vector<int>, less<>> max_pq;
int pq_size; // 큐의 사이즈 관리

vector<int> solution(vector<string> op) {
  vector<int> answer = {0, 0};

  for(auto s : op){
    string order = s.substr(0, 1); // 명령 문자 I 또는 D 

    int num = stoi(s.substr(2, s.size())); // 숫자부분  

    if(order == "I") {
      min_pq.push(num);
      max_pq.push(num);
      pq_size++;
    }
    else if(pq_size > 0 && order == "D"){

      (num == -1) ? min_pq.pop() : max_pq.pop();
      pq_size--;

      if(pq_size == 0){
        while(!min_pq.empty()) min_pq.pop();
        while(!max_pq.empty()) max_pq.pop();
      }
    }
  }

  if(!min_pq.empty() && !max_pq.empty()) answer = {max_pq.top(), min_pq.top()};
  return answer;
}

풀고 나니깐 다른 분들 코드에 set이 보이길래 multiset으로 풀어도 됬겠다 싶었다.  

2. vector 로 푼 코드 

앞, 뒤에서 하나씩 erase로 지워주기만 하면 되니까. vector로도 괜찮다. 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> solution(vector<string> op) {
  vector<int> answer = {0,0};
  vector<int> v;

  for(auto s : op){
    string order = s.substr(0, 1); // 명령
    int num = stoi(s.substr(2)); // 숫자

    if(order == "I") {
      v.push_back(num);
      sort(v.begin(), v.end(), greater<>()); // 푸시하고 바로 정렬.
    }
    else {
      if(v.size() == 0) continue;

      (num == -1) ? v.erase(v.end()-1) : v.erase(v.begin());
    }
  }

  if(!v.empty()) {
    answer.clear();
    answer = {v[0], v[v.size()-1]};
  }
  return answer;
}

정수 삼각형 문제 링크 

리뷰 

등굣길 문제와 비슷하게 느껴졌다. 

삼각형의 가로 세로는 500이하라는 조건이 있으니까 점화식 값을 저장할 DP배열 크기를 501, 501로 잡아둔다. 

최대 합을 구하려면, 반드시 1층부터 마지막층까지 이동해야 한다. 

모든 층의 첫번째 칸은 바로 위에서만 올 수 있다. 

모든 층의 마지막 칸은 왼쪽 위에서만 올 수 있다. 

이 2가지 예외를 제외하고, 아래와 같은 점화식을 만족한다. 

D[a][b] = max(D[a-1][b] , D[a][b-1]) + 현재칸의 값 A[a][b]

맞았습니다 코드 

#include <string>
#include <vector>
using namespace std;

int D[501][501];

int solution(vector<vector<int>> t) {
  int answer = 0;

  D[0][0] = t[0][0];
  D[1][0] = t[1][0] + D[0][0];
  D[1][1] = t[1][1] + D[0][0];

  int height_t = t.size();

  for(int i = 2; i < height_t; i++){

    for(int j = 0; j <= i; j++){
      if(j == 0) D[i][j] = t[i][j] + D[i-1][j];
      else if(j == i) D[i][j] = t[i][j] + D[i-1][i-1];
      else{
        D[i][j] = t[i][j] + max(D[i-1][j], D[i-1][j-1]);
      }
    }
  }

  for(int i = 0; i < height_t; i++){
    answer = max(answer, D[height_t-1][i]);
  }

  return answer;
}

등굣길 문제링크 

리뷰 

최단 경로를 세야 하니까 오른쪽 또는 아래로만 이동해야 한다. 

그래서 특정 지점까지 몇번을 거쳐 가는지 점화식을 세야 한다. 

웅덩이가 있으면 최단경로를 세면 안되니까 처음부터 -1로 초기화 해둔다. 

현재 지점 기준으로 위, 또는 왼쪽의 최단경로를 기반으로  현재 지점의 최단경로를 계산한다. 

인덱스에 음수가 발생하지 않도록 (1, 1)을 시작점으로 두고 (1, 1)의 최단경로를 1로 초기화한다. 

핵심 코드는 아래와 같다

temp_a = (위칸이 음수가 아니라면, ) D[a-1][b] 
temp_b = (왼쪽칸이 음수가 아니라면, ) D[a][b-1] 

D[a][b] = (temp_a + temp_b) % div_num;

맞았습니다 코드 

#include <string>
#include <vector>

using namespace std;
int D[101][101]; // 최단거리를 저장할 배열
int div_num = 1000000007;

int solution(int m, int n, vector<vector<int>> puddles) {

  for(auto v : puddles){
    D[v[1]][v[0]] = -1; // 물웅덩이를 -1로 초기화
  }
  D[1][1] = 1;

  for(int i = 1; i <= n; i++){ // n: 행
    for(int j = 1; j <=m; j++){ // m: 열
      if(D[i][j] == -1) continue;
      int temp_a = 0, temp_b = 0;

      if(D[i-1][j] != -1) temp_a = D[i-1][j];
      if(D[i][j-1] != -1) temp_b = D[i][j-1];

      D[i][j] += (temp_a + temp_b) % div_num;
    }
  }

  return D[n][m];
}

문제 링크 

리뷰 

처음에 감을 못잡은 문제... 어떤 파라미터 넘겨서 탐색해야되지? 다음에 다시 풀어봐야겠다. 

맞았습니다 코드 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int global_N, target_number;
int max_cnt = 8;
int min_cnt = 1 + max_cnt;

void dfs(int cur_num, int cnt){ // (현재 숫자, N을 사용한 개수)
  if(cnt > max_cnt) return;
  else if(cur_num == target_number){
    min_cnt = min(cnt, min_cnt);
    return;
  }

  int n = 0;  // 계산할 숫자 n 
  for(int i = 1; i <= 6; i++){ // N을 1개~6개 사용가능
    // 계산할 숫자 n -> N, NN, NNN
    n = n*10 + global_N;
      
    dfs(cur_num + n, cnt + i);
    dfs(cur_num - n, cnt + i);
    if(cur_num != 0 || cnt > 8){
      dfs(cur_num * n, cnt + i);
      dfs(cur_num / n, cnt + i);
    }
  }
}

int solution(int N, int number) {
  global_N = N;
  target_number = number;
  dfs(0, 0);
  return (min_cnt == 9) ? -1 : min_cnt;
}

구매경로

애플스토어에 학교 메일로 학생 인증을 받고 교육할인을 받을 받을 수 있었다. 등록금 뽕뽑는날이 오다니. 

에어 5세대 64G를 사려고 했다가.. 22만원정도 더 보태서 프로 11을 선택했다. 

120Hz 프로모션 디스플레이를 포기할 수 없었기 때문이다. 그리고 스피커 쥭여줌.....하트하트

또한 64GB가 애매한 용량이라고 느껴졌다. 반면에 에어 256GB는 오바;

프로 11인치가 인기가 많은건가.. 영업일 3~5일 후에나 발송된다니 ㅠㅠ 

패드보다 펜슬이 먼저온다; 

정가와 할인가 비교 

교육 할인으로 7만 3천원의 이득이 있었다. 그치만 109만원 오지게비싸다..

패드의 용도

굿노트앱과 펜슬2가 탐났다!!

필자는 공부할 때 텍스트 말고도 이미지와 도식화를 최대한 활용하는 편이다. 

블로그 포스팅에서 그림추가는 충분히 가능하지만, 기존 이미지에 필기나 화살표를 더하는 것이 불편하다.

포스팅할 때 답답함이 있어서 종이에 하다보면, 구글링의 이미지를 그대로 갖다 쓰고 싶을 때가 많았다. 

내용을 끄적이고 궁금한건 바로 찾아서 내용추가를 하면서 나만의 공부노트를 정리하려고 구매했다. 

딴짓할까봐 유튜브, 왓챠 어플은 설치하지 않을 계획이다... 게임은 전혀 관심 없음. 

장인은 연장을 탓하지 않지만, ^^ 큰맘먹고 장만한 패드 버프를 받아서 열공에 박차를 가하기로 다짐했다.

케이스 입힌 내 패드💛

귀여운 스티커가 보이면 하나씩 붙이는중. 

굿노트, 유니콘https, 네이버클로바노트 앱을 유용하게 쓰고 있다. 

MOODA, 북적북적 어플은 3줄일기와 독서일기용으로 잘 나와 있어서 종종 쓰고 있다. 

쌩패드에 쌩펜으로 글씨 쓰는게 미끌거려서 어색한데. 그냥 적응하고 있다. 

종이질감 필름은 화질저하되니깐 붙여보는거를 최대한 미루고 있다. 

그리고 스피커 퀄리티가 중요한 사람은 꼭 프로를 구매하기를 추천한다. 

문제 링크 

리뷰 

항상 가장 작은 수와, 그 다음 작은 수가 필요해서 자동으로 정렬해주는 우선순위 큐를 이용했다. 

우선순위 큐에서 front()를 first로 받고, pop()후에 front()를 second로 받으면 쉽게 접근할 수 있다. 

항상 2개를 꺼내니까 pop()을 2번 해줘야하는 것을 유의하자. 

전부 스코빌지수가 K가 됬는지는 큐의 크기가 1이 됬을 때 검사한다. 

마지막 남은 원소가 K 미만이라면 answer 는 실패다. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> scoville, int K) {
  int answer = 0;
  bool result = true;

  priority_queue<int, vector<int>, greater<int>> pq;

  for(auto s : scoville){ pq.push(s); }

  while(!pq.empty()){

    if(pq.top() > K) break; // 더 검사하지 않아도 된다
    if(pq.size() == 1 && pq.top() < K) { result = false; break; } // 실패

    int first = pq.top();
    pq.pop();
    int second = pq.top();
    pq.pop();

    pq.push(first + (second * 2));
    // cout << "first: " << first << " second:" << second << ' ';
    answer++;
  }
  if(!result) answer = -1;
  return answer;
}

int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int k = 7;
  vector<int> scofille = {1, 2, 3, 9, 10, 12};
  cout << solution(scofille, k);

  return 0;
}

문제 링크 

문제 유의 사항

반드시 모든 티켓을 사용해야 한다. 

반드시 시작 공항은 ICN 이다. 

모든 티켓을 사용할 수 있는 입력만 주어진다. 

가능한 경로가 여러개 나와도, 알파벳순으로 우선하는 경로를 선택한다. (== 탐색 전 정렬 필요) 

리뷰 

DFS 구현 시, 탐색 함수 매개변수와 종료 조건이 중요하다. 

탐색 목표 : 목적지, 몇번째 방문인지. 

탐색 종료 조건 : 티켓 개수가 방문 순서와 똑같으면 모든 티켓을 사용한 것이니까 종료. 

탐색 가능 조건 : 목적지를 시작점으로 하는 티켓이 있는지 확인 && 미방문인지 확인 

1) 모든 티켓을 검사. 

탐색 가능 조건이 있다면, 방문 표시하고 답 벡터에 넣는다. DFS 탐색 시작. 

DFS탐색은 true/ false 를 리턴한다.

탐색 해보고 만약 실패라면, 다시 미방문 표시 

2) 탐색 가능 조건이 없다면, 답 벡터에서 빼고 false 리턴. 

맞았습니다 코드 

#include <bits/stdc++.h>
using namespace std;

vector<string> routes; // 정답 경로 벡터
bool visit[100002]; // 방문 체크

bool DFS(string start, int cnt, vector<vector<string>> &tickets){

  if(cnt == tickets.size()) return true; // 탐색 끝나면 true

  for(int i = 0; i < tickets.size(); i++){ // 시작점 타겟이 있는지 확인 
    if(visit[i] == false && start == tickets[i][0]){ // 미방문이고, 시작점 타겟이 맞으면, 방문!
      visit[i] = true;
      routes.push_back(tickets[i][1]); // 방문한 도착지를 답 벡터에 푸시
      bool res = DFS(tickets[i][1], cnt+1, tickets);
      if(res) return true;
      visit[i] = false;
    }
  }
  
  routes.pop_back(); // 갈 곳이 없으면, 가장 최근 도착지를 벡터에서 제거 
  return false;
}

vector<string> solution(vector<vector<string>> tickets) {

  sort(tickets.begin(), tickets.end()); // 알파벳 순 앞서는 경로 선택
  routes.push_back("ICN"); // 항상 시작은 ICN
  DFS("ICN", 0, tickets);  //시작점이 "ICN"인 티켓을 탐색

  return routes;
}