자료구조 & 알고리즘 & cs/CodingTest (67) 썸네일형 리스트형 [python] 3826 - 스타일리시 3826번: 스타일리시 (acmicpc.net) 3826번: 스타일리시 각 테스트 케이스에 대해서, P의 인덴트 스타일을 구해 Q에 적용한 뒤, 각 줄의 인덴트의 양을 공백으로 구분해 출력한다. 만약, 인덴트의 양을 유일하게 결정할 수 없는 줄이 있다면, 그 줄은 -1 www.acmicpc.net 이해가 어려웠던 문제였다. 시간도 굉장히 오래 걸리고 시간초과로 애를 먹었던 문제였다. 일단 접근법은 다음과 같다. 1. RCS의 값을 어떻게 구하는가? 2. 주어진 스타일리시 프로그램의 인덴트 스타일을 다른 프로그램 Q에 어떻게 적용하는가? 3. 인덴트의 양을 유일하게 결정할 수 없는 줄은 어떤 경우인가? 1. 우선, 1번은 이해하는데 까지 굉장히 오래 걸렸다. RCS의 값은 정해져 있지 않았다는 것이 이 문.. [python] 19948 - 음유시인 영재 19948번: 음유시인 영재 (acmicpc.net) 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net 실버 3 문제였는데 문제를 꼼꼼히 읽고 풀지 않아서 중간에 계속 틀렸다. 문제에서 주의할 점은 시의 내용과 제목 모두 출력해야 한다는 점이다. 우선 ascii_lowercase를 사용하여 알파벳 리스트와 횟수 딕셔너리를 생성해주었고 문자열을 돌면서 횟수를 차감하는데 이전 문자열과 같을 경우는 차감하지 않고 넘어가도록 하였다. 대소문자 구별을 해야 되기 때문에 딕셔너리에서 값을 찾을 때는 lower()로 비교하였고.. [python] 4386 - 별자리 만들기 4386번: 별자리 만들기 (acmicpc.net) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소 신장 트리 문제였다. 다른 점이 있다면 간선의 가중치가 직접 주어지는 것이 아니라 좌표가 주어지고 좌표의 거리에 따른 가중치값을 직접 구해야 했다. 별들의 좌표를 배열에 입력받은 후 두 점 사이의 거리 공식을 이용하면 될 것 같았고 모든 점들의 거리를 구해야 하기 때문에 조합을 이용하여 케이스를 구한 후 간선과 가중치를 구해 간선 배열에 넣어주었다. 그리고 나머지 부분은 크루스칼 알고리즘을 이용하여 구하였다.. [python] 9519 - 졸려 9519번: 졸려 (acmicpc.net) 9519번: 졸려 첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다. www.acmicpc.net 문자열 구현 문제였다. 처음 접근 방식은 다음과 같다. 문자열을 원래대로 복원하기만 하면 되기 때문에 바꿔야 할 알파벳 수를 구한 후 문자열을 바꾼다. 처음 주어진 규칙을 반대로 하기만 하면 되기 때문에 while문을 이용하여 횟수만큼 반복한 후 문자열을 출력한다. 그런데 두 번째 예제를 보니 왠지 시간초과에 걸릴 것만 같았다.. 문자열이 모두 같은 알파벳일 경우 횟수에 의미가 없기 때문이다. 그래서 중간에 break도 .. [python] 3107 - IPv6 3107번: IPv6 (acmicpc.net) 3107번: IPv6 첫째 줄에 올바른 IPv6 주소가 주어진다. 이 주소는 최대 39글자이다. 또한, 주소는 숫자 0-9, 알파벳 소문자 a-f, 콜론 :으로만 이루어져 있다. www.acmicpc.net 문제 자체는 간단했다. 주어진 IPv6 주소를 원래의 주소로 복원하면 되는 문제였는데 접근 방식은 다음과 같다. 1. ':'을 기준으로 문자열을 나눈 리스트를 생성한다. 2. 리스트를 돈다 2-1. 원소가 공백이 아니라면 - 원소의 길이가 4가 아닐때 4가 될 때까지 앞자리를 0으로 채운다. - 원소의 길이가 4라면 넘어간다. 2-2. 원소가 공백이라면 - '0000' 을 전체 문자열에서 공백을 지운 크기 만큼 추가한다. - 그리고 cnt로 상태를 체크하.. [python] 2469 - 사다리 타기 2469번: 사다리 타기 (acmicpc.net) 2469번: 사다리 타기 첫 줄에는 참가한 사람의 수 k가 나온다(3 ≤ k ≤ 26). 그 다음 줄에는 가로 막대가 놓일 전체 가로 줄의 수를 나타내는 n이 나온다(3 ≤ n ≤ 1,000). 그리고 세 번째 줄에는 사다리를 타고 난 후 결정 www.acmicpc.net 접근을 잘못했던 문제였다. ?로 주어지는 가로줄을 추측할 때에 ['*', '-']에서 가로줄 크기 만큼 고르는 중복 순열로 접근을 했더니 문제가 굉장히 복잡해졌다. 더욱이 사다리 모양이 헷갈려서.. 결국 구글 검색을 통해 풀이를 찾아보고 말았다. 그랬더니 엄청나게 간단한 풀이가 있었다. 왜 진작 이렇게 생각을 못했을까? ?가 나오는 배열 이전과 이후로 나눠 바로 직전의 문자 배열을 구한.. [python] 2608 - 로마 숫자 2608번: 로마 숫자 (acmicpc.net) 2608번: 로마 숫자 첫째 줄과 둘째 줄에 하나씩 로마 숫자로 표현된 수가 주어진다. 입력된 각 수는 2000 보다 작거나 같고, 두 수의 합은 4000보다 작다. www.acmicpc.net 뭐랄까.. 굉장히 어렵진 않지만 조건들도 많았고 구현하기 싫게 생긴 문제였다. 우선, 딕셔너리에 각 문자 값들을 구분해서 담아준 후 문자를 숫자로 변환하는 함수와 숫자를 문자로 변환하는 함수 두개를 만들어 주었다. 문자를 숫자로 변환하는 과정은 크게 까다롭지 않았으나 숫자를 문자로 변환할 때가 만족스럽지 않은 코드였다. 숫자의 자리수와 값을 토대로 if문을 사용하여 케이스를 나눠주었는데 두 숫자의 합에 대한 값이 4000 이하로 제한되어 있기 때문에 해결은 되었지만.. [python] 7490 - 0 만들기 7490번: 0 만들기 (acmicpc.net) 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net # 7490 0 만들기 from itertools import product import sys input = sys.stdin.readline #아스키 코드 값으로 정렬 하려먼 공백-> + -> - sign=[' ', '+', '-'] for _ in range(int(input())): # 오름차순 리스트 numList = [ i for i in range(1, int(input())+1)] # 부호에 대한 중복 순열 리스트, 각 케이스 별로 0이 되는지를 체크 .. 이전 1 2 3 4 5 ··· 9 다음
