전체 글

https://www.acmicpc.net/problem/12683문제 각 문제의 정답 확률과 답안 제출 기회를 사용하여 답안을 제출했을 때 모든 문제를 맞아 시험에 합격할 수 있는 확률의 최댓값을 구하는 문제이다.영어 문제이지만, 번역기 정도만 사용해도 이해할 수 있다. 풀이 답안 제출 기회에 따라 풀이가 달라질 것이다. 만약 답안 제출 기회가 단 한 번만 있을 경우, 문제를 풀 때 합격 확률이 가장 높은 답안을 선택하여 제출해야 한다. 이 답안의 합격 확률은 각 문제의 정답 확률들을 곱했을 때의 값 중에서 가장 큰 값이 되며, 따라서 이 답안은 각 문제의 정답 확률 중에서 가장 높은 값들이 선택된 답안이 된다.하지만 답안 제출 기회가 여러 번 있을 경우에는 단순하게 접근하기가 어려워진다. 처음 답안을..

https://www.acmicpc.net/problem/3230문제 첫 번째 경기와 두 번째 경기가 끝난 후에 메달권 선수들을 출력하는 문제이다.첫 번째 경기 순서가 선수의 순서가 된다.각 선수들의 순위는 들어왔을 때의 순위이다. 풀이 선수들의 순위가 들어왔을 때 순위로 주어지기 때문에 순위를 계속 업데이트 해주어야 한다. 따라서 순위가 리스트의 인덱스라고 한다면, 해당 인덱스에 삽입해주어야 한다. 때문에 선수를 append 로 추가하기 보다 insert 로 삽입해주어야 한다.두 번째 경기는 슬라이싱을 이용하여 해당 순위에 따라 잘라주면 된다. 사실 아래 코드의 경우 잘라주지 않아도 정상적으로 동작하지만, 두 번째 경기 출전 선수를 명시적으로 나타내고 싶어 슬라이싱을 통해 잘라주었다.마지막 출력은 pr..

https://www.acmicpc.net/problem/18129문제 주어진 문자열을 주어진 기준 수를 이용하여 암호로 바꾸는 문제이다.문자열에서 대소문자 구분없이 특정 알파벳이 기준 수 이상으로 연속되어 있다면 1, 미만이라면 0 으로 치환하고, 이미 치환된 적 있다면 그 구간을 삭제한다. 풀이 주어진 문자열에서 대소문자 구분없이 특정 알파벳이 연속되어 있는지 확인하려면 문자열의 하나의 문자와 그 다음 문자가 같은지 비교하면 된다. 단 문자열의 끝에 도달하면 비교할 문자가 없어지기 때문에 예외처리가 필요하다. 이 문제에서는 문자열이 모두 알파벳이기 때문에 비교하면 무조건 달라지는 숫자를 문자열 끝에 임의로 추가하여 사용하였다.대소문자 구분을 피하기 위해서는 upper 이나 lower 을 활용하면 될 ..

https://www.acmicpc.net/problem/32174문제 주어진 카드 뭉치를 주어진 방법대로 섞고 난 후에 조커의 위치를 찾는 문제이다.조커는 처음에는 덱 가장 위에 있다. 섞는 방법은 세 가지가 있는데 첫 번째 방법은 아래 카드를 위로 올리는 것이고, 두 번째 방법은 위 카드를 아래로 내리는 것이고, 세 번째 방법은 특정 시점에 섞었던 상태로 덱을 바꾸는 것이다. 풀이 중요한 것은 조커의 위치이다. 즉 나머지 카드들이 무엇이고, 어떤 위치에 있는지는 이 문제에서 관심사가 아니다. 따라서 모든 기준을 조커 위치에 맞추고 생각하는 것이 좋다.첫 번째 셔플 방법은 아래 카드를 위로 올리는 것인데, 조커 위치로 생각해본다면 올리는 경우만큼 내려가는 것이다. 인덱스로 생각해보면 더해진다. 다만 이..

https://www.acmicpc.net/problem/32173문제 학생들이 식당에 줄을 설 때 가장 앞, 가장 뒤 중 하나를 선택하여 설 수 있다. 이때 만족도가 변하는데, 경우의 수 중 가장 높은 만족도를 구하는 문제이다. 풀이 학생에게는 맨 앞에 서거나, 맨 뒤에 서는 두 가지 선택지밖에 없다. 즉 두 경우의 수 중 무엇이 만족도 총합을 가장 높게 하는지 확인하면 된다.조건에 따르면 가장 앞에 서게되면 가장 앞에 서는 학생의 만족도 만큼 총 만족도가 올라가지만, 현재 서있는 학생들의 만족도의 합만큼 총 만족도가 감소하게 된다. 그러나 가장 뒤에 서게되면 해당 학생의 만족도는 0 이므로 총 만족도는 변화하지 않는다. 따라서 어떤 학생이 맨 앞에 서느냐가 만족도에 영향을 준다는 것을 알 수 있다.그..

