SCPC 1차 예선 1번

#include <cstdio>
#include <queue>
using namespace std;

unsigned long long getPower(int);
void bfs();
queue<unsigned long long> q1, q2;
int k;
unsigned long long minv;

int main() {
//    freopen("input.txt", "r", stdin);
    setbuf(stdout, NULL);
    int tc;
    scanf("%d", &tc);
    for(int i=1; i<=tc; i++) {       
        q1=queue<unsigned long long>();
        q2=queue<unsigned long long>();
        unsigned long long maxv;
        scanf("%d", &k);
        minv=getPower(k);
    //    printf("%llu\n", minv);
        if(k<=4) {
            minv=maxv=(1<<k);
        }
        else {
            maxv=getPower(k);
            bfs();
        }
        printf("Case #%d\n%llu %llu\n", i, minv, maxv);
    }   
    return 0;
}

void bfs() {
    q1.push(1);
    for(int i=0; i<k; i++) {       
    //    int cnt=0;////////////
        while(!q1.empty()) {
    //        cnt++;///////////////
            unsigned long long here=q1.front(); q1.pop();           
            unsigned long long there;
            there=here*2;
            q2.push(there);
            if(i==k-1 && minv>there) minv=there;
           
            if((here-1)%3==0 && ((here-1)/3)%2 != 0 && (here-1)/3 > 1 ) {
                there=(here-1)/3;
                q2.push(there);
                if(i==k-1 && minv>there) {                           
                    minv=there;
                }
            }
        }   
        q1=q2;
        q2=queue<unsigned long long>();
    //    printf("cnt : %d\n", cnt);
    }
}

unsigned long long getPower(int n) {
    unsigned long long ret=1;
    for(int i=0; i<n; i++) ret*=2;
    //printf("ret : %llu\n", ret);
    return ret;
}

1e9, 1e-9의 차이

출처 : http://stackoverflow.com/questions/12134345/1e-9-or-1e9-which-one-is-correct



e의 의미는 (10의 제곱을 곱한...) 이란 의미 같다.
결국 1e9은 "1에 10의 9제곱을 곱한" 이란 의미...

[OS] Introduction

공부할 내용
1. computer system의 기본적인 구조
2. operating system의 주요 요소들
3. 여러 종류의 computing environment 개요
4. open-source operating system

목차
What is an Operating System?
What Operating Systems Do
Computer-System
    -Organization, Architecture
User Interface
Computing Environments
Open-Source Operating Systems


What is an Operating System?

일단, 시스템의 정의부터 알아보자.
"A systems is a collection of components linked together and orgainized in such
a way as to be recognizable as a single unit."
음... 영어 해석하기도 어렵고 해석해도 와닿지도 않아서 네이버 국어사전을 참조하였다.
  

그렇다면, Operating System은 무엇일까?
"A collection of computer programs"
컴퓨터 프로그램들의 모음!! 운영체제는 컴퓨터 프로그램들을 모아놓은 것으로 볼 수 있겠는데, 밑에 정의가 더 남아있다.
"that integrate the hardware resources of the computer and make those resources available to a user and the user's programs, in a way that allows user access to the computer in a productive, timely, and efficient manner." 
운영체제란 user(사용자)와 user의 프로그램들이 hardware resources(컴퓨터)를 (효과적으로) 이용할 수 있게 해주는 interface(접점)이라고 볼 수 있다.

자 다시 정리해보자.
What is an Operating System?
운영체제란 무엇인가?
-> A progam that 
   운영체제도 일단은 프로그램의 일종이다. 그런데 어떤 프로그램일까?
     manages a computer's hardware
     컴퓨터 하드웨어를 관리해주는 ...
     provides basis for application programs
     프로그램들이 실행될 기반을 제공해주는...
     is an interface between a computer user(program) and the computer hardware
     즉, 컴퓨터 하드웨어와 사용자(및 프로그램)사이의 접점, 연결고리 같은 역할을 하는...

우리가 컴퓨터를 가지고 있는데, 컴퓨터는 그 자체로만 봤을 때 기계, 쇳덩어리...로 보인다. 우리(사용자, user)는 이 기계 쇳 덩어리를 이용해서 무언가를 하고 싶다. 빠르게 계산도 하고 싶고 게임도 하고 싶고, 과제도 하고 싶고... 그런데 우리가 직접 이 하드웨어를 이용한다고 해보자. 뭘 할 수 있지...? 직접 하드디스크에 파일을 저장...? 할 수 있는게 없다. 설령 할 수 있는게 있다고 해도 안쓰는 것만 못할 것이다. 그래서 OS라는 프로그램이 존재하는 것이다. OS는 우리가 하드웨어를 어떻게 써야할지, 키보드를 치면 뭐가 나오는지 등의 복잡한 것들을 생각할 필요 없게 한다. 하드웨어와 우리(사용자, 우리가 쓸 프로그램)사이에서 우리가, 그리고 우리가 쓰려는 프로그램이 하드웨어 자원(cpu, memory등)을 효율적으로, 무엇보다도 편하게 쓸 수 있도록 해주는 역할을 한다고 볼 수 있다.

