태터데스크 관리자

도움말
닫기
적용하기   첫페이지 만들기

태터데스크 메시지

저장하였습니다.
블로그 이미지
Lonewolf dlbo

calendar

1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30          

Notice

2009.02.19 22:46 Solutions/Dlbo's Solution

오차를 보정하려고 ceil과 pow를 지우려다 보니 생각보다 난해해졌습니다.

Mr.K의 솔루션에서 궁금한 점은 오차를 어떻게 커버했느냐 입죠.

-_-;

문제푸시는데 방해되지 말라고 숏코딩으로 처리했습니다.

같은 알고리즘이나 재귀호출을 이용한 방법으로 돌렸습니다.
posted by Lonewolf dlbo
TAG C, pku

댓글을 달아 주세요

  1. 아. 알고리즘이 약간 다르긴 하네요. 재귀호출로 변경하면서 기존엔 자릿수에 따라 수를 깎아내려갔지만, 이번엔 자릿수에 따라 카운트해 올라갔습니다.

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2009.02.19 23:01  Addr Edit/Del Reply

    오차를 어떻게 커버하긴

    int형 안에서 갖고 노니 오차가 날리가 ㅋㅋ

2008.12.04 22:19 Solutions/Dlbo's Solution


ㄲㄲ

다풀었심다.

아스키 코드 상으로 오른쪽으로 5칸씩 밀렸잖습니까?

그니깐 +5를 하되, +5를 했을때 영문자의 갯수인 26개, 즉 아스키 코드 값이 'Z'보다 커지면

21을 빼주면 되는 겁니다.

ㄲㄲ

근데 여기서 낚시성이 짙은게..

Cipher text가 암호화된겁니다.

-_-

고로 입력받은 문자열에 대해 각 문자마다 -5를 해 주되,

'A'의 아스키코드 값보다 작아지면 +21을 해 주면 됩니다.

-_-!
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. ㄲㄲ 곽도 인제 올리센

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.12.05 08:49  Addr Edit/Del Reply

    태그 ㅋㅋ

2008.12.01 12:57 Solutions/Dlbo's Solution


... 따로 설명하고 자시고 할 것도 없군요.

광고 수익이 더 크면 광고하고,

같으면 그냥 상관 없다 하고,

적자나면 안하면 됩니다.

ㅡ.,ㅡ;

워낙 간단해서 뭐 코드 구조도 같군요;
posted by Lonewolf dlbo

댓글을 달아 주세요

2008.11.30 00:19 Solutions/Dlbo's Solution


낄낄.

전에 지군 앞에서 숏코딩 보여줬던 문제였는데 이걸 번역하다니 -_-a
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. 내가 요새 좀 몸이 볍신이라 그래.

2008.11.28 23:18 Solutions/Dlbo's Solution


....

감기몸살때문에 무지막지하게 힘들군요 ㄱ-

다들 몸 건강히 조심하세요 ㄱ-

그나저나 Nordic 기출에서도 이런 쉬운게 있었군요;
posted by Lonewolf dlbo

댓글을 달아 주세요

2008.10.22 19:32 (임시휴재) Fanta's Post

10X10의 미로에서 01부터 100까지 가는
복수의 이동경로가 있을 경우 이동은 북, 동, 남, 서 순으로 한다.

방 번호

(입구)1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
31 32 33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48 49 50
51 52 53 54 55 56 57 58 59 60
61 62 63 64 65 66 67 68 69 70
71 72 73 74 75 76 77 78 79 80
81 82 83 84 85 86 87 88 89 90
91 92 93 94 95 96 97 98 99 (출구)100


입력
10행 10열의 1 또는 0의 값이 주어진다. (1은 벽)

출력
총 경로의 길이를 출력하고 행마다 각 방의 번호를 출력한다.

입력예시(input.txt)
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1
0 1 1 1 1 0 0 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 0 1 0 1 1 1 1
0 1 1 1 0 0 0 1 1 1
0 1 1 1 1 1 0 1 1 1
0 0 0 0 0 0 0 0 0 0

출력예시
19
1
11
21
22
23
24
25
26
36
46
56
66
76
77
87
97
98
99
100




옛날 옛적 대회에서 풀어보았던 문제 올려보았습니다.

'(임시휴재) Fanta's Post' 카테고리의 다른 글

abex1 crack  (1) 2008.11.19
포스팅 연장  (0) 2008.10.31
미로찾기  (0) 2008.10.22
구글입사문제 풀기  (5) 2008.10.19
환형 링크드리스트  (3) 2008.10.08
정보올림피아드 모험가  (5) 2008.09.25
posted by 지환태

