입금후 변신하는 헐리우드 코딩 스타

@RequestMapping(value = "config/properties/test/{idx}") public String propertiesTest(@PathVariable int idx, Model model) { ... } 위와 같이 int 형태로 index를 받아서 숫자 형태로 매핑 시켜도 되고, @RequestMapping(value = {"config/properties/test/1", "config/properties/test/2", "config/properties/test/3"}) public String propertiesTest(Model model) { ... } 이 처럼 그냥 전체를 다 써 줘도 된다. 분기 처리를 해 주고 싶으면 String requestUrl = (String)request.getAttribute(HandlerMapping.PATH_WITHIN_HANDLER_MAPPING_ATTRIBUTE); 로 값을 받아와서 분기 처리 해 주면 된다고 한다. 같은 view 페이지에 내용만 다르게 해서 뿌려줘야 할 경우가 생겨서 사용해 보았다.

/src/main/resources/application.properties 를 생성해도  정상적으로 인식 되지 않는 일이 있어서 인식 하도록 추가 해보았다. 1) servlet-context.xml <context:property-placeholder location="classpath:application.properties" />  추가 2) Configuration 어노테이션 사용하는 클래스 추가 import org.springframework.context.EnvironmentAware; import org.springframework.context.annotation.Configuration; import org.springframework.context.annotation.PropertySource; import org.springframework.core.env.Environment; @Configuration @PropertySource(value = { "classpath:application.properties" }, ignoreResourceNotFound = false) public class ConfigEnvironment implements EnvironmentAware { private static Environment env; public static String getProperty(String key) { return env.getProperty(key); } @Override public void setEnvironment(Environment environment) {   this.env = environment; } } : setEnvironment 는 EnvironmentAware를 상속받아야 해서 추가했다. 이 것을 해야 Bean이 생성되기 전에 먼저 호출이 되어서 Properties 가져올 시에 null이 안 난다. 3) 컨트롤러 등에서

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://free-video-to-jpg-converter.kr.uptodown.com/windows 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ * https://joker1209.tistory.com/11 도 참고했다. View -> Large 로 크게 본 뒤, Edit -> Syncronize Crops 로 일괄 동일하게 적용하는 방식을 사

Window -> Preferences -> Team -> Git -> Configuration -> Add Entry Key : user.name Value : 이름 Key : user.email Value : 이메일 추가 후 커밋 할 수 있는 Git Staging에서 바뀐 것이 확인 가능하다. 설정 안 해 줄 경우 윈도우 기본 계정명, 계정명@컴퓨터명으로 들어간다.

https://github.com/settings/tokens 에서 token을 발행 한 뒤 eclipse나 sts 등에서 연동 시 아이디 / token을 입력하면 된다. 한번 발행한 토큰은 발행 시점 외에는 재확인이 불가능해서, 관리를 잘 해야 한다. 토큰을 잊으면 update나 삭제해서 재 발행한 뒤 사용하면 된다.

이클립스에서 제우스 원격 디버깅 하는 방법은 JEUSMain.xml에  <command-option> -Xms256m -Xmx512m -XX:MaxPermSize=128m -Dcom.dsjdf.config.file=/apphome/gpkisecureweb/conf/dsjdf.properties -Xdebug -Xnoagent -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=8000 </command-option> 을 추가한다. Eclipse -> Run -> Debug Configration -> Remote Java Application -> New Host : 원격 제우스의 IP 포트 : 8000 으로 입력하면 된다고 한다. 출처: https://expert0226.tistory.com/183

안드로이드 APK 파일을 디컴파일해서 dex2jar 와 같은 툴에다 넣으면 dex 압축형태를 jar 파일로 변환해준다. dex(실행파일)을 사람이 볼 수 있는 형태로 변환해줘야 사용 가능하다. https://sudeky.tistory.com/30 위변조 확인을 위해 dex 추출하는 얘기를 해서 찾아보았다. 출처: https://dwfox.tistory.com/43

QT는 QT Creator 때문에 확인 하고 있다. 이것은 GUI 라이브러리가 유명한가 보다. UI 개발 도구도 유명한가 보다. 근데 결론적으로는 C++ 개발용 종합 프레임워크인가 보다. QT Creator 가 통합 개발 환경인데, 이거를 비주얼 스튜디오랑 연동해서 사용할 수 있나 보다. C++ 개발 할일을 만들어서 써봐야겠음. 출처: https://namu.wiki/w/Qt(%ED%94%84%EB%A0%88%EC%9E%84%EC%9B%8C%ED%81%AC)

기드라는 미국 국가 안보국에서 만들어서 오픈 소스로 공개한 역 어셈블리 프레임워크라고 한다. IDA PRO에 대적할 수 있는 무료 프로젝트라고 한다. 자바 11 이상부터 지원하고, 파일 소스코드 추적도 할 수 있다. 맨날 Java Decompiler(커피잔) 만 썼는데 여러 가지 좋은 툴이 있었다! 툴도 잘 쓰는 것이 능력인 것 같다. 최신 툴을 찾아서 써봐야지. 출처: https://ndb796.tistory.com/323

IDA (Interactive DisAssembler) 상용 디스 어셈블러로, 주로 리버스 엔지니어링을 위한 디버거이다. 스크립팅 언어로 변환을 해 주는 기능이 있어서 많이 쓴다고 한다. 근데 가격이 600만원이라고 한다. 비싸고...다들 크랙판을 쓰는 것 같은 IDA... 좋아 보여서 써볼까 했는데 학생용 버전으로 공부만 해봐야겠다.