Operating system goals(운영체제의 목표)
 - 유저 프로그램을 실행하고, 유저의 문제 해결을 쉽게 만들어준다.
 - 컴퓨터 시스템을 사용하기 편리하도록 만들어준다.
 - hardware resources를 효율적으로 사용할 수 있도록 한다.



What Operating Systems Do
 

OS 정리 및 공부를 시작하기에 앞서...

2학년 1학기(2015년 1학기)때 배웠던 운영체제 강의자료를 기반으로 정리해보겠다.

그리고 무엇보다...
Fall in love with OS!!

https://www.youtube.com/watch?v=PARlXpQQPy0

BOJ 11014 컨닝2

이 문제는 최대 독립 집합(Maximum Independent set) 문제이고, 최대 독립 집합 문제가 NP-Hard지만 이분 그래프에서는 전체 정점에서 최대매칭의 개수를 뺀 것과 같다. (minimum vertex cover의 여집합이기도 하다.)

구현 자체는 이분매칭 코드 구현과, 주어진 데이터를 이분 그래프(bipartite graph)로 만드는 것이 전부라 별로 어렵지 않았는데, 이상하게 틀린 답이 나왔다.

그래서 뭘까 고민하면서 배열에 값이 잘못 들어갔나 해서 일일이 출력도 해보고 확인했는데도 원인을 못 찾다가... 직접 그려보다가 깨달았다.

나는 홀수 열 기준으로 이분 그래프를 만들었는데, 문제는 짝수열과 인접한 대상을
<왼쪽 위 대각선, 오른쪽 위 대간선, 왼쪽, 오른쪽> 이렇게 4방향만 생각했고, 연결했다.
물론 4방향이 맞긴한데, 문제는 짝수열 입장에서의 홀수열로 왼쪽 위 대각선, 오른쪽 위 대각선 부분을 빼먹고 연결 안하게 된 것이다.

결국 홀수열쪽에서 연결할 때는 <위, 아래> 이 2방향만 빼고 다 연결해줘야 할 것 같다.
아직 시도는 안해봤는데 한 번 직접 해봐야겠다.

오 역시 바로 4개 방향에서 2개 방향을 더 추가 해주니 결과가 제대로 나온다!!
이제 제출 해봐야지...

제출해보니 맞았습니다!!가 나왔다.

요즘 느끼는 거지만 알고리즘, 문제 해결도 제대로 열심히 하면 재밌는 것 같다.
즐겁게 하자!

//다시 풀어보면서 인접 리스트를 이용한 maximum flow를 구현했을 때 시간초과,
bipartite match를 구현했을 때는 런타임 에러를 받았다.
계속 원인을 생각도 못하다가... 결국 감사하게도 찾았는데... 바로 테스트 케이스가 다음으로 넘어갈 때마다 adj를 초기화해 주지 않은 것이 문제였다....!!!

BOJ 1348 주차장 runtime error

원인은... memset에 있었다....

시간을 조금이라도 줄인답시고... memset(visited, false, sizeof(car)*4)로 했는데...
visited 배열은 boolean배열이므로... sizeof(car)*4가 아닌 sizeof(car)*1을 해야한다...

devC++에서는 runtime error가 안뜨는데... 휴..
ubuntu에서 해봐야겠다. ubuntu에서도 안뜨네.. 옵션같은 것을 걸어줘야되나..음 모르겠다.

그리고 저런 것은 에러가 나도 찾기가 힘드니... sizeof(visited)를 그냥 쓰거나.. 그냥
vector<bool>(car.size(), false)로 초기화를 해주거나 하자...


그리고 또하나... 에러 찾느라 엄청 고생한 것...
-> 이분매칭 구현 코드에서 dfs부분...if(bMatch[b]==-1 || dfs(bMatch[b]))로 해야되는데,
나도 모르게 if(bMatch[b]==-1 && dfs(bMatch[b]))로 했다가 에러찾느라 고생했다. 설마 여기서 실수했을 줄이야... 근데 왜 에러가 생긴거지-> 생각해보니까 && 해놓으면 dfs(-1)이 호출될 수 있어서 배열 범위를 넘어가게 되는 것 때문에 에러가 생긴 것 같다.

주의하자...!