댓글을 달아 주세요

2008.10.19 17:00 (임시휴재) Fanta's Post
"최고인재 가치는 평균적 인력의 300배"
이 기사에 구글 입사문제가 소개되어있습니다.
풀어보죠

양수 n에 대해서 1과 n 사이에 1이 나오는 횟수를 나타내는 함수를 f(n)이라고 한다. 예를 들어 f(13)=6이다. f(n)=n이 되는 첫번째 양수는 1이다. 두번째 양수는 무엇인가.

f(1)=1
     1

f(2)=1
     1,2

f(11)=4
     1,2,3,4,5,6,7,8,9,10,11
쉬워요 쉬워.


중학교 1학년 과정을 별 탈없이 진행하셨으면 전개식은 쉽게 프로그래밍하실 수 있을거에요.


이 부분에서 각 자리의 숫자를 구해줍니다.

'(임시휴재) Fanta's Post' 카테고리의 다른 글

포스팅 연장  (0) 2008.10.31
미로찾기  (0) 2008.10.22
구글입사문제 풀기  (5) 2008.10.19
환형 링크드리스트  (3) 2008.10.08
정보올림피아드 모험가  (5) 2008.09.25
재귀함수랑 친해지기 : 파스칼의 삼각형  (1) 2008.09.17
posted by 지환태
TAG C, 구글, 문제

댓글을 달아 주세요

  1. n에다가 INT_MAX를 집어넣어 버리면 시간 소모가 상당해집니다. 다른 답안을 원한건 아닐까요? ㅡ,.ㅡ;

    • Favicon of http://zfanta.com BlogIcon  환타 2008.10.19 19:53  Addr Edit/Del

      f(n)=n이 되는 2번째 수만 찾으면 되는 것 같은데....
      199981 아닌가요?

  2. f(n) = n인 경우를 찾아내라는 문제이지만.. f(n)의 값을 찾는 부분에서 알고리즘적인 옵티마이즈가 더 가능하지 싶습니다. 머리부상으로 지금 좀 안굴러가긴 한데... 공식화가 가능하지 않을까 싶습니다.(Art of Computer Programming에 너무 빠진건가 ㄱ-)

    • Favicon of http://zfanta.com BlogIcon  환타 2008.10.20 17:53  Addr Edit/Del

      찾아보니 mathclub.kr의 은빛비님은
      k 자리수일 때, n의 증가치에 비해서 최대의 f(n)값을 보여주는 최소값은 2*10^(k-1)-9일 때이다.
      즉.. 11, 191, 1991, 19991 등이다..
      2*10^(k-1) - 9 일 때, f(n)의 값은, 10^(k-1) + 2*(k-2)*10^(k-2)-8 가 된다.
      같은 수가 될 수 있는 조건은.. 2*10^(k-1)-19 일 때, 10^(k-1) + 2*(k-1)*10^(k-2)-19 이며..
      f(199,981) = 100,000 + 2*5*10,000 - 19 = 199,981
      라고 하시네요

  3. 역시 수학적으로는 뭐든 분석 가능하군요 -_-)_b;;

2008.10.08 20:46 (임시휴재) Fanta's Post

원형 큐와 비슷합니다.


//지금 포토샵이 안켜져서......

tail이 없다는 것 빼곤 링크드리스트와 같습니다.


선언



함수들


환영 링크드리스트로 원형 탁자복불복 문제를 쉽게 풀 수 있습니다.

그냥 소스

'(임시휴재) Fanta's Post' 카테고리의 다른 글

미로찾기  (0) 2008.10.22
구글입사문제 풀기  (5) 2008.10.19
환형 링크드리스트  (3) 2008.10.08
정보올림피아드 모험가  (5) 2008.09.25
재귀함수랑 친해지기 : 파스칼의 삼각형  (1) 2008.09.17
동적 배열할당  (2) 2008.09.10
posted by 지환태

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.10.08 22:05  Addr Edit/Del Reply

    환영이래서 깜짝;

    환'형'인듯 =_=;

  2. 원형큐구먼유 ㅁ_ㅁ)~ 자료구조 기말고사때 이거 배열로 크기 3짜리 고정형을 구현하라 그래서 화냈었는데 -_-;

2008.09.23 16:43 Solutions/Fanta's Solution

Run ID User Problem Result Memory Time Language Code Length Submit Time
4114901 jht009 1844 Accepted 204K 0MS C 296B 2008-09-23 15:25:49

