텍스트를 암호화는 방법 중에 보안상 취약하긴 하지만 흔하게 쓰이는 방법으로 알파벳 글자를 다른 글자로 돌리는 방법이 있다.
즉 알파벳의 각 글자를 다른 글자로 치환한다. 암호화된 것을 다시 원래대로 되돌릴 수 있으려면 두 개의 서로 다른 글자가 같은 글자로 치환되지 않아야 한다.
암호화된 텍스트가 한 줄 입력되는데, 이 때 매 시도마다 서로 다른 치환 방법이 적용된다.
암호화 이전의 텍스트에 있는 단어는 모두 주어진 사전에 들어있는 단어라고 가정하고, 암호화 된 텍스트를 해독하여 원래 텍스트를 알아내자.
입력
입력은 한 개의 정수 n이 들어 있는 행으로 시작되며 그 다음 줄부터는 한 줄에 하나씩 n개의 소문자로 쓰인 단어들이 입력된다.
이 n개의 단어들은 복호화된 텍스트에 들어갈 수 있는 단어로 구성된 사전이다. 사전 뒤에는 몇 줄의 텍스트가 입력된다.
각 줄은 앞에서 설명한 방법에 따라서 복호화 된다.
사전에 들어갈 수 있는 단어의 수는 1000개를 넘어가지 않는다. 단어의 길이는 16 글자를 넘지 않는다.
암호화된 텍스트에는 소문자와 스페이스만 들어가며 한 줄의 길이는 80 글자를 넘어가지 않는다.
출력
각 줄을 복호화하여 표준 출력으로 출력한다. 여러 문장으로 복호화 할 수 있다면 그 중 아무 결과나 출력하면 된다.
가능한 풀이가 없다면 모든 문자를 아스테리스크(*)로 바꾸면 된다.
예제
6
and
dick
jane
puff
spot
yertle
bjvg xsb hsxn xsb qymm xsb rqat xsb pnetfn
dick and jane and puff and spot and yertle
해설
꽤 좌절을 겪은 문제다. 이래저래 2달 정도 걸린 것 같다. 내가 생각한 풀이는 다음과 같다.
1. 입력으로 받은 사전과 암호화 된 단어의 '알파벳'을 기준으로 치환 가능한 모든 '조합'을 구한다.
2. 구해진 '조합'으로 암호화 된 단어를 복호화 해서 원본 단어가 모두 있으면 출력
3. 하나라도 원본 단어가 없다면 모든 단어를 아스테리스크(*)로 출력
재귀 호출(Recursive Call)을 이용해서 '하노이 탑' 문제 풀듯이 했는데, 방법 자체는 맞는 것 같다.
다만 문제가 시간이 기하급수적으로 오래 걸린다는 것이다. '조합'을 구하는데 알파벳 수의 Factorial 만큼 걸리는데 어마어마한 수가 나온다.
일단 답은 올린다. 시간만 오래 걸리는거 빼고는 잘 동작하는 것 같다.
다시 이 문제를 찬찬히 읽어보니, 알파벳이 아니라 그냥 단어 단위로 쉽고 무식하게 풀면 될 것 같긴한데 너무 처음에 어렵게 생각한 걸까?
기회가 되면 2번째 풀이를 이 글에 올려보겠다~
# Quiz 0012, Crypt Kicker
# written by badsaram
import sys
class CryptKicker(object):
def __init__(self, dbgMode):
self.numDictionary = 0
self.dictionary = []
self.cryptFrom = []
self.cryptTo = []
self.cryptMatrix = []
self.dbgMode = dbgMode
def inputDictionary(self):
str = input()
if ((str.isdigit() != True) or (int(str) <= 0) or (int(str) > 1000)):
print("Please Input Correct Number (0 < n <= 1000).")
sys.exit(-1)
self.numDictionary = int(str)
for i in range(0, self.numDictionary):
str = input()
if ((len(str) > 16) or (str.isalpha() == False)):
print("Please Input String Under 16 Characters. You should input %d strings" % (self.numDictionary))
sys.exit(-1)
self.dictionary.append(str)
self.makeSymbolArray(self.dictionary, self.cryptFrom)
def makeSymbolArray(self, words, cryptArray):
# make cryptFrom
for word in words:
for ch in word:
try:
cryptArray.index(ch)
except:
cryptArray.append(ch)
def isEmpty(self, ch):
ret = False
if (ch.isalpha() == True):
ret = False
else:
ret = True
return ret
def insertCryptMatrix(self, cryptPattern):
dup_flag = False
for pattern in self.cryptMatrix:
sameCnt = 0
for i in range(len(pattern)):
if (pattern[i] == cryptPattern[i]):
sameCnt += 1
else:
break
if (sameCnt == len(pattern)):
dup_flag = True
break
if (dup_flag == False):
self.cryptMatrix.append(cryptPattern.copy())
if (self.dbgMode == True):
print(cryptPattern)
def makeCryptMatrix(self, cryptMatrix, n):
for i in range(len(self.cryptFrom)):
cryptPattern = [ '' for i in range(len(self.cryptFrom)) ]
for j in range(len(self.cryptTo)):
try:
cryptPattern.index(self.cryptTo[j])
except:
cryptPattern[i] = self.cryptTo[j]
self.makeCryptMatrixRecursive(cryptPattern, n + 1)
cryptPattern[i] = ''
def makeCryptMatrixRecursive(self, cryptPattern, n):
if ( (n >= len(self.cryptFrom)) or (n >= len(self.cryptTo)) ):
self.insertCryptMatrix(cryptPattern)
return
for i in range(len(self.cryptFrom)):
if (self.isEmpty(cryptPattern[i]) == False):
continue
for j in range(len(self.cryptTo)):
try:
cryptPattern.index(self.cryptTo[j])
except:
cryptPattern[i] = self.cryptTo[j]
self.makeCryptMatrixRecursive(cryptPattern, n + 1)
cryptPattern[i] = ''
def decodeChar(self, pattern, ch):
index = pattern.index(ch)
return self.cryptFrom[index]
def tryDecode(self):
successFlag = False
strInput = input()
encodedWords = strInput.split(" ")
self.makeSymbolArray(encodedWords, self.cryptTo)
if (len(self.cryptTo) > len(self.cryptFrom)):
successFlag = False
else:
self.makeCryptMatrix(self.cryptMatrix, 0)
if (self.dbgMode == True):
print(self.cryptMatrix)
for pattern in self.cryptMatrix:
successFlag = True
decodedResult = []
for word in encodedWords:
temp = list(word) # string is immutable
for i in range(len(word)):
temp[i] = self.decodeChar(pattern, word[i])
decodedWord = ''.join(temp)
if (self.dictionary.count(decodedWord) > 0):
if (self.dbgMode == True):
print("%s is found" % (decodedWord))
decodedResult.append(decodedWord)
else:
successFlag = False
break
if (successFlag == True):
break
if (successFlag == True):
if (self.dbgMode == True):
print("found")
self.printDecodedWord(decodedResult)
else:
if (self.dbgMode == True):
print("not found")
self.printNotDecodedWord(encodedWords)
def printDecodedWord(self, decodedResult):
for word in decodedResult:
print(word, end=' ')
def printNotDecodedWord(self, encodedWords):
for word in encodedWords:
for i in range(len(word)):
print("*", end='')
print(" ", end='')
if __name__ == '__main__':
dbgMode = False
obj = CryptKicker(dbgMode)
obj.inputDictionary()
obj.tryDecode()
방글라데시의 정당들은 자신의 세를 과시하기 위해 정기적인 동맹 휴업(파업)을 추진한다고 합니다.
이 문제는 동맹 휴업 지수(hartal parameter)라고 부르는 h라는 양의 정수로 나타낼 수 있습니다. 이 값은 한 동맹 휴업과 다른 동맹 휴업 사이의 기간을 날짜 수로 표시한 값입니다.
세 개의 정당이 있다고 생각해봅시다. i 번째 당의 동맹 휴업 지수를 h(i) 라고 할 때, h(1) = 3, h(2) = 4, h(3) = 8 이라고 가정합니다. N일(N=14)일 동안의 세 당의 행보를 시뮬레이션하면 다음과 같이 표시할 수 있습니다. 시뮬레이션은 항상 일요일에 시작하며 금요일이나 토요일에는 동맹 휴업이 없습니다.
요일
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1번 정당
X
X
X
X
2번 정당
X
X
X
3번 정당
X
동맹 휴업
1
2
3
4
5
이 결과를 보면 14일 동안 정확하게 다섯 번의 동맹 휴업(3, 4, 8, 9, 12일)이 있음을 알 수 있습니다. 6일은 금요일이기 때문에 동맹 휴업이 일어나지 않습니다. 결국 2주 동안 근무 일수로 5일의 동맹 휴업이 실시됩니다.
몇 정당의 동맹 휴업 지수와, 어떤 정수 N이 주어졌을 때, N일 가운데 동맹 휴업으로 인해 일을 하지 않은 근무 일수를 계산해봅시다.
입력
입력의 첫째 줄에는 한 개의 정수 N(7≤ N ≤ 3,650)이 들어있으며 시뮬레이션을 돌릴 기간(날 수)를 나타냅니다. 그 다음 줄에는 정당의 개수를 나타내는 정수 P(1 ≤ P ≤ 100) 가 들어갑니다. 그 다음부터 시작하는 P개의 줄 가운데 i 번째 줄(1≤ i ≤ P) 에는 i번째 동맹 휴업 지수를 나타내는 양의 정수 h(i)가 들어있습니다. 이때 h(i) 값은 7의 배수가 아닙니다.
출력
각 입력에 대해 손실된 근무 일수를 한 줄에 하나씩 출력합니다.
예제
해설
기간을 입력 받고 그 갯수만큼 리스트(배열) 할당. 이 후에는 각 정당별로 휴업 일수마다 '1'로 Marking.
Marking시 금요일, 토요일일때는 수행하지 않고 건너뛰도록 해준다. 모든 정당에 대해서 수행한 뒤, 나중에 Marking된 '1'의 갯수가 몇개인지 확인하면 끝.
# Quiz 0011, Hartal
# written by badsaram
import sys
class Hartal(object):
def __init__(self):
self.working_day = 0
self.member_count = 0
self.working_states = []
self.hartal_parameters = []
def input(self):
# input days
str = input()
if (str.isdigit() == False):
print("Please input number for working days")
sys.exit(-1)
working_day = int(str)
if ((working_day < 7) or (working_day > 3650)):
print("Please input working days in 7 - 3650 range.")
sys.exit(-1)
# input member count
str = input()
if (str.isdigit() == False):
print("Please input number of member count")
sys.exit(-1)
member_count = int(str)
if ((member_count < 1) or (member_count > 100)):
print("Please input member count in 1 - 100 range.")
sys.exit(-1)
hartal_parameters = []
# input hartal parameter
for i in range(member_count):
str = input()
if (str.isdigit() == False):
print("Please input number for hartal parameters.")
sys.exit(-1)
hartal_parameters.append(int(str))
working_states = [ 0 for i in range(working_day) ]
self.working_day = working_day
self.member_count = member_count
self.working_states = working_states
self.hartal_parameters = hartal_parameters
def calc(self):
if ((self.hartal_parameters == []) or (self.working_states == [])):
print("There is no hartal parameters and working states.")
return
for hartal_parameter in self.hartal_parameters:
for day in range(0, self.working_day, hartal_parameter):
if (((day % 7) != 6) and ((day % 7) != 7) and (day != 0)):
self.working_states[day - 1] = 1
print("%d" % (self.working_states.count(1)))
if __name__ == '__main__':
obj = Hartal()
obj.input()
obj.calc()
우측 밑에 "Downloads for open source users" 라는 항목이 있죠? 이걸 선택해 줍니다.
좀 더 가시면 "Download the Qt Online Installer"가 있습니다. 이걸 선택해 줍니다.
이어지는 메뉴에서 "Download"를 눌러서 Installer를 다운 받고 실행해줍니다. Installer 파일명은 "qt-unified-windows-x64-4.4.1-online.exe" 이런 식의 이름을 가지고 있습니다. 이 글을 쓰는 시점에서 버전은 4.4.1인 것 같습니다.
인스톨러 화면이 뜹니다. QT 가입은 하셨나요? 없으면 여기서 계정을 만들어서 로그인까지 해주고 쭉쭉 진행해줍니다.
구성 요소에서 선택은 아래처럼 해주세요
개인 개발자는 "나는 개인이며 어떤 회사 업무에도 Qt를 사용하지 않습니다" 선택. 회사라면 회사 정보도 입력.
Custom Installation 을 선택합니다. 밑에서 따로 QT 버전과 MinGW 버전을 선택하기 위함입니다. 그냥 필요 없다면 "Qt 6.3 for desktop development" 를 선택하셔도 됩니다.
QT 버전은 최신으로. 이 시점에서는 6.3.1이 최신이었습니다. 설치하는 김에 MinGW 11.2.0 64-bit도 넣었습니다.
용량이 꽤 되네요. 설치를 시작합니다. 32GB 정도네요. 용량이 너무 크다면 본인에 맞게 구성 요소를 조정해줍니다.
시간이 제법 걸리니 가볍게 영화를 하나 시청해 줍니다.
수시간이 걸려서 겨우 설치가 됐습니다. 저는 노트북에 설치했는데 절전 모드 들어가니까 다운로드가 취소 됐습니다. 이 부분 감안하셔서 절전 모드를 필요시 잠시 끄는 것도 필요할 것 같습니다.
Visual Studio 에 QT 연동하기
Visual Studio에 QT 확장을 설치해봅시다. 상단 메뉴에서 "확장" → "확장관리" 에서 "qt" 로 검색해서 "Qt Visual Studio Tools" 를 설치합니다.
설치하고 Visual Studio 2022를 실행하면 아래처럼 Qt version을 설정하라는 메시지가 뜹니다. 눌러줍니다.
아래처럼 qmake.exe가 있는 곳을 찾아서 선택해줍니다. 예제의 경우 "C:\Qt\6.3.1\msvc2019_64\bin\qmake.exe" 입니다.
이후에도 상단 메뉴 "확장" → "Qt VS Tools" → "Qt Versions" 에서 확인이랑 설정을 변경할 수 있습니다.
Qt Project 생성하기
이제 Visual Studio 2022를 실행해서 QT 프로젝트를 만들어봅니다.
"새 프로젝트 만들기" → "C++" 을 선택. 템플릿에서 조금 밑으로 내리면 아래처럼 QT 프로젝트들이 보입니다.
예제로 하나 만들어보려고 하니, "Qt Quick Application"을 선택해서 프로젝트 경로를 적당한 곳에 만들어줍니다. 아래 화면이 나오면 프로젝트가 만들어진 것입니다.
샘플 소스 코드가 보입니다. 여기서 자신의 코드를 덧붙여서 작업을 하면 되겠습니다.
샘플 소스 코드 그대로 실행한 결과입니다.
윈도우용 QT 응용 프로그램을 만들려면 아무래도 Python + Qt 가 접근성에서는 좋습니다.
하지만 Device Driver 처럼 좀 더 시스템에 밀접한 작업을 해야할 경우에는 C/C++이 제격이죠.
호주(오스트레일리아) 에서는 투표를 할 때, 모든 후보에 대해서 선호도 순으로 투표를 한다고 합니다.
처음에는 1순위로 선택한 것만 집계를 먼저하고, 이 중 한 후보가 50% 이상 득표하면 그 후보가 바로 선출됩니다. 하지만 50% 이상 득표한 후보가 없으면 가장 적은 표를 받은 후보(둘 이상이 될 수 있음)가 우선 탈락합니다. 그리고 이렇게 탈락한 후보를 1순위로 찍었던 표만 다시 집계해서 아직 탈락하지 않은 후보들 가운데 가장 높은 선호를 얻는 후보가 그 표를 얻게 됩니다.
이런 식으로 가장 약한 후보들을 탈락시키면서, 그 다음 순위의 아직 탈락하지 않은 후보에게 표를 주는 과정을 50% 이상의 표를 얻는 후보가 나오거나 탈락되지 않는 후보가 동률이 될때까지 반복한다.
입력
첫 입력은 후보 수를 나타내는 20 이하의 정수 n이 입력된다. 그 밑으로 n개의 줄에 걸쳐서 후보의 이름이 순서대로 입력되며 각 후보의 이름은 80글자 이하로 출력 가능한 문자로 구성된다.
그 뒤에는 최대 1,000줄이 입력될 수 있는데, 각 줄에는 투표 내역이 입력된다. 각 투표 내역에는 어떤 순서로 1부터 n까지의 수가 입력된다. 첫번째 숫자는 1순위로 찍은 후보의 번호, 두번째 숫자는 2순위로 찍은 후보의 번호, 이런 식으로 숫자가 기록된다.
출력
각 테스트 케이스에 대해 당선된 후보의 이름 한 줄, 또는 동률을 이룬 후보들의 이름이 들어있는 여러줄을 출력한다. 두 개 이상의 테스트 케이스가 있는 경우 각 결과는 한 개의 빈줄로 구분한다.
예제
해설
문제는 단순한데 구현하면서 꽤 골치가 아팠던 문제입니다.
처음 투표 평가하고, 탈락자 선별 이후에 다시 재귀적으로 처리하는 부분에서 깔끔하게 구현하려고 고민 좀 했습니다.
# AusVote.py , 0008 quiz
# written by badsaram
import sys
class AusVote(object):
def __init__(self):
self.info_candidates = []
self.info_votes = []
self.info_scores = []
self.max_candidates = 20
self.max_namelen = 80
self.max_votes = 1000
def inputCases(self):
max_candidates = 0
# input candidates
str = input()
if (str.isdigit() == False):
print("Please input number.")
sys.exit(-1)
max_candidates = int(str)
if ((max_candidates > self.max_candidates) or (max_candidates < 0)):
print("number of candidates : (0 < n <= 20)")
sys.exit(-1)
for i in range(max_candidates):
str = input()
if (len(str) > self.max_namelen):
print("name is too long. The size of name is under %d" % (self.max_namelen))
sys.exit(-1)
self.info_candidates.append(str)
self.info_scores.append(0)
for i in range(self.max_votes):
str = input()
if (str == ""):
break
str_votes = str.split(' ')
if (len(str_votes) != max_candidates):
print("please input votes correctly")
sys.exit(-1)
int_votes = []
for str_vote in str_votes:
if (str_vote.isdigit() == False):
print("plese input number")
sys.exit(-1)
int_votes.append(int(str_vote))
self.info_votes.append(int_votes)
def calcVotes(self):
isFinished = False
if (len(self.info_votes) <= 0):
return
for each_vote in self.info_votes:
target = self.findVotes(each_vote, 1)
self.info_scores[target] += 1
while (isFinished == False):
if (self.checkAllSame(self.info_scores) == True):
isFinished = True
elif ( max(self.info_scores) >= (len(self.info_votes) / 2) ):
isFinished = True
else:
# drop out loser
target = self.findMin(self.info_scores)
losers = self.findLosers(self.info_scores, target)
self.recalcScore(losers, self.info_votes)
if (isFinished == True):
target = max(self.info_scores)
winners = self.findWinners(self.info_scores, target)
for winner_name_index in winners:
print("%s " % (self.info_candidates[winner_name_index]))
def checkAllSame(self, scores):
ret = True
target = scores[0]
for score in scores:
if (target != score):
ret = False
break
return ret
def findMin(self, scores):
minScore = -1
for score in scores:
if (score >= 0):
if (minScore == -1):
minScore = score
elif (score < minScore):
minScore = score
else:
pass
return minScore
def findVotes(self, info_votes, rank):
ret = -1
for i in range(0, len(info_votes) - 1):
if (info_votes[i] == rank):
ret = i
break
return ret
def findLosers(self, scores, min_score):
ret = []
for i in range(0, len(scores)):
if (scores[i] == min_score):
ret.append(i)
return ret
def findWinners(self, scores, max_score):
ret = []
for i in range(0, len(scores)):
if (scores[i] == max_score):
ret.append(i)
return ret
def recalcScore(self, losers, info_votes):
for each_vote in info_votes:
for loser_num in losers:
if (each_vote[loser_num] == 1):
target = self.findVotes(each_vote, 2)
self.info_scores[target] += 1
for loser_num in losers:
self.info_scores[loser_num] = -1
def makeTestPattern1(self):
self.info_candidates.append('John Doe')
self.info_candidates.append('Jane Smith')
self.info_candidates.append('Sirhan Sirhan')
self.info_votes.append([1, 2, 3])
self.info_votes.append([2, 1, 3])
self.info_votes.append([2, 3, 1])
self.info_votes.append([1, 2, 3])
self.info_votes.append([3, 1, 2])
self.info_scores.append(0)
self.info_scores.append(0)
self.info_scores.append(0)
def makeTestPattern2(self):
self.info_candidates.append('John Doe')
self.info_candidates.append('Jane Smith')
self.info_candidates.append('Sirhan Sirhan')
self.info_votes.append([1, 2, 3])
self.info_votes.append([2, 1, 3])
self.info_votes.append([2, 3, 1])
self.info_votes.append([1, 2, 3])
self.info_votes.append([3, 1, 2])
self.info_votes.append([3, 2, 1])
self.info_scores.append(0)
self.info_scores.append(0)
self.info_scores.append(0)
def makeTestPattern3(self):
self.info_candidates.append('John Doe')
self.info_candidates.append('Jane Smith')
self.info_candidates.append('Sirhan Sirhan')
self.info_votes.append([1, 2, 3])
self.info_votes.append([2, 1, 3])
self.info_votes.append([2, 3, 1])
self.info_votes.append([1, 2, 3])
self.info_votes.append([3, 1, 2])
self.info_votes.append([3, 2, 1])
self.info_votes.append([1, 2, 3])
self.info_votes.append([2, 1, 3])
self.info_votes.append([1, 2, 3])
self.info_scores.append(0)
self.info_scores.append(0)
self.info_scores.append(0)
if __name__ == '__main__':
obj = AusVote()
obj.inputCases()
#obj.makeTestPattern1()
#obj.makeTestPattern2()
#obj.makeTestPattern3()
obj.calcVotes()