안드로이드 앱 배포 시 APK, AAB 라는 용어가 나온다. APK는 파일 확장자이고, AAB는 안드로이드 앱 번들의 줄임말이다. APK는 ABI(안드로이드 바이너리 인터페이스)를 여러 개 포함하여 용량이 크다. 따라서 APK 다운 시 시간이 많이 걸린다. 그래서 APK의 통 빌드 대신에 AAB를 통해서 경량화된 앱을 제공한다. 스토어에도 AAB 파일이 업로드되며, AAB 파일 기반으로 아키텍쳐, 화면 밀도, 언어에 최적화된 분할 APK를 생성한다. 따라서 최종적으로 앱 실행 필수 요소인 base APK를 비롯하여 분리 형태로 파일들이 생성된다. 이는 다양한 APK들이 사용자 기기 환경에 맞게 설치되어 하나의 앱을 구성하는 방식이다. Android App Bundle 은 앱의 모든 컴파일된 코드 및 리소스를 포함하며 APK 생성 및 서명을 Google Play에 맡기는 게시 형식입니다. Google Play는 App Bundle을 사용하여 각 기기 설정에 맞게 최적화된 APK를 생성하고 제공합니다. 따라서 앱을 실행하기 위해서는 특정 기기에 필요한 코드와 리소스만 다운로드하면 됩니다. 개발자는 더 이상 다양한 기기에 대한 지원을 최적화하기 위해 여러 개의 APK를 빌드, 서명 및 관리할 필요가 없으며, 사용자는 더 작고 최적화된 앱을 다운로드하게 됩니다 출처: https://real-dongsoo7.tistory.com/137 https://developer.android.com/guide/app-bundle?hl=ko

Mach-O (Mach Object file format) 마쵸가 아니라 마하 오 라고 읽는다. Mach는 카네기 멜론 대학에서 개발된 커널이라고 한다. Mach-O는 마이크로 커널의 가장 초기 예시로 언급되고는 한다. Apple의 XNU를 비롯하여 macOS, iOS, iPadOS, tvOS등을 Mach 기반으로 작업했다고 한다. 네이티브 실행 파일, 라이브러리, 객체 코드 형식에 이 Mach-O 형식을 다 적용했다고 한다. Mach-O는 특정한 포맷이 없고, 의미가 있는 데이터로 그룹화된 바이너리 바이트 스트림이라고 한다. 출처: https://en.wikipedia.org/wiki/Mach-O https://zeddios.tistory.com/908

ODM(Original Development Manufacturing) ODM은 주문자(Client, 고객) 가 제조사(업체)에게 특정한 제품의 생산을 위탁하면, 제조사가 이 제품의 설계, 디자인 등의 개발, 생산등을 모두 책임지고 주문자에게 납품하고, 주문업체는 이 제품을 유통, 판매하는 형태를 말한다. 주문자가 만들어준 설계도에 따라 단순하게 생산만하는 하청 생산 방식인 '주문자 상표 부착 생산(OEM (Original Equipment Manufacturing))과 달리 주문자는 컨셉만 전달하고, 제품의 설계, 디자인, 개발, 생산 등을 제조업체가 책임지게 된다. ODM은 주로 기술력을 보유한 제조업체에서 제품을 개발하면, 브랜드와 판매망을 보유한 유통업체에서 납품을 받아 유통과 판매에 집중한은 시스템으로 이루어진다. 따라서 ODM은 제품을 만드는 업체와 제품을 판매하는 업체의 전략적 제휴 관계라 보면 된다. IT 개발에서 ODM이 나와서, 궁금하여 검색 해 보았다. 출처: http://dmc21.co.kr/ODM%EC%9D%B4%EB%9E%80/write_form

IPA ( i OS A pp Store P ackage) iAP가 아니라 IPA인 이유는 모르겠다. .ipa 라는 확장자를 사용해서 iOS에서 사용하는 앱의 설치 파일을 생성한다. Xcode에서 앱을 만들면 .app 폴더가 생성되는데, 이 파일을 .zip 형식으로 압축해 확장자만 .ipa로 바꾸는 방식을 사용한다. 따라서 앱스토어에서 앱을 다운받으면 일단 .ipa 파일을 다운 받은 뒤, iOS에서 압축을 해제하는 과정을 거친 뒤, 실질적으로는 .app 폴더로 설치하게 된다고 한다. 출처 : 오랜만에 나무위키

application.getServerInfo(); * application 기본 객체는 ServletContext 클래스의 인스턴스로 웹 어플리케이션이 구동중인 웹 컨테이너에 대한 정보들을 얻을 수 있다.   출처: https://dololak.tistory.com/427

 JCE(Java Cryptography Extension) 강력한 암호화인 AES256 등을 사용 불가능 할 때 검색하여 JCE를 다운받아 사용한다. 기존에는 자바홈\jre\lib\security 폴더 안에 local_policy.jar, US_export_policy.jar 파일을 넣으면 동작했었다. 그런데 이제 자바 8 151 버전 이후부터는 자바홈\lib\security\policy 폴더 안의 limited 와 unlimited 폴더가 생기며 파일이 애초에 존재해서 다운 받지 않아도 된다. 이제 자바홈\lib\security\java.security 파일을 열어서 crypto.policy=unlimited 를 주석 해지해 주면 된다. 아니면 자바 소스 내에서 Security.setProperty("crypto.policy", "unlimited") 라고 지정하면 된다. 9부터는 그냥 활성화 되어 있다고 한다. 출처: https://java.elex.pe.kr/2017/11/jce-180151.html https://hongsii.github.io/2018/04/05/java-aes256-error/ https://bigenergy.tistory.com/entry/AES256-%EC%95%94%ED%98%B8%ED%99%94-%EB%B3%B5%ED%98%B8%ED%99%94-%EC%A3%BC%EC%9D%98%EC%82%AC%ED%95%AD-%EB%B0%8F-%EC%83%98%ED%94%8C-%EC%BD%94%EB%93%9C