매트릭스 포기해도 되나요????????????????????????????????
헣헣헣
GG

'Solutions > Fanta's Solution' 카테고리의 다른 글

PKU 2649. Factovisors. AC 소인수분해  (2) 2008.10.07
PKU 2649. Factovisors. AC  (7) 2008.10.06
PKU 2649. Factovisors. TLE  (1) 2008.10.05
PKU 1844, Sum. AC  (1) 2008.09.23
PKU 2017, Speed Limit. AC  (3) 2008.09.12
PKU 2027. No Brainer. AC 94B  (1) 2008.09.11
posted by 지환태
TAG C, pku

댓글을 달아 주세요

  1. 포기하셔도 따로 할 말 없음 ㄱ-; 리턴군 한번 굴릴께요 ㄱ-

2008.09.22 21:34 Solutions/Dlbo's Solution


흐음.

이번에도 쉬운 문제이지요?

1부터 N까지 숫자를 나열해 두고, 각 숫자마다 부호를 아무렇게나 둔 다음,

부호까지 붙인 수들을 합해서 S가 되게 만들되, 그 N중 최소를 출력하는 겁니다.

제 솔루션은 간단합니다.

1부터 N까지의 합을 그냥 구합니다. -_-;

이 때 1부터 N까지의 합이 S보다 크다면, S는 1부터 N까지의 숫자중 몇개를 뽑아서 만들 수 있다는 거지요.

그 말인 즉슨, S보다 큰 1부터 N까지의 합이 나와야 N이 답이 될 가능성이 있다는 겁니다.

12 = -1 + 2 + 3 + 4 + 5 + 6 - 7 이지요?

12 = 1 + 2 + 3 + 4 + 5 + 6 + 7  - 1 - 7

이리 둬봤는데...

어색하더군요. 만들 방법이 읍드만 -_-;

근데 이걸 반복하다 문득 느낀 것.

"최소일땐 1부터 N까지의 합에서 S를 뺀 게 2의 배수다 -_-!"

.... 무려 1부터 20까지 노가다를 뛰었습니다.

20까지는 맞습니다.

냈어요.

AC 됐구요.

-_-;

'Solutions > Dlbo's Solution' 카테고리의 다른 글

PKU 2649. Factovisor. get AC -_-  (8) 2008.10.07
PKU 2649. Factovisors. TLE  (4) 2008.10.02
PKU 1844. Sum. AC get!~  (1) 2008.09.22
PKU 3685. Matrix. AC get!  (5) 2008.09.20
PKU 2017, Speed Limit. AC get!  (0) 2008.09.11
PKU 2027. No Brainer. AC get~-_- - 101Byte  (5) 2008.09.11
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.23 02:21  Addr Edit/Del Reply

    ;; 그거 굳이 노가다 안뛰어도 되네;
    S가 어떤 값이라 해도 최소의 N을 찾을 수 있으면 만족하는거라 -_-;

2008.09.20 01:00 Solutions/Dlbo's Solution


으흠.

용호군 코드와 많이 닮았죠?

다음 주 풀 문제는 미리 예고하지요.

Maximum sum이라고...

일부러 안 한 건데....

용호군이 이런 무서운걸 해버려서....

용호군 코드와 제 코드에 대해 설명하지요.

일단 원래 내준 식은 i^2 + 100000i + j^2 - 100000j + ij 이지요?

일단 최소와 최대를 -100억, +100억으로 잡고 시작해 봅시다.

이 기존 식에 x라는 변수를 하나 추가하여,

i^2 + 100000i + j^2 - 100000j + ij - x라는 식을 만듭니다.

이 후, i에 대해 판별식을 만들어 det에 저장해 두었지요.

이차방정식의 판별식. 아시죠 다들?

이를 이용해 x값에 따라 i는 고정하고, j값을 1부터 5만까지 반복시켜

x값에 따라 유효한지 아닌지를 체크합니다.

이 때, cal_1과 cal_2는 딱 det값만큼 차이납니다.

j의 증가에 따라 둘 사이의 차이는 계속 변화합니다.

이 차이가 N을 넘을 때는 강제로 N으로 줄여서 sum에 지속적으로 누적시킵니다.

이걸 N번 반복하고 나서, 이 누적된 sum이 M보다 작거나 같다면 이 x는 유효하며,

아직 최소값보다는 작다는 의미입니다. 이에 따라 min을 x + 1로 설정합니다.

만약 sum이 M보다 크다면 x가 무효하다는 것이겠지요?

무효하다는 의미는 곧 최대값이라 봐도 무방하단 의미겠지요.

