검색결과 리스트
전체에 해당되는 글 249건
- 2011.10.28 C언어 - 긴 문자열 초기화
- 2011.10.28 블랙 구글
- 2011.10.28 S1080 사용 후기
- 2011.10.27 [TED] 30일동안 새로운 것 도전하기
- 2011.10.27 밴치마크 테스트
- 2011.10.27 연결성 문제를 위한 가중 퀵병합 방식
- 2011.10.27 재밋는? 러시아 페인트공 알고리즘
- 2011.10.27 냅색(Knapsack:배낭) 문제
- 2011.10.27 토끼와 거북이 알고리즘
- 2011.10.27 XOR 교체 알고리즘
글
C언어 - 긴 문자열 초기화
EXAMPLE
char str[]="행복이라함은 성공해서 풍요롭고 여유롭게 사는것이라 생각해 왔었다.\
돈 많이 벌고, 착한 마누라랑 멋들어지게 사는거 말이다.\
사실 이렇게 되어도 행복하게될지는 알 수 없다.";
(2) " " (큰따옴표)로 묶어주기
EXAMPLE
char str[]="행복이라함은 성공해서 풍요롭고 여유롭게 사는것이라 생각해 왔었다."
"돈 많이 벌고, 착한 마누라랑 멋들어지게 사는거 말이다."
"사실 이렇게 되어도 행복하게될지는 알 수 없다.";
EXAMPLE 2
char str[]="행복이라함은 성공해서 풍요롭고 여유롭게 사는것이라 생각해 왔었다."
"돈 많이 벌고, 착한 마누라랑 멋들어지게 사는거 말이다."
"사실 이렇게 되어도 행복하게될지는 알 수 없다.";
결론
(2) 의 방법이 코드를 정렬하기에 더 좋다.
만일 (1)의 방법으로 EXAMPLE 2 와같이한다면 사이에 공백(또는 TAB 문자)가 들어가게 된다.
'C > C' 카테고리의 다른 글
| 포인터는 왜 어려울까? (0) | 2011.11.03 |
|---|---|
| 헤더 파일의 중복 정의 막기 (0) | 2011.10.28 |
| c/c++ 2차원(이차원) 배열 동적할당 방법2 (0) | 2011.10.23 |
| C언어 할 때 알면 좋은 것 (0) | 2011.10.20 |
글
http://www.blackle.com
구글은 바탕이 흰색이지만 Blackle은 검정색입니다. 이름도 구글 앞의 Goog를 빼고 Black으로 바꾸었습니다. 이렇게 검정 바탕으로 하는 이유는 흰색보다 검정색이 에너지를 덜 소모한다는 것이죠. 사용하는 사람은 전기세를 아껴서 좋고, 지구 전체로 따지만 에너지를 아껴서 좋고.
바탕을 검정으로 바꾸어서 얼마나 에너지를 아끼는지 모르겠습니다만, 아낄 수 있다면야 좋은 일이죠.
흠~ 좀 찔리는데요. ^^;
출처 : 블랙 구글?
'I > info' 카테고리의 다른 글
| Hotspot Shield && Simple AdBlock (0) | 2011.10.30 |
|---|---|
| Notepad++ (0) | 2011.10.28 |
| 화면캡쳐 for win & mac (0) | 2011.10.27 |
| Daum 꼬마사전 (영단어 자동검색 사전) (0) | 2011.10.27 |
| 하드디스크를 샀는데 용량이 작다! (0) | 2011.10.27 |
글
S1080 사용 후기
------------------ S1080 산지 두달 후 사용 후기
우선 배송이 너무 많이 지연되었다는 점에서는 상당히 불만이 많았다.
그래도 사은품은 잘 받았긴 했지만 그리 도움은 되지 않았고...
다만 제품만은 상당히 쓸만했다.
win 8 개발자 버젼도 설치 해보고 이것저것 실험도 해보고
여느 다른 넷북과 차이점은 없어 보이지만.. 휴대성 만큼은 점수를 크게 주고 싶다.
시야각 또한 안 좋긴하지만.. 우선 화면 보는데 크게 지장은 없으므로 패스
USB 나 인터페이스들이 잘되어 있어서 다른 패드들보단 편리한거같다.
또 다른 장점은 윈도우 운영체제라 사용하기 익숙하고 이것저것 할 수 있다는 점?
윈도우 패드는 현재? 우리나라에 많이 나와있지 않아서 관심 끌기용으로도 좋다 ㅋ
하지만 나에겐 노트북이 있는 상태이므로.. 결국엔 서브용으로도 잘 안쓰게 되는....
결론은 사용할 만하지만.. 아직도 부족한 점이 있다 정도?
만일 win 패드를 사실 분이 있다면.. 한 번 다시 고민해보시고 사시길..
(윈도우 운영체제는 터치를 위해 만들어진게 아니니.. 무언가 불편한 점이 보일것이다.(단 윈 8은 예외))
글
[TED] 30일동안 새로운 것 도전하기
'V > Video' 카테고리의 다른 글
| iPad Alternatives 10.1" Windows 7 Tablet (0) | 2011.10.23 |
|---|---|
| Windows 7 vs iPad (0) | 2011.10.23 |
글
// 위에 있는 게 S1080 성능 ( N570 Atom 1.66g ram 2g 내장 그래픽)
// Asus K52J Series 성능 ( i5 M 450 2.40g ram 4g 그래픽 geforce 310m)
// 데스크 탑 성능 ( i7 2600 3.4GHz ram g.skill 4g 그래픽 gtx 560ti)
'C > Com' 카테고리의 다른 글
| 이상적인 Com? (0) | 2011.11.05 |
|---|---|
| S1080 사용 후기 (0) | 2011.10.28 |
글
연결성 문제를 위한 가중 퀵병합 방식
// 가중 퀵병합
#include <stdio.h>
#define N 50
int main(void)
{
int i, j, p, q, id[N], sz[N];
for(i=0; i<N; i++) // 초기화
id[i] = i, sz[i] = 1;
while(scanf("%d %d", &p, &q) == 2){
for(i = p; i != id[i]; i = id[i]); // p의 부모 노드 찾기
for(j = q; j != id[j]; j = id[j]); // q의 부모 노드 찾기
if(i == j) // 부모노드가 같을 경우 패스
continue;
if(sz[i] > sz[j]){
id[j] = i, sz[i] += sz[j];
} else if(sz[i] <= sz[j]){
id[i] = j, sz[j] += sz[i];
}
}
for(i=0; i<N; i++) // 출력 예
printf("%d ", id[i]);
puts("");
return 0;
}
+++++++ 절반 분할에 의한 경로 압축 +++++++ // 이것을 하는 것과 안하는 차이는 미묘하다고 전해짐
for(i = p; i != id[i]; i = id[i])
id[i] = id[id[i]];
for(j = q; j != id[j]; j = id[j])
id[j] = id[id[j]];
'A > Algorithm' 카테고리의 다른 글
| KMP 알고리즘 (0) | 2011.10.28 |
|---|---|
| 재밋는? 러시아 페인트공 알고리즘 (0) | 2011.10.27 |
| 냅색(Knapsack:배낭) 문제 (0) | 2011.10.27 |
| 토끼와 거북이 알고리즘 (0) | 2011.10.27 |
| XOR 교체 알고리즘 (0) | 2011.10.27 |
글
재밋는? 러시아 페인트공 알고리즘
다음날 페인트공은 겨우 150야드만 칠했습니다. 그래도 책임자는 "음, 어제 만큼은 못하지만, 여전히 손놀림이 좋아. 150야드도 대단하지."라며, 1코펙을 주었습니다.
그 다음날 페인트공은 30야드를 칠했습니다. 책임자는 "고작 30야드라니! 용납할 수 없네! 첫날에는 어떻게 오늘보다 10배를 넘게 칠한건가? 도대체 뭐가 문제야?"라고 윽박질렀습니다.
풀이 죽은 페인트공은 이렇게 말했습니다. "저도 어쩔 수 없었습니다. 매일 페인트통에서 점점 멀어지니까요."
이것이 러시아 페인트공 알고리즘이다. 자... 이제 다음의 C언어 코드를 보자... 두 문자열을 합하는 코드이다. 무엇이 문제일까??
{
while (*dest) dest++;
while (*dest++ = *src++);
}
아주 간단하면서도 명확해 보이는 코드이다. 물론 동작도 잘 한다. 하지만 과연 성능도 괜찮을까?? 위의 함수로 아래의 코드를 실행한다고 생각해 보자. 여러 사람의 이름을 문자열 하나에 이어 붙이는 문제이다.
bigString[0] = '\0';
strcat(bigString, "John, ");
strcat(bigString, "Paul, ");
strcat(bigString, "George, ");
strcat(bigString, "Joel ");
이 함수(strcat)는 러시아 페인트공 알고리즘을 사용하고 있다. 한 문자열을 이어 붙이기 위해서는 이전의 문자열의 끝을 찾아 문자열 처음 부터 끝까지 이동을 해야 한다. C언어는 ASCIZ 문자열 타입을 사용하기 때문이다. ASCIZ는 문자열 끝이 영(Zero)로 끝나는 ASCII라는 뜻이다. 파스칼 같은 경우는 ASCII 문자열을 사용하지만 문자열의 길이를 저장하기 때문에 문자열 끝이 영으로 끝날 필요가 없어 ASCIZ를 사용한다고 볼 수는 없다.
자... 그럼 저 strcat 함수를 바꿔보자.
{
while (*dest) dest++;
while (*dest++ = *src++);
return --dest;
}
char * p = bigString;
bigString[0] = '\0';
p = mystrcat(p, "John, ");
p = mystrcat(p, "Paul, ");
p = mystrcat(p, "George, ");
p = mystrcat(p, "Joel ");
'A > Algorithm' 카테고리의 다른 글
| KMP 알고리즘 (0) | 2011.10.28 |
|---|---|
| 연결성 문제를 위한 가중 퀵병합 방식 (0) | 2011.10.27 |
| 냅색(Knapsack:배낭) 문제 (0) | 2011.10.27 |
| 토끼와 거북이 알고리즘 (0) | 2011.10.27 |
| XOR 교체 알고리즘 (0) | 2011.10.27 |
글
냅색(Knapsack:배낭) 문제
출처 : http://devils9curse.tistory.com/11
냅색 문제라는 것이 있습니다.
주어진 가방이 있을 때 가치가 최대한이 되도록 물건을 담는 것이죠.
그런데 각 물건은 무게가 있어서, 원하는 만큼 전부 가방에 담을 수는 없습니다.
이런 냅색 문제에는 여러가지 종류가 있는데요, 거의 대부분 다이나믹으로 해결할 수 있습니다.
우선 한 물건당 물건의 수량이 1개밖에 없고 물건을 쪼갤 수도 없는 0/1 냅색이 있습니다.
이 경우의 다이나믹 테이블 정의와 점화식은 다음과 같습니다.
(W[i]:i번째 물건의 무게, P[i]:i번째 물건의 가치
D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]]+P[i]) :(j>=W[i])
=D[i-1][j] :(j<W[i])
01Knapsack.cpp그리고 물건을 쪼갤 수는 없지만 물건의 수량이 여러개인 경우로 변형을 할 수 있는데요,
일단 물건의 개수가 유한개로 주어진 경우에는 두가지 풀이가 있습니다.
하나는 각 물건당 여러개를 담았을 때의 무게와 가치를 전부 데이터에 넣어서 0/1 냅색을 하는 것이죠.
또 다른 방법은, 다이나믹을 약간 다르게 돌리는 것입니다.
D[i][j]:i물건까지를 j크기의 가방에 담았을 때 최대 가치
D[i][j]=MAX(D[i-1][j],D[i-1][j-W[i]*k]+P[i]*k) :(j>=W[i]*k)
=D[i-1][j] :(j<W[i]*k)
별 차이는 없죠?
물건의 개수가 무한개로 주어지는 경우를 보겠습니다.
이번에는 1차원 다이나믹만으로도 해결이 가능합니다.
D[j]:j크기의 가방에 담았을 때 최대 가치
D[j]=MAX(D[j],D[j-W[i]]+P[i]) (j>=W[i])
마지막 경우로는, 물건을 쪼갤 수 있는 경우가 되겠는데요, 이런 경우에는 그리디로도 해결이 가능합니다.
무게 1당 가치가 높은 순으로 넣을 수 있는 만큼 차례대로 넣으면 되죠.
냅색 문제는 여러 방법으로도 활용이 가능하니, 잘 알아 두시는 것이 좋습니다.
'A > Algorithm' 카테고리의 다른 글
| 연결성 문제를 위한 가중 퀵병합 방식 (0) | 2011.10.27 |
|---|---|
| 재밋는? 러시아 페인트공 알고리즘 (0) | 2011.10.27 |
| 토끼와 거북이 알고리즘 (0) | 2011.10.27 |
| XOR 교체 알고리즘 (0) | 2011.10.27 |
| 욕심쟁이(Greedy) 알고리즘 (0) | 2011.10.27 |
글
토끼와 거북이 알고리즘
출처 : http://minjang.egloos.com/1687021
영어 질문 하나. 우리가 잘 아는 이솝 우화, '토끼와 거북이'를 영어로 하면은? 학교에서 거북이는 Turtle로 배웠고 토끼는 Rabbit으로 배웠으니...
Rabbit and Turtle ?
안타깝게도 이것은 정답이 아니다. 토끼와 거북이는 영어로
Tortoise and Hare
로 쓴다. 내가 Rabbit and Turtle라는 말을 쓰자 인도친구가 웃으면서 Tortoise and Hare로 고쳐주더라.
그런데 정작 하고 싶은 이야기는...
Tortoise and Hare, 즉 토끼와 거북이 알고리즘이라는 것이 있다. 주어진 리스트에 싸이클이 있는지 없는지를, 보다 일반적으로 표현하면 주어진 함수에서 싸이클이 있는지 없는지를 알려주는 알고리즘이다. 이 알고리즘을 고안한 사람은 Floyd라는 사람이다. 알고리즘 책에서 본, 그 짧은 코드에도 불구 오묘한 기능을 하는 All Shortest Path 알고리즘을 만든 그 Floyd이다.
그림을 그려서 다시 이 문제를 설명하면,
링크드 리스트에서 O(n) 시간과 O(1) 저장 공간을 이용해서 싸이클이 있는지 없는지를 알아내어라.
만약 시간과 저장 공간의 제약이 없다면, 노드마다 방문 되었는지 기억하는 변수를 하나 두고 돌아다니면 될 것이다. 그러나 문제에서는 O(1)의 공간, 즉 이런 추가적인 변수를 둘 수 없다. 그렇다면 일반적인 방법으로는 풀기가 어렵다. 여기서 아주 기발하게 토끼와 거북이가 등장해서 싸이클 유무를 판단할 수 있다.
- 거북이는 리스트를 한 번에 한 노드씩 앞으로 나아간다.
- 반면에 토끼는 두 걸음씩 움직인다.
- 이런 과정을 계속 반복한다.
만약 리스트에 싸이클이 있다면? 그렇다면 이 둘은 언젠가 만나게 될 것이다.
그림을 그려서 확인해보자. (PowerPoint 2007 만세~)
이렇게 보다시피 언젠가는 만나게 됨을 직관적으로 알 수 있다. Wiki에는 리스트가 아닌 함수에서 싸이클 찾는 알고리즘을 Python으로 기술하고 있다. (리스트일 경우에는 단순히 함수 f를 다음 노드를 반환해주는 것으로 만들면 될 것이다.)
def floyd(f, x0):
# The main phase of the algorithm, finding a repetition x_nu = x_2nu
# The hare moves twice as quickly as the tortoise
tortoise, hare = f(x0), f(f(x0))
while tortoise != hare:
tortoise = f(tortoise)
hare = f(f(hare))
Floyd의 논문에는 단순히 싸이클의 존재 유무를 떠나 모든 싸이클 (보다 엄밀하게는 simple cycle)을 다 찾고 나열할 수 있는 알고리즘이 나와있다 (Fig. 5~8). 그러나 정확히 위의 pseudo code처럼 토끼와 거북이를 명시한 알고리즘은 아니다.
Floyd는 이런 알고리즘을 Back-tracking 알고리즘과 구분하여 Nondeterministic 알고리즘이라고 부른다. 흔히 우리가 알고 있는 Nondeterministic Turing Machine의 행동과 비슷하다. NTM에서는 다음 스텝으로 갈 때, 일반적인 Deterministic TM처럼 한 곳으로만 가는 것이 아니라 (확률에 의존적이지가 않고) 여러 군데로 가는 것을 허용한다. Floyd가 제안한 Nondeterministic 알고리즘은 이와 유사하게 multivalued function (아래 참고)을 도입하여 비결정성을 구현하고 있다. 그러나 결국 컴퓨터로 돌리기 위해서는 deterministic 해야 하니 실제 모든 루프(=싸이클)를 찾는 알고리즘을 보면 (컴파일러 최적화에서 쓰이는 것) Floyd가 제시한 알고리즘과 매우 유사하지만 모든 스텝이 결정적으로 이루어져있다. 더 이상 쓰려니 머리가 아파서 그만...
암튼 결론은 리스트에서 싸이클을 찾고 싶을 때 토끼와 거북이를 이용하라는 것.
@ Multivalued function: 간단하게 말하면, 함수는 x원소에 대응되는 y 원소가 오직 하나 뿐임에 비해 이 multivalued function은 f(x)가 여러 개의 y 값을 가지고 있음. 즉, 일반적인 함수의 정의에는 위배됨.
@ 그냥 관심있으면 보시라고 Floyd의 논문을 직접 다운 받아 여기에 올렸는데 설마 잡아가지는 않겠지...
'A > Algorithm' 카테고리의 다른 글
| 재밋는? 러시아 페인트공 알고리즘 (0) | 2011.10.27 |
|---|---|
| 냅색(Knapsack:배낭) 문제 (0) | 2011.10.27 |
| XOR 교체 알고리즘 (0) | 2011.10.27 |
| 욕심쟁이(Greedy) 알고리즘 (0) | 2011.10.27 |
| 리스트의 이차원 배열 (0) | 2011.10.13 |
글
XOR 교체 알고리즘
XOR 교체 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다.
다음은 XOR 교체 알고리즘을 구현한 C 코드이다.
void swap(int *x, int *y) { if (*x != *y) { *x ^= *y; *y ^= *x; *x ^= *y; } }
이 코드는 두 포인터가 서로 다른 메모리 공간을 가리킬 때에만 교체 연산을 수행해서 문제를 제거한다.
이 코드는 종종 다음과 같은 형태로 쓰이기도 한다.
if (*x != *y) *x ^= *y ^= *x ^= *y;
실제 사용에서의 장단점
XOR 교체 알고리즘은 대부분의 현대적인 프로세서에서는 임시 변수를 사용하는 방법보다 더 느린데, 그 이유 중 하나로는 임시 변수를 사용하는 방법은 여러 명령어를 동시에 실행할 수 있도록 (명령어 수준 병렬성) 최적화하기가 더 쉽기 때문이다. XOR 교체 알고리즘은 3 연산 모두 데이터 의존성 (Read-After-Write)을 만들기에 반드시 순서대로만 실행해야한다. 따라서 현대 비순차 프로세서나 VLIW 컴파일러가 XOR 교체 알고리즘을 최적화할 수 있는 방법은 거의 없다.
반면, XOR 교체 알고리즘은 속도가 그리 빠르지 않아도 되고 메모리 (혹은 캐시) 사용을 최소화해야 하는 환경에서는 유용하게 사용될 수 있다. 따라서 이 방식은 임베디드 개발 환경에서 많이 이용된다.
'A > Algorithm' 카테고리의 다른 글
| 재밋는? 러시아 페인트공 알고리즘 (0) | 2011.10.27 |
|---|---|
| 냅색(Knapsack:배낭) 문제 (0) | 2011.10.27 |
| 토끼와 거북이 알고리즘 (0) | 2011.10.27 |
| 욕심쟁이(Greedy) 알고리즘 (0) | 2011.10.27 |
| 리스트의 이차원 배열 (0) | 2011.10.13 |