슈가러쉬(Sugar Rush) : 사탕이나 쵸콜렛같은 달콤한 음식을 먹고 살짝 흥분이 되는 상태를 의미한다. 슈가 크래쉬(Sugar Crash) : 반대로 카페인이나 단 성분의 음식을 먹은 후 오는 극심한 피로 현상을 의미한다. 출처: https://ssadic.com/%EB%9C%BB/%EC%8A%88%EA%B0%80%EB%9F%AC%EC%89%AC/

내가 쓰려고 만드는 토이 프로젝트      제목 : 퇴근 시간 계산기      목적 : 퇴근 시간 계산 및 휴일까지 남은 날짜 제공      디자인 : 구글에서 발췌      URL : http://cat.dothome.co.kr/ (무료 호스팅)           제약 조건 : html 내에서 제공하는 기능만 사용 가능 (무료 호스팅의 한계)      개발 기간 : 짬 날 때마다 비정기적으로 수정

https://data.go.kr/index.do 에서 신청해서 사용 가능하다. https://www.data.go.kr/data/15012690/openapi.do 특일 신청 (공휴일 조회) HTML에만 단독으로 가져와서 사용할 때는 CORS 오류가 나므로, var request = new XMLHttpRequest(); request.open('GET', 'http://cors-anywhere.herokuapp.com/입력할URL'); request.responseType = 'json'; request.send(); request.onload = function() { dataValue= request.response; }; 위와 같이 프록시 서버를 사용해서 Access-Control-Allow-Origin 을 설정하였다. 그 후에는 가져온 값들 비교해서 오늘이 공휴일 일 때만 확인할 수 있도록 작업 할 예정이다. var todayDate = getTimeStamp(); for(var i = 0; i<dataValue.numOfRows;i++){      if(todayDate == dataValue.items.item[i].locdate){ alert(dataValue.items.item[i].dateName);      } } 토이 프로젝트로 구글 형태를 띄는 html 페이지 만들어 보는 중인데, 여기서 사용 예정이다. http://cat.dothome.co.kr/ 추신. var proxyURL = 'https://cors.bridged.cc/'; //herokuapp demo 서버 사용의 불편함으로 bridged.cc 로 전환 210618 //proxyURL = 'http://cors-anywhere.herokuapp.com/'; //proxyURL = 'https://robwu.nl/cors-anywhere.html/'; //proxyURL = &

cmd 에서 tree를 입력시에는 현재 해당하는 디렉토리 내의 정보가 출력 가능하다. 명령어 : tree 파일 형태로 저장하고 싶으면 > 를 사용해서 내보내면 된다. 명령어 : tree > 저장하고자 하는 이름.txt 옵션을 사용해서 저장하고 싶으면 /f /a를 사용하면 된다. /f 는 각 폴더에 있는 파일을 모두 표시하는 것이다 /a 는     │      └─2. 사이트 전달 내역     └─2. 상담 자료 이런식으로 그래픽 문자 형태로 출력하는 대신     |       \---2. 사이트 전달 내역     \---2. 상담 자료 이런 형식으로 텍스트 문자로 대치해서 출력해준다. 명령어 : tree /f /a > 저장하고자 하는 이름.txt  이렇게 출력 형태 변경, 저장, 조회가 가능하다. 출처 : https://ojhsky.tistory.com/entry/%ED%8C%8C%EC%9D%BC%ED%8A%B8%EB%A6%AC-%EC%83%9D%EC%84%B1%ED%95%98%EA%B8%B0-%ED%8F%B4%EB%8D%94-%EB%82%B4%EC%9A%A9-%ED%95%9C%EB%88%88%EC%97%90-%EB%B3%B4%EC%9E%90

http://www.myipaddress.com/show-my-ip-address/ 위 주소에서 본인 PC IP확인 후 https://whois.kisa.or.kr/ 여기서 IP 입력 후 검색하면 ISP 할당 된 것 확인 가능하다. 아니면 아래 사이트에서 속도 테스트, 회사 확인 가능하다. https://beta.speedtest.net/ 출처 : https://dvdprime.com/g2/bbs/board.php?bo_table=comm&wr_id=17193624

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

① 우선, Gmail의 아이디와 비밀번호를 확인해 줍니다. ② 그다음으로 아래 링크로 들어가셔서 Google 계정의 '보안 수준이 낮은 앱의 액세스' 설정을 허용해 줍니다. https://myaccount.google.com/lesssecureapps Google '보안 수준이 낮은 앱의 액세스' 설정.  ③ 마지막으로, 아래 링크에서 외부기기 등 다른 App 에서 로그인 할 경우에 추가 인증을 거치지 않도록 설정해 줍니다. https://accounts.google.com/b/0/DisplayUnlockCaptcha Google '내 Google 계정에 대한 액세스 허용' 설정.  이렇게 설정해 주고 나면 등록 완료 팝업이 출력되게 됩니다. 1년만에 사용 가능하게 되어서 저장 목적으로 스크랩 해 두었음. 출처 : https://amiandappi.tistory.com/1

dothome 무료 호스팅 이용 - XE (제로보드) 설치 후 FTP 프로그램으로 접속한다. /html/common/tpl/common_layout.html 테마는 삭제하거나 미사용하게 두고, common_layout.html 을 변경하면 html 페이지로 사용 가능하다. http://cat.dothome.co.kr/ 이런 식으로 퇴근 계산기 페이지로 샘플 제작해 보았음. * 공유해 본 결과 mobile 기기나 스마트 디바이스에서 안 보이는 것을 확인하였다. /html/common/tpl/common_layout.html /html/common/tpl/mobile_layout.html /html/common/tpl/default_layout.html 도 동시에 수정하였다. * 그리고 어짜피 저 기능만 쓸 것이라 일단 tpl 폴더를 모두 같은 것으로 교체하였다. 231002 : termius는 ssl을 지원 안 하는 것은 접속 불가. moba xterm으로만 사용하겠다. html은 직접 수정 시 utf-8로 수정되지 않으므로 utf-8로 변환한 동일 파일을 올리는 편이 낫다.