이를 이용해 계속 min과 max로 하한, 상한을 점차적으로 줄여나가는 방식을 택합니다.

보시면 내부 for문중 N번 돌때 sum <= M인지도 체크하는데,

이때는 이미 sum이 M보다 커진다면 더이상 x의 유효성을 검사할 필요가 없으니 바로 나오는 거지요.

이리하여 서로 상한과 하한이 크로스되면 이때의 min값이 바로 최소값이 되는거지요.

x가 0부터 시작해(-100억과 100억의 중간값) 판별식의 유효성 검사를 통해 이진탐색법처럼

가능한 범위를 점차적으로 좁혀나가는 겁니다.

아참, 유효성 검사란... x를 중심으로 잡았을 때, M번째로 작은 수가 x보다 작은 쪽에 포진해 있어야

유효함을 이용한 체크를 하는겁니다. cal_1과 cal_2는 순수하게 유효성 체크만을 위해 연산하는 변수이죠.

아, 그리고 dizies님께는 죄송합니다만....;;

PKU의 GCC는 비주얼 스튜디오에서 사용하는 dll과 같은 ms계열을 쓰기 때문에 __int64를 써도 전혀 문제가

되지 않는다는군요 -_-;

double형이나 long long형은 모두 오버플로우로 인해 정확하지 못한 연산값이 나와 WA가 나옵니다.

long long형도 처리만 잘 해 주면 정확한 답을 얻을 수 있을것 같습니다.






P.S.

다음주 진짜 Maximum sum 해도 될까요?-_-?

'Solutions > Dlbo's Solution' 카테고리의 다른 글

PKU 2649. Factovisors. TLE  (4) 2008.10.02
PKU 1844. Sum. AC get!~  (1) 2008.09.22
PKU 3685. Matrix. AC get!  (5) 2008.09.20
PKU 2017, Speed Limit. AC get!  (0) 2008.09.11
PKU 2027. No Brainer. AC get~-_- - 101Byte  (5) 2008.09.11
PKU 2027. No Brainer. AC get!~ 91Byte.  (4) 2008.09.11
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.20 01:11  Addr Edit/Del Reply

    Maximum sum 은 의외로 쉽게 풀릴지도 모르지요. -_-a

    그러고 보니 그거 풀게되면 또 행렬이로군? -_-;

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.20 01:26  Addr Edit/Del Reply

    하지마

  3. Favicon of http://dizies.tistory.com BlogIcon dizies 2008.09.20 12:37  Addr Edit/Del Reply

    Maximum sum은 PKU2479 인가요 아니면 UVa108인가요? UVa108 Maxmum sum 이라면 풀었는데..
    PKU2479에는 흐미 어려운 수학식이 써있군염

  4. UVa 108입니다. TL의 대명사이지요. -_-;

    • Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.20 13:57  Addr Edit/Del

      아, 두개가 다른 문제였군?

      근데 문제 읽어보니 PKU쪽이 좀 더 어려운듯 -_-;

2008.09.12 16:15 Solutions/Fanta's Solution
Run ID User Problem Result Memory Time Language Code Length Submit Time
4060072 jht009 2017 Accepted 204K 0MS C 297B 2008-09-12 15:11:15

우후훗

'Solutions > Fanta's Solution' 카테고리의 다른 글

PKU 2649. Factovisors. AC 소인수분해  (2) 2008.10.07
PKU 2649. Factovisors. AC  (7) 2008.10.06
PKU 2649. Factovisors. TLE  (1) 2008.10.05
PKU 1844, Sum. AC  (1) 2008.09.23
PKU 2017, Speed Limit. AC  (3) 2008.09.12
PKU 2027. No Brainer. AC 94B  (1) 2008.09.11
posted by 지환태
TAG C, pku

댓글을 달아 주세요

  1. 오홋. 배열로 처리하셨네요? ㅁ_ㅁ?

    • Favicon of http://zfanta.com BlogIcon  환타 2008.09.13 23:38  Addr Edit/Del

      ㅎㅎ 입력,출력에 대한 설명이 부족한 것 같아요 ㅜㅜ
      PKU랑 UVa가 아직은 낯설기도 하구요 ㅎㅎ

  2. PKU가 입력 설명을 제대로 해놓지도 않고 마음대로 하는 경향이 있긴 하지요... UVa는 좀 깔끔한 편이지만.

2008.09.11 21:44 Solutions/Dlbo's Solution


이번 문제도 좀 쉽나...

'Solutions > Dlbo's Solution' 카테고리의 다른 글

