cothi / algorithmcode

알고리즘 스터디 공간

#include <iostream>
#include <string>

using namespace std;
class Cothi {
  public:
    Cothi() {
      name = "jiung han";
      role = "Software Engineer";
      currentFocus = "I am focusing on backend technologies.";
      portfolio = "https://cothi.github.io/";
      blog = "https://wooong-dev.tistory.com/";
    }
  void sayHi() {
    cout << "Hello";
  }
  private:
    string name;
    string role;
    string portfolio;
    string currentFocus;
    string blog;
};
int main() {
  Cothi me;
  me.sayHi();
}

---

type	badge
algorithm

algorithmcode's Issues

test

test

https://github.com/hanjiung/AlgorithmCode/blob/20b2b368765c3cb47ec08cc09287ec4dc7db8e52/jiung/Greedy/3-6.cpp#L22

BOJ#2042 구간합 구하기

#include <iostream>
#define TREE 1000001
using namespace std;


class SegmentTree{
  public:
  int tree[TREE*4];

  SegmentTree()=default;
  int intiTree(int start, int end, int node,int *arr);
  int Sumtree(int start, int end, int node, int left, int right);
  void Change_node(int start, int end, int node,int* arr, int change, int val);
};

int SegmentTree::intiTree(int start, int end, int node, int* arr){
  int mid = (start+end)/2;
  if(start==end)  return tree[node]=arr[start];
  return tree[node] = intiTree(start, mid, node*2,arr) + intiTree(mid+1, end, node*2+1,arr);
}

int SegmentTree::Sumtree(int start, int end, int node, int left, int right){
  if(end<left || right<start) return 0;
  if(left<=start&&end<=right) return tree[node];
  int mid = (start+end)/2;
  return Sumtree(start,mid,node*2,left,right) + Sumtree(mid+1,end,node*2+1,left,right);
}

void SegmentTree::Change_node(int start, int end, int node, int *arr, int change, int val){
  if(end<change||change<start)  return;
  if(change>=start&&change<=end){
    tree[node]=tree[node]-arr[change]+val;
    if(end==start) return;
  }
  int mid = (start+end)/2;
  Change_node(start,mid,node*2,arr,change,val);
  Change_node(mid+1,end,node*2+1,arr,change,val);
  return;
}

int N,M,K;
int a,b,c;


int main() {
  SegmentTree trees;

  int arr[TREE];
  cin>>N>>M>>K;

  for(int i=1;i<=N;i++){
    cin>>arr[i];
  }

  trees.intiTree(1,N,1,arr);
  while(M+K>0){
    cin>>a>>b>>c;
    if(a==1) {
      trees.Change_node(1,N,1,arr,b,c);
      M--;
    }
    else{
      cout<<trees.Sumtree(1,N,1,b,c)<<endl;
      K--;
    }
  }
return 0;
}

test

test

test

시간초과

문제: https://www.acmicpc.net/problem/1874

현재 상태: 해결완료

문제점: 시간 초과가 되어서, 제출기간이 밀릴 것 같습니다.

/******
 * Author      :    Jiung
 * Filename    :    1874.cpp
 * Version     :    Apple clang version 12.0.0 (clang-1200.0.32.27)
 * Date        :    2021-02-08
 * Copyright   :    Free
 */
  
#include <iostream>
#include <string>
#include <queue>
#include <deque>
using namespace std;


deque<int> stack;
deque<int> command;
deque<char> ans;
int main()
{
    int N, command1;
    cin >> N; 
    int i=1;

    // 예제입력
    while(i <= N)
    {
        cin >> command1;
        command.push_back(command1);
        i += 1;
    }
    
    i=1;
    stack.push_back(i);
    ans.push_back('+');
    
    while(command.size()) {


        if (stack.empty()) {
            ans.push_back('+');
            i += 1;
            stack.push_back(i);
        }

        if (stack.back() == command.front()) {
            ans.push_back('-');
            stack.pop_back();
            command.pop_front();

        
        } else if (stack.back() > command.front()) {
            cout << "NO";
            return 0;

        } else { 
            ans.push_back('+');
            i += 1;
            stack.push_back(i);
        }

    }
    
    i=0;
    int size = ans.size();
    while (i < size) {
        cout << ans[i] << "\n";
        i += 1;
    
    }



    i=0;
    while (i < ans.size()) {
        cout << ans[i] << "\n";
        i += 1;
    }
}

  

현재 작성 중인 스택 구현 코드인데,,, 시간초과 문제로 계속 수정하고 있습니다.

마인크래프트 문제

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
import kotlin.collections.LinkedHashMap


fun main() = with(BufferedReader(InputStreamReader((System.`in`)))) {
    val data = StringTokenizer(readLine())
    val hash = LinkedHashMap<Int,Int>()
    with(data){
        val y = nextToken().toInt()
        val x = nextToken().toInt()
        val block = nextToken().toInt()
        for(i in 0 until y){
            val line = StringTokenizer(readLine())
            for(j in 0 until x){
                line.nextToken().toInt().setCount(hash)
            }
        }
        println("${hash.getResult(block).first} ${hash.getResult(block).second}")
    }
}

fun Int.setCount(map : LinkedHashMap<Int,Int>){
    var count = map[this] ?: 0
    map[this] = ++count
}

fun LinkedHashMap<Int,Int>.getResult(block : Int) : Pair<Int,Int>{
    val PUT_BLOCK_TIME = 1
    val REMOVE_BLOCK_TIME = 2
    var result = 0
    var minTime = Int.MAX_VALUE

    forEach {
        var item = block
        val data = it
        var time = 0
        forEach {searchData ->
            if(data!=searchData){
                val need = data.key - searchData.key
                val tempBlock = need*searchData.value
                if(need < 0)
                    time -= tempBlock*REMOVE_BLOCK_TIME
                else
                    time += tempBlock*PUT_BLOCK_TIME
                item -= tempBlock
            }
        }

        if(minTime >= time && item >= 0){
            if(minTime!=time||(minTime == time && result < data.key)){
                minTime = time
                result = data.key
            }
        }
    }
    return Pair(minTime,result)
}