백준

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: ..

https://www.acmicpc.net/problem/18870문제 좌표를 압축하여 나타내는 문제이다.압축된 좌표는 $ X_i > X_j $ 를 만족하는 서로 다른 좌표 $ X_j $ 의 개수와 같아야 한다. 가장 작은 수가 0 이 되고 그 이후로 1 씩 커지는 좌표라고 생각하면 좋을 듯 하다. 풀이 주어진 좌표들을 오름차순으로 정렬하고, 정렬된 수의 인덱스를 처음 주어진 좌표들의 순서에 맞게 출력해주면 된다.단 같은 수는 같은 인덱스를 가져야 하므로 오름차순으로 정렬할 때 중복을 제거해야 한다. 파이썬에서는 set 을 사용하여 간단하게 중복을 제거할 수 있다.좌표들의 순서에 맞게 인덱스를 정렬하면 가장 작은 수가 0 이 되고 그 이후 수들이 커질 때 마다 1 씩 커지게 된다. 즉 좌표가 압축된다. ..

https://www.acmicpc.net/problem/21920문제 주어진 수열에서 주어진 수와 서로소인 수들을 모두 고르고, 그 서로소인 수들의 평균을 구하는 문제이다. 풀이 수열의 길이가 500,000까지 가능하고, 주어지는 수가 1,000,000까지 가능하기 때문에 반복문을 활용하여 단순하게 접근하면 시간 초과가 날 수 있는 문제이다. 따라서 효율적으로 서로소를 구하도록 접근해야 한다.서로소는 공약수가 1 뿐인 두 정수이다. 즉 주어진 수의 약수로 나누어 떨어지는 수가 있다면 그 수는 서로소가 될 수 없다. 또한 더 생각해본다면 약수 중 소수로만 확인해도 서로소인지 아닌지 확인할 수 있다.따라서 주어진 정수의 약수 중 소수를 골라내야 한다. 약수를 먼저 고르는 것 보다 에라토스테네스의 체를 사용..