PKU 1844. Sum. AC get!~  (1) 2008.09.22
PKU 3685. Matrix. AC get!  (5) 2008.09.20
PKU 2017, Speed Limit. AC get!  (0) 2008.09.11
PKU 2027. No Brainer. AC get~-_- - 101Byte  (5) 2008.09.11
PKU 2027. No Brainer. AC get!~ 91Byte.  (4) 2008.09.11
PKU 2027. No Brainer. AC get!  (2) 2008.09.10
posted by Lonewolf dlbo

댓글을 달아 주세요

2008.09.11 20:02 Solutions/Dlbo's Solution
사용자 삽입 이미지

곽군.

101B네.

굳이 함수화 안해도 되 -_-a
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.11 20:38  Addr Edit/Del Reply

    오 굿

    근데 제출할 때 나오는 것 중에 GCC(G++)와 C(C++)의 차이가 뭔가?

  2. GCC는 GNU 계열의 C 컴파일러로 컴파일 하겠다는 의미. G++ 또한 GNU 계열 C++로 한다는거지. C(C++)은 그냥 ANSI인데 GNU의 경우 코드 추가단축이 가능하지.

  3. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.12 10:44  Addr Edit/Del Reply

    아, 이거 define으로 바꾸면 안돼

    함수 s랑 리턴값 달라 -_-;

  4. 그래서 돌리는 방식을 바꿨잖나 -_-a

2008.09.11 16:51 Solutions/Dlbo's Solution


낄낄낄.
사용자 삽입 이미지

알고리즘 차원의 옵티마이즈도 진행중입니다.

scanf대신 gets와 main재귀 고려중.
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. 우왕 ㅋ 굳 ㅋ 가운데에도 증감식을 쓸 수 있었네요 ㅎㅎ

  2. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.12 05:05  Addr Edit/Del Reply

    도대체 뭐 어쩌다 숏코딩 경쟁이 붙었지? -_-;;;

  3. 저는 91B가 한계인 것 같아요 ㅇㅅㅇa;;;;
    라이브러리함수에 쓸 만한 걸 못찾겠어요 ㅋㅋ

2008.09.10 16:54 (임시휴재) Fanta's Post

메모리를 아끼기 위해선 배열을 동적으로 생성해야합니다.
뭐 다 아시겠지만

1차원배열 동적할당


malloc함수를 사용하기 위해선 stdlib헤더파일을 포함시켜야합니다.
동적할당할 원소의 개수(n)을 입력받고 sizeof(int) 곱하기 n만큼 메모리공간을 확보하고 그 주소를 arr포인터에 넘겨줍니다.


2차원배열 동적 할당

일단 줄(y)의 개수만큼 할당하고 각각 줄마다 칸(x)의 개수만큼의 원소를 할당합니다.

'(임시휴재) Fanta's Post' 카테고리의 다른 글

구글입사문제 풀기  (5) 2008.10.19
환형 링크드리스트  (3) 2008.10.08
정보올림피아드 모험가  (5) 2008.09.25
재귀함수랑 친해지기 : 파스칼의 삼각형  (1) 2008.09.17
동적 배열할당  (2) 2008.09.10
stl vector 사용  (4) 2008.09.03
posted by 지환태

댓글을 달아 주세요

  1. 중학교때 프로그래밍 처음 공부할 때가 생각나네요 ㅁ_ㅁa 환타님은 아직 젊으셔서 좋겠어요~ ㅁ_ㅁ!

2008.09.04 01:24 Solving process


Mr.K의 솔루션입니다.

위 부분에서 첫번째 문제...

문제에는 "EOF까지 입력받아라~"라고 되어있습니다.

근데 이 처리가 없지요 -_-a;;

이 처리는 생각보다 단순합니다.



위와 같습니다.

scanf는 EOF를 만나면 데이터를 변수에 넣지 않고, EOF를 리턴합지요.

이 외의 경우 scanf는 읽어들이는데 성공한 변수의 갯수를 리턴합니다.

while문의 조건에 scanf가 EOF를 만나느냐 아니느냐를 가지고 처리하게 해 버리고

내부 처리 루틴을 이 안에 쑤셔넣음으로써 해결되지요.

UVa나 PKU에서 EOF를 만날때까지 입력받을때 항상 쓰이는 방법입니다.

일반적으로 UVa나 PKU는 입력이 남았는데도 프로그램이 종료될 경우

TLE(Time Limit Exceed)나 WA(Wrong Answer)중 자기 마음대로 나오는 경향이 있습니다.

UVa의 경우는 WA만 나오더군요.