Knapsack Problem Knapsack - n개의 아이템과 배낭 - 각각의 아이템은 무게 wi와 가격 vi를 가짐 - 배낭의 용량 W - 목적: 배낭의 용량을 초과하지 않으면서 가격이 최대가 되는 부분집합 - 예:      {1,2,5}는 가격의 합이 35      {3,4}는 가격의 합이 40      {3,5}는 46이지만 배낭의 용량을 초과함 i                    vi                    wi 1                1                1 2                6                2 3                18              5 4                22              6 5                28              7 knapsack instance (weight limit W = 11) Greedy     -  가격이 높은 것 부터 선택     -  무게가 가벼운 것부터 선택     -  단위 무게당 가격이 높은것 부터 선택 i                vi                wi 1                1                1 2                6                2 3                18              5 4                22              6 5                28              7 knapsack instance (weight limit W = 11) 순환식 - OPT(i) : 아이템 1,2,...,i로 얻을 수 있는 최대 이득 - 경우 1: 아이템 i를 선택하지 않는 경우           OPT(i) = OPT(i-1) - 경우 2: 아이템 i를 선택하는 경우          OPT(i) = ? 순환식     -  OPT(i, w) : 배낭 용량이 w일 때 아이템 1,2,...,i로 얻을 수 있는 최대 이

Longest Common Subsequence Longest Common Subsequence(LCS) - <bcdb>는 문자열 < a bc b d a b>의 subsequence이다. - <bca>는 문자열 < a bc bd ab>와 <b d ca ba >의 common subsequence 이다. - Longest common subsequence(LCS)      common subsequence들 중 가장 긴 것      <bcba>는 <abcbdab>와 <bdcaba>의 LCS이다 Brute Force - 문자열 x의 모든 subsequence에 대해서 그것이 y의 subsequence가 되는지 검사한다. - |x|=m, |y|=n - x의 subsequence의 개수 = 2m - 각각이 y의 subsequence인지 검사: O(n)시간 - 시간복잡도 O(n2m) Optimal Substructure x                ㅁㅁㅁㅁㅁㅁㅁ [A] ㅁㅁ                                            ↑                                            ↓           y                   ㅁㅁㅁㅁㅁㅁ [A]                                    ↑                                          /                                 ↓      LCS z         ㅁㅁㅁㅁㅁㅁ [A] ㅁㅁ ㅁㅁㅁㅁㅁㅁ 는  ㅁㅁㅁㅁㅁㅁ 와  ㅁㅁㅁㅁㅁㅁㅁ 의 LCS이다. 순환식 L[i, j] : 문자열  X =< x1x2 ··· xi >와 Y =< y1y2 ··· yj >의 LCS의 길이 X [x1] [x2] [      ] [      ] [xi-1] [xi]                        

     Matrix-Chain Multiplication 행렬의 곱셈 p×q 행렬 A와 q×r 행렬 B 곱하기 void product(int A[][], int B[][], int C[][]) {       for (int i=0; i<p; i++) {            for (int j=0; j<r; j++) {                 C[i][j] = 0;                 for (int k=0; k<q; k++)                      C[i][j] += A[i][k]*B[k][j;]                 }            }      } 곱셈연산의 횟수 = pqr Matrix-Chain 곱하기 - 행렬 A는 10×100, B는 100×5, C는 5×50 - 세 행렬의 곱 ABC는 두 가지 방법으로 계산가능 (결합법칙이 성립)      (AB를 곱하면 결합법칙이 성립된다)           (AB)C : 7,500번의 곱셈이 필요 (10×100×5 + 10×5×50)           A(BC) : 75,000번의 곱셈이 필요 (100×5×50 + 10×100×50) -  즉 곱하는 순서에 따라서 연산량이 다름 - n개의 행렬의 곱 A1A2A3…An을 계산하는 최적의 순서는? - 여기서 Ai는 pk-1×pk 행렬이다. Optimal Substructure A1 A2 … Ak Ak+1 Ak+2 … An     X               Y                X는 앞부분의 곱이고                                            Y는 뒷부분의 곱이다.             Z 최종 결과 Z는 직전의 두 행렬 X와 Y의 곱이다. 순환식 m[i, j] AiAi+1 ··· Aj 를 곱하는 최소곱셈 횟수 m[i, j] =                                0                                               

Optimal Substructure 동적계획법 1. 일반적으로 최적화문제(optimisation problem) 혹은 카운팅(counting) 문제에 적용됨 2. 주어진 문제에 대한 순환식(recurrence equation)을 정의한다. 3. 순환식을 memoization 혹은 bottom-up 방식으로 푼다. 동적계획법 subproblem들을 풀어서 원래 문제를 푸는 방식. 그런 의미에서 분할정복법 과 공통성이 있음 분할정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않음 즉 서로 overlapping하는 subproblem들을 해결 함으로써 원래 문제를 해결 분할정복법 vs. 동적계획법 quicksort의 경우 pivot을 기준으로 분할된 두 subproblem은 서로 disjoint하다. : 각각 따로 데이터를 정렬하는 방법 (pivot 기준 앞/뒤) Optimal Substructure 어떤 문제의 최적해가 그것의 subproblem들의 최적해로부터 효율적으로 구해질 수 있을 때 그 문제는 optimal substructure를 가진다고 말한다. (A problem is said to have optimal substructure if an optimal solution can be constructed efficiently from optimal solutions of its subproblems.) 분할정복법, 탐욕적기법, 동적계획법은 모두 문제가 가진 이런 특성을 이용 한다. Optimal Substructure를 확인하는 질문 “최적해의 일부분이 그부분에 대한 최적해인가?” 최단경로(shortest-path) 문제 순환식은 optimal substructure를 표현한다. Optimal Substructure를 확인하는 질문 최장경로(Longest-Path) 문제 노드를 중복 방문하지 않고 가는 가장 긴 경로 optimal substructure를 가지는가?