https://www.acmicpc.net/problem/22233문제 중복이 없는 메모장의 키워드에서 새로 작성되는 글에 사용된 키워드들을 제거했을 때 메모장에 남은 키워드의 개수를 구하는 문제이다. 풀이 가장 먼저 입력되는 값이 40만개까지 가능하므로, 빠른 입출력을 지원하는 sys 를 사용해야 한다.메모장에 저장되는 키워드에는 중복이 없기에 새로 작성되는 글의 키워드를 메모장에서 삭제해주면 된다. 이때 새로 작성되는 글에 사용된 키워드가 메모장에 있는지 먼저 확인해야 하는데, 메모장 키워드들을 리스트로 저장한다면 리스트에서 키워드를 탐색할 때 순차적으로 탐색하기 때문에 시간이 오래 걸릴 수밖에 없다. 즉 in 을 활용해서 리스트에서 특정 값을 탐색할 경우 시간 복잡도는 O(N)이다.따라서 리스트가 ..

https://www.acmicpc.net/problem/1158문제 원을 그리고 앉아있는 사람들에 차례로 번호를 매기고, 특정 번째 사람을 제거해 나가면서 제거된 사람들의 번호인 요세푸스 순열을 구하는 문제이다.제거되는 것은 특정 번째를 기준으로 하지만, 각 사람들의 번호는 처음 차례로 매겨진 번호이다. 풀이 주어진 사람들의 리스트에서 주어진 차례의 사람들을 제거해나가면 될 듯 하다. 파이썬에서 원형을 따로 구현하기 보다는 해당 길이보다 차례가 커지면 차례를 조정해주면 될 듯 하다.그런데 생각해야 하는 것은 사람 한 명을 제거할 때 마다 인덱스로 따지면 두 칸을 이동해야 된다는 것이다. 예를 들어 문제 예시와 같이 7명의 사람과 제거해야 하는 차례가 3인 경우를 생각해 본다면 인덱스에 3을 더할 때는 ..

https://www.acmicpc.net/problem/10431문제 학생들을 줄 세우면서 학생들이 총 몇 번 뒤로 물러나는지 구하는 문제이다.학생들을 줄 세우는 방법은 주어진 순서대로 오름차순으로 세우는데 학생이 앞이나 중간에 서게되면 그 뒤 사람들은 모두 한 걸음씩 뒤로 물러난다. 풀이 각 학생이 줄을 설 때 경우의 수는 크게 두 가지로 나뉜다. 해당 차례의 학생이 지금까지 나온 학생들 중 가장 커서 맨 뒤에 서게 되는 경우와 그 외 경우이다. 전자의 경우 뒤로 움직여야 하는 학생이 없지만, 후자의 경우 해당 차례의 학생보다 큰 학생들은 모두 뒤로 한 걸음 물러서야 한다.따라서 학생들이 움직이는 횟수는 해당 차례의 학생보다 큰 학생의 수를 확인하면 간단하게 알 수 있다. 큰 학생의 수를 확인하는 것..

https://www.acmicpc.net/problem/15312문제 알파벳 대문자로 주어지는 이름을 가지고 이름 궁합을 보고 그 결과를 출력하는 문제이다.이름 궁합은 각 글자의 획수를 번갈아가며 나열하고, 양 옆 획수를 더하고 일의 자리만 남기는 것을 반복하여 두 자리만 남았을 때 멈춘다. 남은 두 자리가 궁합 결과이다. 풀이 힌트에 있는 알파벳 획수에 맞추어 이름을 획수로 바꿔주고, 번갈아가며 나열해준다. 그 후 양 옆칸을 더하고 10 으로 나눠서 나머지를 남겨놓는다.알파벳 획수에 맞추어 이름을 바꿔줄 때는 리스트나 딕셔너리를 활용하면 편할 듯 하다. 아래 코드는 딕셔너리를 사용하였다.두 자리 남을 때 까지 획수로 만들어진 숫자들을 양 옆으로 더하고 나머지를 구하며 반복한다. 어차피 문제에서 이름의..

https://www.acmicpc.net/problem/28064문제 주어진 단어들을 앞뒤로 연결할 수 있는 모든 경우의 수를 확인하는 문제이다. 풀이 주어진 단어들을 나열하고, 앞과 뒤를 잘라가면서 비교하고, 같을 때 카운트하면 된다.단 두 단어를 비교하면서 앞과 뒤를 비교해도, 뒤와 앞을 비교해도 일치할 때 2 개로 세는 것이 아니라 1 개로 센다.간단하게 이중 for 문과 슬라이싱을 사용해서 앞과 뒤를 자르고 비교하면 된다. 코드 test = int(input())word = []cnt = 0for i in range(test): word.append(input())for i in range(test): for j in range(i, test): if i == j: ..