-_-;

이후 45~ 53줄.

gets를 이용해 입력을 받고 있습니다.

이 경우 문제점이.....

자. 아래 입력 예시를 보세요.

3 (3()
())
4 (2(2()())
())

.....

첫 문장만 처리해야 하는데...

4 (2(2()()) 까지 gets가 먹어버립니다.

-_-;

로직상 문제 없지 않냐구요?

.....

문제 있어요 -_-;;

gets는 버퍼에 글을 쓴 후, 버퍼 내용을 지우지 않고 변수에 데이터를 넣고 끝냅니다.

고로.... 입력 버퍼와 변수에 저장할 버퍼 사이에서 gets 한번 더 호출시

'\0'의 위치가 엉킨다거나, 하는 문제가 발생합니다.

-_-;

한두번의 입력은 버텨내겠지만, 이후에는 RE(Runtime Error)나 WA(Wrong Answer)를

유도할 수 있습니다.

이 떄문에 제가 getchar로 하나하나 받아다 처리했다지요 -_-;;

제 경우는 scanf의 특성을 활용했습니다.

EOF를 만날 경우 EOF나 -1을 리턴하는것 외에도,

scanf("%d", &a);시 입력받은 부분이 숫자로 시작하지 않는다면 scanf는 1개중 1개를 읽는데 실패했으니

1 - 1 = 0, 즉, 0을 리턴합니다.

이리하여 제 경우는 처음 비교대상은 scanf로 받고, 이후 getchar로 (를 받을떄까지 달린 후, 바로 scanf

를 이용해 빈 노드인지 아닌지를 판별하고 넘어가는 방식을 썼습니다.

빈 노드가 아니라면 scanf가 1을 리턴함으로써 참이 될 테고, 이 경우 내부 노드를 추가 확인하는 작업,

빈 노드라면 scanf가 0을 리턴함으로써 거짓이 되니, 다시 한번 (를 찾아 getchar의 여행을 떠나는거지요.

-_-;;

이후 곽군 코드의 문제점.

스택에다가 아예 우르르 쌓아버린후 연산하는데...

TL 걸리기 딱 좋답니다.

WA 풀린다면 아마 TL이 또 한번 가로막을꺼에요.

-_-!;;;;

용호군은 현재 솔루션이 있으나, 다시 생각해 풀어 올린다 합니다.

용호군의 솔루션도 저와 비슷한데.... 전북대 ALPS의 솔루션과 매우 흡사합니다.

용호군이나 저나 getchar를 이용해 한글자씩 받으며 입력받음과 동시에 연산을 했습니다.

이리하여 만약 yes가 된다면, 이후에는 종료될때까지 입력만 받도록 처리되었지요.

특히 Mr.K의 솔루션에서는 구조체를 이용해 처리를 했는데,

구조체의 배열 크기를 300으로 잡았답지요.

gets를 썼다는 부분과 문자열로 처리했다는 부분, 노드 갯수를 300이라는 적은 숫자로 잡은 부분에서

큰 문제가 발생합니다.

문자열로 처리함으로써 만약 한 줄에 256자가 넘게 입력되거나, 한 입력문이 256자가 넘으면

바로 RE입죠.

-_-;

동시에, 노드 갯수(Mr.K는 카드)가 300개를 넘는 경우에도 RE가 발생합니다.

물론 저런 극악의 경우는 드물겠지만 말입니다. -_-;

이 부분에 대한 처리를 하고 나면 코드가 상당히 짧아짐과 동시에 안정성을 가질겁니다.
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.04 01:43  Addr Edit/Del Reply

    저같은 경우는 어떤 수를 써도 string으로 받는 건 불가능하더군요. -_-;

    제가 동원할 수 있는 모든 방법을 써 봤지만, 결국 실패했습니다.
    한 문자씩 끊어서 비교. 검사해 가는 수 밖에 없겠더라구요 -_-

    그리고 ... dlbo군의 지적대로, 구조체 배열로 스택을 구현하기 보단 차라리 스택을 처리할 수 있는
    루틴을 따로 함수로 작성해서 코딩하는 것이 훨씬 나은 방법이라 생각됩니다.

    물론, 꽤 아슬아슬하겠지만 말이죠 -_-;;

    제 저번 솔루션이 그런 식이었습니다만... 전북대학교 동아리 ALPS의 솔루션과 90% -_-;; 흡사하기 때문에...
    여기에 올리기엔 무리가 있습니다. - 깜짝 놀랬어요 ㄱ- -

    다른 방법을 강구해서 어떻게든 풀어보도록 하죠.

  2. Favicon of http://klone.tistory.com BlogIcon Mr.K 2008.09.04 21:35  Addr Edit/Del Reply

    EOF 처리방법 알려준대로 해서 끝냄//

    그리고 gets가 4 (2(2()())까지 받아들인다고 말했는데 저 소스가 그렇게 짜여있진 않네//
    3 (3()())을 입력하고 엔터치는 순간 while문에서 튕겨나가지;

    SIZE 300이 불만이면 그건 그냥 늘여놓으면 되는 일.

2008.09.02 18:38 Solutions/Dlbo's Solution


ANSI C 기준 컴파일러에서 동작하는 코드입니다.

VS의 경우는 6.0에서만 가동됩니다.

스타팅의 '('를 기준으로 트리 노드 레벨을 설정해 최초 시작시 1, 최후 노드 레벨이 0이 되면 탈출하도록

하면서 처리했습니다.

노드레벨이 증가할때(루트에서 멀어질 때) 합에 노드의 값을 더하고, 노드레벨이 감소할 때(루트에 가까워질때)

합에서 기존 노드의 값을 빼는 방식으로 진행하면서, 양쪽 자식노드가 모두 없을 때

(()()꼴일때)의 합을 먼저 입력받은 비교대상과 비교해 맞는지 아닌지 여부를 처리하게 했습니다.

여러 줄에 걸쳐 받아야 하는데다가, 한 줄에 괄호하나 딸랑 있는 경우도 존재하기 때문에

한 글자씩 받아 처리했으며(getchar로 돌렸지요....), scanf가 숫자가 아닌 값을 받았을때 false를 반환한다는

점을 이용해 빈 트리노드인지 아닌지를 판별했습니다.

UVa 기준 상위 랭크 43위 기록된 코드입니다.

사용자 삽입 이미지
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.03 02:40  Addr Edit/Del Reply

    크흠. String으로 받아보려고 C++에서 문자열 클래스의 >> 연산자까지 재정의해 가면서 생 쇼를 해봤는데 -_-;

    방법을 못찾겠더군. 문제에서 트리를 1줄 이상으로 받는 경우의 처리가 모호해 져서.

    익히 알다시피 RE먹기 쉽지 -_-;;;;;;;

    역시나 한 문자씩 받고 검사해 가면서 처리하는 수 밖에 없을듯. C의 gets역시 어불성설이고.

    우리처럼 '(' 문자 뒤에 정수가 오면 tree level 증가, 만약 ')' 가 오면 tree level 감소시켜서 재귀구조로
    구현하는게 가장 간단하고 직관적인 솔루션이고...

    현재 다른 방법을 찾고 있는중 -_-;;;;

2008.08.29 21:44 (비정기) Dlbo's Post


하암...

비주얼 스튜디오 6.0,

혹은 gcc나 ANSI C 표준을 따르는 컴파일러에서 작동하는 코드입니다.

(비주얼 스튜디오 닷넷은 ANSI C 표준이 아닙니다.)

아 참,

저게 뭐하는 거냐구요?

.......

두 개의 한자리 양의 정수를 입력받아 합을 출력하는 프로그램 입니다.

.......

직장 상사한테 뺨때기 한대 맞기 딱 좋죠?

것도 합이 두 자리 수가 되면 답이 안나와요.

-_-;

두 자리 수가 될 경우 나오게 하는 방법이 있긴 하지요.

printf를 활용 하되, 좀 색다른 방법을 써야 합니다.

....

저 코드가 어떻게 돌아가느냐구요?

.......

C언어 표준을 따르니 돌아가지요 뭐 -_-;

#include <stdio.h>를 빼도 gets와 putchar는 built-in 함수라 해서 컴파일러 자체에 내장되어 있습니다.

컴파일 하는 순간 해당 헤더가 없다면, 컴파일러가 직접 구현해서 포함시켜 주는거지요.

참... 당황스럽지요?

-_-;

main 앞에 있던 int나 void도 사라졌습니다.

main() 안에는 int형 인자가 최대 2개까지 들어갈 수 있다고 알려졌습니다만...

무슨 함수라도 부른 것 처럼 변수 이름만 들어가 있습니다.

동시에 gets에서 이 데이터형도 알 수 없는 변수에 입력받은 문자열을 집어넣고 있구요.

putchar에서 또한 알수없는 이상한 짓을 합니다.

근데... 프로그램은 잘 동작해요.

아까 말씀드린 것처럼 합의 결과도 1자리수 일 때만.

-_-)_b

사실 main 앞에는 int가 생략되어 있고,

괄호 내부의 n 또한 int n인데 int가 생략되어 있는겁니다.

ANSI C 표준이라면, 데이터형을 생략하면 자동으로 int형이 되지요.

그건 둘째치고...

근데 왜 int형에다가 문자열을 집어넣느냐...



입력형식을 봅시다

한자리 숫자 두개에요.

1과 2를 넣는다면

'1 2\n'

.....

빈칸까지 합해 정확히 4바이트 맞지요?

....

문제 없습니다.

-_-)_b

putchar 에서는 첫번째와 세번째 숫자만 골라내어 처리하도록 나머지연산까지 써서 처리합니다.

이로써 동작하는 거지요.

-_-)_b

이런 엽기적으로 코드를 단축시켜 버리는 기법을 숏 코딩이라 합니다.

대표적인 사람으로 Short Coding이라는 책의 저자인 일본인 Ozy 씨가 있지요.(필명 -_-)

심심하다면 자신의 코드를 한번 극단적으로 줄여보세요. ㅋㅋ


Short coding의 원리들.

if문 -> &&연산으로 대체합니다. &&연산은 앞의 식이 성립할때만 뒤의 식을 실행합니다.
      -> 될수있도록 사용을 자제합니다. 함수 내에서는 물론이고, for문의 조건판별부분에도 쓸 수 있습니다.
scanf문 -> EOF가 들어오면 -1을 리턴합니다. 예외처리시 if(scanf(어쩌구저쩌구) == EOF) break;
                이렇게 처리하기 보단... 그냥 입력 루프에 while(~scanf(어쩌구저쩌구))로 처리하시면 한방!

.....

숏코딩 한번 도전해보세요~

건투를 빕니다. -_-)_b
posted by Lonewolf dlbo