* 윈도우 10에서 사용 가능하다. 바탕화면 -> 마우스 우클릭 -> 새로 만들기 -> 바로가기 바로가기 만들 항목 위치 입력 시  "C:\Program Files (x86)\Google\Chrome\Application\chrome.exe" --disable-web-security --user-data-dir="D:\Chrome" 위와 같이 실행 -> 열기 내에 입력하는 방식으로 입력 예시는 https://hothoony.tistory.com/763 에서 CORS 무시하고 크롬 실행하는 예제 사용 마침 입력. 테스트 진행중에 귀찮아서 system32에 등록하고 사용하려고 만들었다.

Basic Example - 행렬 경로 문제 : 정수들이 저장된 n×n 행렬의 좌상단에서 우하단까지 이동한다. 단 오른쪽이나 아래쪽 방향으로만 이동할 수 있다. 방문한 칸에 있는 정수들의 합이 최소화되도록 하라. Key Observation 세로 축 : i 가로 축 : j => (i,j) (i,j)에 도달하기 위해서는 (i,j-1) 혹은 (i-1,j)를 거쳐야 한다. 또한 (i,j-1) 혹은 (i-1,j)까지는 최선의 방법으로 이동해야 한다. 순환식 L[i, j] : (1,1)  에서  (i,j)까지 이르는 최소합 L[i, j]  =  mij                                                           if i = 1 and j = 1; L[i  1, j] + mij                                         if j = 1; L[i, j  1] + mij                                         if i = 1; min(L[i  1, j], L[i, j  1]) + mij                  otherwise. 경로 구하기 void printPathRecursive(int i, int j)      {            if (i==1 && j==1)                 print(1 + “ “ + 1);            else {                  if (P[i][j] == ‘←’)                      printPathRecursive(i, j-1);                 else                      printPathRecursive(i-1, j);                 print(i + “ “ + j);       } } 이렇게 recursive 하게 구하는 게 낫다. int mat() 같은 경우에도 for 문 두번 돌리면서 경로 구하는 형태임.

