[pwnable.kr] coin1

해킹대회 문제 풀이 연습장소

Moderator: amesianx

Post Reply
gee8195
Posts: 34
Joined: Thu Jul 21, 2016 5:12 pm

[pwnable.kr] coin1

Post by gee8195 » Wed Oct 26, 2016 4:40 pm

1.png
1.png (17 KiB) Viewed 354 times
잠시 미뤄뒀던 코딩문제를 풀어봤습니다.


2.png
2.png (150.41 KiB) Viewed 354 times
문제에서 주는 호스트와 포트로 연결을 해보면 이와같은 설명이 나옵니다.
해석하면 금화동전 몇개를 주고 그들가운데 실제 동전과 같지만 무게가 다른 가짜동전이 있으니
가짜 동전을 찾으라는 것 같습니다. 실제 동전의 무게는 10이고 가짜 동전의 무게는 9라고 나와있습니다.
인터넷에 가짜동전찾기라고 검색하면 나오는 수많은 게임과 비슷한것 같습니다.
문제의 게임방법은
1.돈전개수(N) 과 기회수(C)를 줍니다.
2.계량 동전의 인덱스 번호의 집합을 지정
3.무게 정보를 획득
4.(C) 2 ~ 3 번을 반복, 하고 대답을 얻을수 있습니다.
그밑에는 간단한 예시가 나와있습니다.

즉 N개의 코인이 주어지고 C번의 기회를 이용해서 코인의 무게를 확인한뒤 무게가 9인 가짜동전을 찾는것입니다.

처음 문제를 봤을떄 운이 좋으면 코인갯수가 적어 손으로 풀수있을까해서 풀었는데 100 counterfeit coin을 간과했습니다...
30초 이내에 가짜코인 100개를 찾아내야합니다. 무조건 코딩으로 풀수밖에 없는 문제입니다.
그러기 위해선 소켓프로그래밍과, 가짜코인찾는 알고리즘을 구현해야 할것 같습니다.
일단 정보를 얻기위해 위와같이 코인을 입력해봤습니다.
입력할수 있는 코인의 수는 문제에서 주는 코인의 개수까지 입력이 가능합니다. 만약 100개를 준다면 0부터 99까지
입력했을때 당연히 하나는 가짜코인이 있을테니 무게가 999가 나옵니다.


3.png
3.png (8.76 KiB) Viewed 354 times
여기서 한가지 정보를 추가해서 주어지는 코인개수와 기회는 2 ^ C > N 로 계산하면 항상 참이됩니다.
2 ^ 5(C) == 32
2 ^ 7(C) == 128
2 ^ 10(C) == 1024
이와 같이 항상 동전의 개수보다 크게 나옵니다. 그말은 코인의 개수를 반개찍 나눠가면서 무게를 구하고
동전이 있는 없는 부분을 걸러내다보면 주어진 기회안에 가짜동전을 찾아낼 수 있다는 결론이 나옵니다.
한번만 맞추는 거라면 어설프게 코드를 짜서 여러번 시도하면 성공하겠지만 100번의 기회를 모두 맞추기
위해서는 적절한 예외처리가 필요하므로 이문제에서는 그걸 요구하는것 같습니다.


4.png
4.png (146.17 KiB) Viewed 354 times
해당 소스코드입니다.


5.png
5.png (54.43 KiB) Viewed 354 times
30초안에 가짜동전을 모두 찾아내어 플래그가 출력됬습니다.
깔끔하게 실행되니 기분이 좋아지는것 같습니다.ㅎ
아직 코드짜는게 익숙하지 않아 시간이 너무 오래걸리니 해결할 코드를 하나씩은 머리에 넣고다니는 연습을
하면 도움이 될것 같습니다.

Post Reply

Who is online

Users browsing this forum: No registered users and 18 guests