댓글을 달아 주세요

  1. Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.08.29 22:02  Addr Edit/Del Reply

    하앍. 책보고 공부할때마다 느끼지만 진짜 저건 만든 놈이 대단해-_-;;;;

    컴파일러의 구조 이해 + ANSI C에 대한 확실한 지식이 없으면 나올 수가 없으니 ㄱ-

  2. Favicon of http://dizies2.tistory.com BlogIcon dizies 2008.09.12 15:27  Addr Edit/Del Reply

    저도 그 책 있는데.. 뭐랄까.. 너무 어려워요..ㅋㅋ 그분께 PKU쪽지로 몇마디 주고받은적이 있는데 Ozy님 자신도 숏코딩이 그리 효율적인건 아니라고 하더군요.. 그냥 재미를 위해서 한다고..ㅋㅋ

    • Favicon of http://studyinglw.tistory.com BlogIcon Reuent 2008.09.12 17:17  Addr Edit/Del

      -_-a

      재밌긴 하죠. 말 그대로 똘끼가 가득찬 코딩이라고 할까.

      하지만 응용하긴 쉽지 않더군요 -_-;

2008.08.27 23:23 (비정기) Dlbo's Post


이전 포스트보다 좀 더 간단한 예제.

Hello World! 혹은 Hello C! 라고 불리우는 예제입니다.