다이나믹 프로그래밍 = 동적계획법 피보나치 수열 : 많은 계산이 중복됨 -> recursion 으로 계산하니까 중복현상이 있음! Memoization int fib(int n) {       if (n==1 || n==2)            return 1;       else if (f[n] > -1) /* 배열 f가 -1으로 초기화되어 있다고 가정 */            return f[n]; /* 즉 이미 계산된 값이라는 의미 */       else {            f[n] = fib(n-2) + fib(n-1); /* 중간 계산 결과를 caching */            return f[n];       } } bottom-up 방식으로도 중복 계산을 피할 수 있다. 이항 계수(Binomial Coefficient) int binomial(int n, int k) {       if (n == k || k == 0)            return 1;       else            return binomial(n - 1, k) + binomial(n - 1, k - 1); } 역시 많은 계산이 중복되어 일반적으로  n     n-1             n-1    =           +                   과 같은 경우의 수를 볼 수 있다. k       k              k-1 Memoization int binomial(int n, int k) {        if (n == k || k == 0)            return 1;       else if (binom[n][k] > -1) /* 배열 binom이 -1로 초기화되어 있다고 가정 */            return binom[n][k];       else {            binom[n][k] = binomial(n-1, k) + binomial(n-1, k-1);            return binom

제 6단계 디코딩하기 class HuffmanDecoder public class HuffmanDecoder {       static public void main (String args[]) {            String fileName = "";            HuffmanCoding app = new HuffmanCoding();            RandomAccessFile fIn;            Scanner kb = new Scanner(System.in);            try {                 System.out.print("Enter a file name: ");                 fileName = kb.next();                 fIn = new RandomAccessFile(fileName,"r");                 app.decompressFile(fileName,fIn);                 fIn.close();            } catch (IOException io) {                 System.err.println("Cannot open " + fileName);            }       } } //실제 추가할 함수 decompressFile public void decompressFile(String inFileName, RandomAccessFile fIn)  throws IOException {       String outFileName = new String(inFileName+".dec");       RandomAccessFile fOut = new       RandomAccessFile(outFileName,"rw");       inputFrequencies(fIn);       crea

제5단계 인코딩하기 압축파일의 맨 앞부분(header)에 파일(원본)을 구성하는 run들에 대한 정보를 기록한다. 이 때 원본 파일의 길이도 함께 기록한다. (왜 필요할까?) : 각각의 run 들에게 어떤 codeword를 부여했는지 알아야 복원 가능하기 때문에 codeword에 대한 정보를 기록한다. 아니면 frequency에 대한 정보를 저장한다. outputFrequencies private void outputFrequencies(RandomAccessFile fIn,  RandomAccessFile fOut) throws IOException {     //fIn : 압축할 파일     //fOut : 압축된 파일            fOut.writeInt(runs.size());     // 먼저 run의 개수를 하나의 정수로 출력한다.       fOut.writeLong(fIn.getFilePointer());     // 원본 파일의 크기(byte 단위)를 출력한다.           for (int j = 0; j < runs.size(); j++) {     //             Run r = runs.get(j);            fOut.write(r.symbol); // write a byte            fOut.writeInt(r.runLen);            fOut.writeInt(r.freq);      } } compressFile public void compressFile(String inFileName, RandomAccessFile fIn) //fin은 압축할 파일, inFileName은 그 파일 이름이다. (압축 파일명 정하기 가능)  throws IOException {      String outFileName = new String(inFileName+”.z");     // 압축 파일의 이름은 압축할 파일의 이름에 확장자를 . z를 붙인 것이다.      RandomAcc

제 4단계 Codeword 검색하기 인코딩 - 데이터 파일을 압축하기 위해서는 [데이터 파일을 다시 시작부터 읽으면서 run들을 하나씩 인식한 후 ] 해당 run에 부여된 codeword를 검색하다. - 허프만 트리에서는 모든 run들이 리프노드에 위치하므로 검색하기 불편하다. - 따라서 검색하기 편리한 구조를 만들어야 한다. = 런들이 트리 구조로 되어 있어서 AAA라는 run이 어디에 있는지, 어떤 애가 AAA인지 찾는게 상당히 번거롭게 되어 있음. (규칙성이 없어서 불편함) 이제 4단계에서는 tree 구조 필요가 없어서 다른 자료구조 형태로 변경한다. 예전 가이드 : 해시맵 구조로 변경 현재 가이드 : 연결리스트로 변경 (hashing 비슷한 것) symbol                    : A  codeword               :  0 freg                         : 1 runLen                    : 1 codewordLen          : 2  right                       :  이런 식으로 되어 있으면 runLen이 1이고 symbol이 A 이므로 A이다. symbol                : A  codeword            :  2 freg                    : 2 runLen                : 2 codewordLen        : 2  right                   :  이런 식으로 되어 있으면 runLen이 2이고 symbol이 A이므로 AA이다. 이렇게 symbol이 동일한 run 들을 하나의 연결리스트로 저장한다. 각 run의 right 필드는 다음 노드를 가리키는 링크 필드로 사용한다. 한 run에 대해 마지막 노드는 right 값이 null이 된다. 이렇게 동일한 심볼의 run들을 연결 리스트로 만들어서 저장한다. 크기가 256인 chars 라는 연결 리스트 배열을 만들어서 사용한다. 아스키 코드로

제 3단계 Codeword 부여하기 각각의 런들에게 실제로 코드워드 부여하는 법 : Huffman 트리의 리프 노드에 위치한 run 들에게 이진 codeword 를 부여할 차례이다. -리마인드- Prefix Code : 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드 (codeword란 하나의 문자에 부여된 이진코드를 말함) -리마인드 끝- assignCodeword(prefix, node) 만약에 node가 leaf 이면     prefix 를 node 에 할당한다. (부여한다) 아니면     assignCodeword(prefix + '0' , node.left);     assignCodeword(prefix + '1', node.right); 루트  루트 자식 왼쪽 - 0 | 루트 자식 오른쪽 - 1 루트 자식 왼쪽의 왼쪽 - 00 | 루트 자식 왼쪽의 오른쪽 - 01  ㄴ 이런 식으로 자식 위치에 따라서 나의 codeword 에 0  이나 1을 추가한다. 루트 자식 오른쪽의 왼쪽 - 10 | 루트 자식 오른쪽의 오른쪽 - 11  루트 자식 오른쪽의 오른쪽의 왼쪽 - 110 | 루트 자식 오른쪽의 오른쪽 - 111 ㄴ 이런 식으로 추가하라는 수도 코드임 여기서 prefix를 하나의 32비트 정수로 표현한다 (8비트) 하지만 32비트 중에서 하위 몇 비트만이 실제 부여된 codeword이다. 따라서 codeword의 길이를 따로 유지해야 한다. class Run implements Comparable<Run>{     public byte symbol;     public int runLen;     public int freq;     //트리의 노드로 사용하기 위해서 왼쪽 자식과 오른쪽 자식 노드 필드를 추가한다.     //노드에 부여된 코드워드를 저장하기 위한 필드를 아래와 같이 추가한다.     public int codeword; //부여된

제 2단계 Huffman Tree Huffman coding 알고리즘은 [트리들의 집합]을 유지하면서 매 단계에서 가장 프리퀀시가 작은 두 트리를 찾아서 두 트리를 하나로 합친다. 이런 연산에 가장 적합한 자료구조는 최소 힙이다. (우선순위큐!) 즉 힙에 저장된 각각의 원소들은 하나의 트리이다. (노드가 아니라) ㄴ 런 객체들이 모여서 만들어지는 트리이다. ㄴ extractMin (힙 안의 최소값을 꺼내 주는 것)  ㄴ insert (넣기) 이 기능을 지원하도록 만들 것 최소 힙 - 크기가 5인 힙 - 5개의 트리가 저장되어 있다 - 각 트리는 오직 하나의 노드로 구성되어 있다.  heap 0 : A3 1(프리퀀시 값) 1 : C2 1 2 : A1 1 3 : B1 2 4 : A2 2 이렇게 각각의 런을 싱글 노드 트리라고 보면 되고, 각 트리가 노드 하나짜리 트리이다. min heap은 컴플릿 바이너리 트리 + 힙 프로퍼티를 만족해야 함 부모는 자식보다 작거나 같다 - frequency 값으로 보는 것 A3 1 - C2 1 / A1 1 C2 1 - B1 2 / A2 2  트리 모양은 이런 구조로 되어 있음 힙을 이진 트리 모양으로 만들기는 하는데, 프로그램 상에서는 그냥 1차원 배열 힙으로 만들면 되는 거라서   heap 0 : A3 1(프리퀀시 값) 1 : C2 1 2 : A1 1 3 : B1 2 4 : A2 2 이런 식으로 삽입 하면 된다. 일단 최소 힙 만들기 위해 힙을 만들어서 extreactMin을 두번 반복하고 insert를 하면  공백 7 (루트 - the Root 라고 부름) 공백 4  - 차일드 2      A2 2     B1 2 공백 3  - 차일드 2      C2 1     공백 2 - 차일드 2          A3 1          A1 1 이런 허프만 트리를 조성할 수 있다. class Run implements Comparable<Run>{     public byte symbol;     public int runL

Huffman Method with Run-Length Encoding 무손실 압축 알고리즘을 하이브리드로 이용해서 구현을 해 본다고 한다.   - 파일을 구성하는 각각의 run 들을 하나의 super-symbol로 본다. 이 super-symbol에 대해서 허프만 코딩을 적용한다. 예를 들어 AABAACCAABA는 AAA B AA CC AA 로 구성되며 등장 회수는 1 1 1 2 2 와 같다. A3 - 1 C2 - 1 A1 - 1 B1 - 2 A2 - 2 이 파일에 등장하는 run 들에게 이진 코드를 부여해서 동작시킨다. A3 - 110 C2 - 10 A1 - 00 B1 - 01 A2 - 111 로 run에 대해서 이진 코드를 부여하면 AAABAACCAABA는 110 01 10 111 10 01 00 으로 인코딩 된다 1100110111100100 <- 이거 이진 트리로 변경 하면 접두사가 겹치지 않는 트리를 제작 가능 * Run과 frequncy 찾기 - 압축할 파일을 처음부터 끝까지 읽어서 파일을 구성하는 run 들과 각 run 들의 등장횟수를 구한다. - 먼저 각 run들을 표현할 하나의 클래스 class run을 정의한다. 클래스 런은 적어도 세개의 데이터 멤버 symbol, runLen, freq를 가져야 한다. symbol만 byte고 다른 것은 다 정수이다. - 인식한 run 들은 하나의 ArrayList에 저장한다. - 적절한 생성자와 equals 메소드를 구현한다. symbol : run이 가지고 있는 단자? (AAA 면 A가 symbol이다) runlen : 길이 freq : 빈도 class Run{     byte symbol;     int runlen;     int freq; } 요러면 데이터 파일을 적어도 두번은 읽어야 한다. 1) run 찾기 2) 실제 압축 수행 RandomAccessFile을 이용해서 데이터 파일을 읽어본다고 한다. [RandomAccessFile]  원래 스트림은 원칙적으로 순서대로 처리되지만  예외적으

Case Study : Huffman Coding Huffman Coding : 대표적인 데이터 압축 알고리즘의 하나  - 무손실 Lossless : 데이터 손실이 있으면 안 되는 경우에 사용한다. - 손실 Lossy : 압축률 측에서 효율적이다. 가령 6개의 문자 a,b,c,d,e,f로 이루어진 파일이 있을 때, 문자의 총 개수는 100,000개이고 각 문자의 등장 횟수가 아래와 같을 때 a : 45 b : 13 c : 12 d : 16 e : 9 f : 5 -> 각 문자를 3 비트로 만듬 a : 000 b : 110 c : 010 d : 011 e : 100 f : 101 (45 + 13 + 12 + 16 + 9 + 5) * 3비트 = 300000비트 고정길이 코드를 사용하면 각가의 문자를 표현하기 위해서 3비트가 필요하며, 따라서 파일의 길이는 300,000 비트가 된다. -> 가변길이 코드를 사용하면 a : 0 1비트 * 45 = 45000비트 b : 101 3비트 * 13 = 39000비트 c : 100 3비트 * 12 = 36000비트 d : 111 3비트 * 16 = 48000비트 e : 1101 4비트 * 9 = 36000비트 f : 1100 4비트 * 5 = 20000비트 위 테이블의 가변길이 코드를 사용하면 224,000비트가 된다. : 압축 효과가 좋아졌다. 근데 이거를 1비트 2비트만 사용하면 파일 크기는 줄어든다고 생각 할 수 있겠으나 인코딩을 하는 것이 나중에 다시 디코딩이 가능해야 하는데 문제가 있을 수 있다. 이런 규칙 : Prefix Code Prefix Code : 어떤 codeword(101, 010 같은 것) 도 다른 codeword의 prefix(접두사)가 되지 않는 코드 (codeword란 하나의 문자에 부여된 이진코드를 말함) -> 어떤 코드도 다른 코드의 접두사가 될 수 없는 것이다.  0일 경우 어떤 코드도 0 으로 시작 불가 101 일 경우 어떤 코드도 101로 시작 불가 그래서 1101일 경우에는

Floyd-warshell Algorithm : 동적계획법의 일종  (수학과 컴퓨터 과학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.) - 가중치 방향 그래프 G=(V,E), V = {1,2,... n} - 모든 노드 쌍들간의 최단경로의 길이를 구함 - d^k[i,j[ : 중간에 노드집합 {1,2...k}에 속한 노드들만 거쳐서 노드 i에서 j까지 가는 최단경로의 길이  ㄴ 노드 i에서 j까지 가는 최단경로는 두 가지 경우가 있다 (노드 k를 지나는 경우 , 지나지 않는 경우) i에서 j까지 경로가 k를 안 지나면 중간정점들이 모두 {1,2,...k}에 속한다. i에서 j까지의 경로가 k를 지나면 중간정점들이 모두 {1,2,... k-1}과 {1,2...k-1}에 속한다.  이 알고리즘은 처음에 모든  {\displaystyle (i,j)} 쌍에 대해서  {\displaystyle k=1} 일 때  {\displaystyle \mathrm {shortestPath} (i,j,k)} 를 계산하고, 다음으로  {\displaystyle k=2} 일 때를 계산하는 식으로  {\displaystyle k=N} 이 될 때까지 계속하면, 모든  {\displaystyle (i,j)} 쌍에 대해서 최단 경로를 찾게 된다. 기본적인 알고리즘의 의사코드는 다음과 같다: 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge ( u , v ) 3 dist[ u ][ v ] ← w( u , v ) // 변 ( u , v )의 가중치 4 for each vertex v 5 dist[ v ][ v ] ← 0 6 f

Bellman-Ford 알고리즘 : 이어서 수업  * 릴랙스 하는 순서에 따라서 결과가 달라질 수 있음 : 따라서 진행 되는 결과가 변경 될 수 있긴 함 * 얘는 시간 복잡도 측면에서는 좋은 알고리즘이 아님 Dijkstra의 알고리즘 : 네트워크에서 하나의 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 최단 경로는 경로의 길이순으로 정해진다.  Dijkstra의 알고리즘에서는 시작 정점에서 집합 S에 있는 정점만을 거쳐서 다른 정점으로 가는 최단 거리를 기록하는 배열이 반드시 있어야 한다. * 한 번 노드를 선택한 게 있으면 두번 선택 불가 (최단 경로는 중복 불가) -음수 가중치가 없다고 가정 - s로부터의 최단경로의 길이를 이미 알아낸 노드들의 집합 S를 유지. 맨 처음엔 S={s}. - Loop invariant :  u !∈ S 인 각 노드 u에 대해서 d(u)는 이미 S에 속한 노드들만 거쳐서 s로부터 u 까지 가는 최단경로의 길이 - 정리 : d(u) min v!∈S d(v)인 노드 u에 대해서, d(u)는 s에서 u까지의 최단경로의 길이이다. - 증명은 다른 경로가 존재할 경우에 d(v) >_ d(u) 이므로 모순이라 한다  (s에서 u까지 다른 최단경로가 존재한다고 했을 때) d(u)가 최소인 노드 u!∈S를 찾고, S에 u를 추가 S가 변경되었으므로 다른 노드들의 d(v) 값을 갱신 즉, 에지 (u,v)에 대해서 relaxation 하면 루프 불변이 유지됨 요...요약하면 프림이랑 다익스트라는 루프문 내 조금 다른 거 빼고는 똑같다고 볼 수 있어서 사실 Prim 의 알고리즘이랑 동일하다고 보면 된다고 한다 (-.-);;; 어려워서 나무위키 도움을 받음 다익스트라 알고리즘은 다음과 같다. (P[A][B]는 A와 B 사이의 거리라고 가정한다) 1. 출발점으로부터의 최단거리를 저장할 배열 d[v]를 만들고, 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채워 넣는다. (정말 무한이 아닌, 무

최단경로 - 가중치 (방향) 그래프 G = (V,E), 즉 모든 에지에 가중치가 있음. - 경로 p = (v0, v1, ... vk)의 길이는 경로상의 모든 에지의 가중치의 합 - 노드 u에서 v까지의 최단경로의 길이를 δ(u, v)라고 표시하자.   최단경로문제의 유형 - Single-source  : 하나의 출발 노드 s로부터 다른 모든 노드까지의 최단 경로를 찾아라. - Single-destination : 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾아라. * single-source와 singled-destination은 사실상 같은 것으로 볼 수 있다. - Single-pair : 주어진 하나의 출발 노드 s로부터 하나의 목적지 노드 t까지의 최단 경로를 찾아라. * 최악의 경우 시간 복잡도에서 Single-Source 문제보다 나은 알고리즘이 없을 수 있다. - All-pairs : 모든 노드 쌍에 대해서 최단 경로를 찾아라. 최단 경로와 음수 가중치 - 음수 가중치  : 가중치가 음수인 경우 - 음수 사이클이 있으면 최단 경로가 정의되지 않는다. * 알고리즘에 따라 음수 가중치가 있어도 작동하는 경우도 있고, 그렇지 않은 경우도 있다. 최단 경로의 기본 특성 - 최단 경로의 어떤 부분경로도 역시 그 부분에 대한 최단 경로이다 * 전체 u~v에서, u에서 v까지의 최단 경로를 지정했을 떄, 중간 위치의 x~y 가 있다면 이 경로는 x에서 y까지의 최단경로이다. - 최단 경로는 사이클을 포함하지 않는다. ( 음수 사이클이 없다는 가정 ) Single-source (one to all) 최단경로문제 - 입력 : 음수 사이클이 없는 가중치 방향그래프 G=(V,E)와 출발 노드 s ∈ V - 목적 : 각 노드 v ∈ V에 대해서 다음을 계산한다. - d[v]     - 처음에는 d[s]=0, d[v]=∞ 로 시작한다.     - 알고리즘이 진행됨에 따라서 감소해간다. 하지만 항상 d[v] ≥ δ(s,v)를 유지한다.     - 최종적으로는  d

String to hex String appendValue = ""; StringBuffer sbuf = new StringBuffer();         for(int i=0; i<변경할String.length(); i++){         sbuf.append( "0x" + Integer.toHexString(변경할String.charAt(i)) );         }         appendValue = sbuf.toString();              System.out.println("Original Page default " + 변경할String); System.out.println("Original Page convert " + appendValue); hex to String String convertValue = ""; Pattern p = Pattern.compile("(0x([a-fA-F0-9]{2}([a-fA-F0-9]{2})?))");     Matcher m = p.matcher(변경된String);     StringBuffer sb = new StringBuffer();     int hashCode = 0;     while( m.find() ) {         hashCode = Integer.decode("0x" + m.group(2));         m.appendReplacement(sb, new String(Character.toChars(hashCode)));     }     m.appendTail(sb);     convertValue = sb.toString(); System.out.println("GPKIError Page convert : " + convertValue); 구글링 해서 찾은 것 중에 이거만 오류