성태의 닷넷 이야기
홈 주인
모아 놓은 자료
프로그래밍
질문/답변
사용자 관리
사용자
메뉴
아티클
외부 아티클
유용한 코드
온라인 기능
MathJax 입력기
최근 덧글
[정성태] 아쉽게도, 커뮤니티는 아니고 개인 블로그입니다. ^^
[정성태] 질문이 잘 이해가 안 됩니다. 우선, 해당 소스코드에서 ILis...
[양승조
] var대신 dinamic으로 선언해서 해결은 했습니다. 맞는 해...
[양승조
] 또 막혔습니다. ㅠㅠ var list = props[i].Ge...
[양승조
] 아. 감사합니다. 어제는 안됐던것 같은데....정신을 차려야겠네...
[정성태] "props[i].GetValue(props[i])" 코드에서 ...
[정성태] 저렇게 조각 코드 말고, 실제로 재현이 되는 예제 프로젝트를 압...
[정성태] Modules 창(Ctrl+Shift+U)을 띄워서, 해당 Op...
[정성태] 만드실 수 있습니다. 단지, Unity 엔진 내의 스크립트와 W...
[공진영] 안녕하세요 좋은글 감사합니다. 현재 제가 wpf로 관제 모...
글쓰기
제목
이름
암호
전자우편
HTML
홈페이지
유형
제니퍼 .NET
닷넷
COM 개체 관련
스크립트
VC++
VS.NET IDE
Windows
Team Foundation Server
디버깅 기술
오류 유형
개발 환경 구성
웹
기타
Linux
Java
DDK
Math
Phone
Graphics
사물인터넷
부모글 보이기/감추기
내용
<div style='display: inline'> <h1 style='font-family: Malgun Gothic, Consolas; font-size: 20pt; color: #006699; text-align: center; font-weight: bold'>The 3n + 1 problem의 C#/Java 버전 풀이</h1> <p> 두뇌를 말랑말랑하게 유지하려고 "알고리즘 트레이닝 북"을 구매했습니다. ^^<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > Programming Challenges - 알고리즘 트레이닝 북 ; <a target='tab' href='http://www.yes24.com/24/Goods/1396784?Acode=101'>http://www.yes24.com/24/Goods/1396784?Acode=101</a> </pre> <br /> 오일러도 88번까지 풀다가 문제가 더 출제되지 않아서 그만두고 있었는데,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 일단... "Project Euler @kr" 88번까지 완료! ^^ ; <a target='tab' href='http://www.sysnet.pe.kr/0/0/427'>http://www.sysnet.pe.kr/0/0/427</a> </pre> <br /> 오랜만에 방문해 보니 어느새 113번 문제까지 출제가 되었네요. ^^ 그래도, 책을 구매했으므로 이것 먼저 하고 오일러를 손대야 할 것 같습니다. ^^ <br /> <br /> 우선 첫 번재 문제!<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > The 3n + 1 problem ; <a target='tab' href='http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html'>http://www.programming-challenges.com/pg.php?page=downloadproblem&probid=110101&format=html</a> </pre> <br /> C# 언어로 만들어 봤는데,<br /> <br /> <pre style='height: 400px; margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > using System; using System.Collections.Generic; namespace ConsoleApplication1 { class Program { Dictionary<long, int> _cycles = new Dictionary<long, int>(); List<long> _steps = new List<long>(); static void Main(string[] args) { Program my = new Program(); my.Run(); } private void Run() { _cycles.Add(1, 1); while (true) { string txt = Console.ReadLine(); if (string.IsNullOrEmpty(txt) == true) { break; } string[] numbers = txt.Split(' '); long start = UInt32.Parse(numbers[0]); long end = UInt32.Parse(numbers[1]); if (start > end) { long temp = start; start = end; end = temp; } long ticks = Environment.TickCount; int maxLength = GetMaxCycle(start, end); long diff = Environment.TickCount - ticks; Console.WriteLine(start + " " + end + " " + maxLength + ", elapsed: " + diff); } } private int GetMaxCycle(long start, long end) { int maxLength = 0; for (long i = start; i <= end; i++) { int cycleLength = GetCycleLength(i); if (maxLength < cycleLength) { maxLength = cycleLength; } } return maxLength; } private int GetCycleLength(long i) { _steps.Clear(); while (_cycles.ContainsKey(i) != true) { _steps.Add(i); if (i % 2 == 0) { i /= 2; } else { i = i * 3 + 1; } } int cycleLength = _cycles[i] + _steps.Count; int result = cycleLength; if (_steps.Count > 0) { foreach (long s in _steps) { _cycles[s] = cycleLength--; } } return result; } } } </pre> <br /> 아쉽게도 programming-challenges 공식 사이트에서는 C, C++, Java, Pascal 언어만 지원하기 때문에 자바로도 만들어 봤습니다.<br /> <br /> <pre style='height: 400px; margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > import java.io.*; import java.util.*; class Main { static String ReadLn(int maxLength) { byte line[] = new byte[maxLength]; int length = 0; int input = -1; try { while (length < maxLength) { input = System.in.read(); if ((input < 0) || (input == '\n')) break; line[length++] += input; } if ((input < 0) && (length == 0)) return null; return new String(line, 0, length); } catch (IOException e) { return null; } } public static void main(String args[]) { Main myWork = new Main(); myWork.run(); } HashMap<Long, Integer> _cycles = new HashMap<Long, Integer>(); ArrayList<Long> _steps = new ArrayList<Long>(); public void run() { String input; StringTokenizer idata; _cycles.put(1L, 1); while ((input = Main.ReadLn(255)) != null) { idata = new StringTokenizer(input); long start = Long.parseLong(idata.nextToken()); long end = Long.parseLong(idata.nextToken()); if (start > end) { long temp = start; start = end; end = temp; } long ticks = System.currentTimeMillis(); int maxLength = GetMaxCycle(start, end); long diff = System.currentTimeMillis() - ticks; System.out.println(start + " " + end + " " + maxLength + ", elapsed: " + diff); } } public int GetMaxCycle(long start, long end) { int maxLength = 0; for (long i = start; i <= end; i++) { int cycleLength = GetCycleLength(i); if (maxLength < cycleLength) { maxLength = cycleLength; } } return maxLength; } private int GetCycleLength(long i) { _steps.clear(); while (_cycles.containsKey(i) != true) { _steps.add(i); if (i % 2 == 0) { i /= 2; } else { i = i * 3 + 1; } } int cycleLength = _cycles.get(i) + _steps.size(); int result = cycleLength; if (_steps.size() > 0) { for (long s : _steps) { _cycles.put(s, cycleLength--); } } return result; } } </pre> <br /> 입력 파일인 data.txt 파일을 다음과 같이 구성해서,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > 1 10 100 200 201 210 900 1000 1 1000000 </pre> <br /> C#, Java 버전의 코드를 실행하면 다음과 같은 실행 결과가 나옵니다.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > D:>ConsoleApplication1.exe < i.txt 1 10 20, elapsed: 16 100 200 125, elapsed: 0 201 210 89, elapsed: 0 900 1000 174, elapsed: 0 1 1000000 525, elapsed: 406 D:>java -classpath . Main < i.txt 1 10 20, elapsed: 0 100 200 125, elapsed: 1 201 210 89, elapsed: 0 900 1000 174, elapsed: 2 1 1000000 525, elapsed: 1186 </pre> <br /> 그나저나... 자바 버전으로 만든 소스코드에서 elapsed 측정을 제외시켜 다음과 같이 출력이 나오도록 변경한 다음,<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > D:>java -classpath . Main < i.txt 1 10 20 100 200 125 201 210 89 900 1000 174 1 1000000 525 </pre> <br /> "<a target='tab' href='http://www.programming-challenges.com'>http://www.programming-challenges.com</a>" 웹 사이트에 제출하면 답이 틀렸다(Wrong answer)고 나옵니다. 웹을 검색해서 다른 사람들의 답과 비교해봐도 답이 틀린 것은 모르겠는데... 암튼 답이 틀렸다고 나옵니다. 혹시 어떤 기준으로 저런 판정이 났는지 아시는 분은 덧글 부탁드립니다. ^^<br /> <br /> 어쨌든 재미있군요. 가끔씩 심심할 때마다 풀어봐야겠습니다. ^^<br /> </p><br /> 참고로, C++ 버전도 추가.<br /> <br /> <pre style='margin: 10px 0px 10px 10px; padding: 10px 0px 10px 10px; background-color: #fbedbb; overflow: auto; font-family: Consolas, Verdana;' > #include <iostream> #include <string> #include <vector> #include <cstring> #include <algorithm> #include <map> using namespace std; class Ch1_3n1 { int _start; int _end; map<int, int> _cache; public: Ch1_3n1(int start, int end) { _start = start; _end = end; if (_start > _end) { swap(_start, _end); } } int calc() { int result = 0; for (int i = _start; i <= _end; i++) { result = max(result, calc3n1(i, 1)); } return result; } int calc3n1(int n, int depth) { map<int, int>::iterator it = _cache.find(n); if (it != _cache.end()) { return it->second + depth; } if (n == 1) { return depth; } int totalDepth = 0; if ((n % 2) == 0) { totalDepth = calc3n1(n / 2, depth + 1); } else { totalDepth = calc3n1(n * 3 + 1, depth + 1); } _cache.insert(pair<int, int>(n, totalDepth - depth)); return totalDepth; } }; // https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=29&page=show_problem&problem=36 int main() { while (true) { int start = -1; int end = -1; cin >> start; cin >> end; if (start == -1 && end == -1) { break; } Ch1_3n1 c(start, end); cout << start << " " << end << " " << c.calc() << endl; } return 0; } </pre> <br /><hr /><span style='color: Maroon'>[이 글에 대해서 여러분들과 의견을 공유하고 싶습니다. 틀리거나 미흡한 부분 또는 의문 사항이 있으시면 언제든 댓글 남겨주십시오.]</span> </div>
첨부파일
스팸 방지용 인증 번호
1823
(왼쪽의 숫자를 입력해야 합니다.)