이번에 새로 나온건 '\n'.

그리고 전에는 printf() 내부에 "" 이후 콤마로 구분해 출력 형식에 집어넣을 변수가 있었는데

이번엔 사라졌지요?

printf()함수의 특성은 ()안에 인자(함수 구동시 사용하는 인풋)의 갯수가 무한대라는 것입니다.

최소 1개(""로 쌓인 출력할 문장), 최대 무한대.

뭐... 사실 최대 갯수가 정해져 있긴 하지만, 그걸 다 넣을 정도라면 차라리 여러 줄로 나눠 쓰는게

보기에도 편하고 쓰기에도 편하답니다.

printf() 내부에 이번엔 "Hello World!\n"만 들어갔는데요.

이로 인해 Hello World! 라는 문자열만 출력된다는 것을 알 수 있습니다.

아까 언급했던 '\n'는 "개행문자" 라는 것인데,

한 줄 다음으로 넘기는 것이지요.

고로



라고 기술한다면,

Hello
World!

라고 출력되는걸 보실 수 있습니다.

반면, scanf()는 ""만 들어있으면 안됩니다.

뭐... 그렇게 써도 상관은 없지만...

입력을 받기 위한 것인데, 그냥 저렇게 해버리면

아무것도 하지 않겠지요?

그럼... 내일 다시 뵙지요. -_-)_b
posted by Lonewolf dlbo

댓글을 달아 주세요

prev 1 next