티끌모아 태산

https://www.acmicpc.net/problem/1296 1296번: 팀 이름 정하기 연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다. 이환 www.acmicpc.net 설명 연두는 프로그래밍 대회에 나갈 팀 이름을 정하려고 한다. 미신을 믿는 연두는 이환이에게 공식을 하나 받아왔고, 이 공식을 이용해 우승할 확률이 가장 높은 팀 이름을 찾으려고 한다. 이환이가 만든 공식은 사용하려면 먼저 다음 4가지 변수의 값을 계산해야 한다. L = 연두의 이름과 팀 이름에서 등장하는 L의 개수 O = 연두의 이름과 팀 이름에서 등장하는 O의 개수 V = 연두의 이름과 팀 이름에..

https://www.acmicpc.net/problem/1834 1834번: 나머지와 몫이 같은 수 N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다. www.acmicpc.net 설명 N으로 나누었을 때 나머지와 몫이 같은 모든 자연수의 합을 구하는 프로그램을 작성하시오. 예를 들어 N=3일 때, 나머지와 몫이 모두 같은 자연수는 4와 8 두 개가 있으므로, 그 합은 12이다. 핵심 아이디어 처음에는 단순히 조건문을 사용해서 N으로 나눈 몫과 나머지가 같은 수를 찾아 합한 값을 출력하면 되는줄 알았다. 하지만 범위를 지정하는 부분에서 헷갈리고 시간 초과가 발..

https://www.acmicpc.net/problem/1357 1357번: 뒤집힌 덧셈 어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만드는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev( www.acmicpc.net 설명 어떤 수 X가 주어졌을 때, X의 모든 자리수가 역순이 된 수를 얻을 수 있다. Rev(X)를 X의 모든 자리수를 역순으로 만드는 함수라고 하자. 예를 들어, X=123일 때, Rev(X) = 321이다. 그리고, X=100일 때, Rev(X) = 1이다. 두 양의 정수 X와 Y가 주어졌을 때, Rev(Rev(X) + Rev(Y))를 구하는 프..

https://www.acmicpc.net/problem/1292 1292번: 쉽게 푸는 문제 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. www.acmicpc.net 설명 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 핵심 아이디어 1 ..

https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 설명 문자열 S가 주어졌을 때, S의 서로 다른 부분 문자열의 개수를 구하는 프로그램을 작성하시오. 부분 문자열은 S에서 연속된 일부분을 말하며, 길이가 1보다 크거나 같아야 한다. 예를 들어, ababc의 부분 문자열은 a, b, a, b, c, ab, ba, ab, bc, aba, bab, abc, abab, babc, ababc가 있고, 서로 다른것의 개수는 12개이다. 핵심 아이디어 문자열의 부분 문자열들을 파악하는게 전부다. 코드 구현 Python impo..

https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 핵심 아이디어 각 행과 열마다 X가 들어있지 않는 행, 열의 개수를 구하고 그중 큰 값을 출력해주면 된다. 위 예에서 X가 없는 행은 3개이고 X가 없는 열은 1개이다. 이 중 큰 값을 출력하면 3이 된다. 코드 구현 Python ''' 각 행과 열마다 X가 안들어 있는 행, 열의 개수를 구하고 그 중 큰 값을 출력하면 된다. ''' n,m = map(int, input().split(..

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 설명 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 핵심 아이디어 주어진 문자의 알파벳 빈도수를 0~25 공간에 저장한다. 즉 카운팅 배열! -> ord(), char(), lower(), upper() 마지막으로 해당 알파벳이 유일한 최다 빈도수인지 확인한 후 결과를 출력한다. 코드 구현 Python s = inpu..

https://www.acmicpc.net/problem/9996 9996번: 한국이 그리울 땐 서버에 접속하지 총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다. 참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다. www.acmicpc.net 핵심 아이디어 별표를 기준으로 별표 앞에 오는 문자열로 시작하고 별표 뒤에 오는 문자열로 끝나야 함. 만약 "a*a"를 패턴으로 할 때, "a"로 시작해서 "a"로 끝나지만 "a"가 두개 존재하고 양 끝에 존재해야 한다는 의미. 그리고 입력받은 s의 길이가 pat 보다 작으면 안된다. 즉, pat = abc*abc, s = abc 이렇게 len(s) < len(p..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 핵심 아이디어 dictionary() -> 만약 리스트에서 탐색을 할 경우 시간복잡도는 O(n). 따라서 index를 탐색할 때, 데이터의 양에 따라 시간초과가 발생할 수 있기 때문에 자료구조별 시간 복잡도를 잘 생각해야 한다. 파이썬에서 딕셔너리는 hash table을 사용한 것으로, 데이터를 읽을 때 시간복잡도가 O(1)이다. 그러므로 인덱스 탐색이나 특정 문자 탐..

https://www.acmicpc.net/problem/1159 1159번: 농구 경기 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작 www.acmicpc.net 핵심 아이디어 Counting 배열 Counter 라이브러리 (파이썬) 처음에 풀 때는 counting 배열로 풀다 chr()을 고려하지못해서 Counter 를 사용하여서 풀었다. 그리고 이 문제를 풀면서 ''.join()함수에 대해서도 알 수 있었다. join 함수 - ''.join(리스트) 매개변수로 들어온 리스트가 ['a', 'b', 'c'] 일 때 문자열을 'abc'로 합쳐서 반환해준다. - '구..