Algorithm Study
-
[백준] 1157 단어 공부Algorithm Study/Python 2024. 11. 13. 23:44
https://www.acmicpc.net/problem/1157풀이이번 문제는 어려운 문제는 아니지만 재밌는 방법으로 풀어봤다.먼저 나온 1~9까지의 숫자, 알파벳의 갯수를 세아리는 가장 큰 방법은 list나 dictionary를 활용하여 세아리는 것이다.해당 index를 값으로 value를 갯수로 표시하면 쉽게 구현할 수 있다. N = input()A = N.upper()a = list(A)#print(a) # a = ['ZZA']x = [] # 처음 등장한 값인지 판별for i in a: if i not in x: # x= [Z A] x.append(i)duple = []for i in x: #[Z] k = a.count(i) #a = ['ZZA'] Z..
-
[백준] 16165번 걸그룹 마스터 준석이Algorithm Study/Python 2024. 11. 11. 23:03
https://www.acmicpc.net/problem/16165풀이이번에도 dictionary 연습을 위한 문제이다.먼저 걸그룹의 수 N, 맞혀야할 문제의 수 M을 입력 받은 다음걸그룹, 걸그룹의 멤버 이름을 입력받아 저장한다. 그 뒤 걸그룹 또는 멤버의 이름을 받아 필요한 내용을 출력하는 문제다. N, M = map(int, input().split())girls = dict()먼저 N, M을 입력받고 걸그룹을 저장하기 위한 dictionary를 생성한다. for _ in range(N): temp = input() girls[temp] = [] K = int(input()) for _ in range(K): girls[temp].append(input()) ..
-
[백준] 7785번 회사에 있는 사람Algorithm Study/Python 2024. 11. 10. 23:41
https://www.acmicpc.net/problem/7785 문제설명위 문제는 들어온 사람과 나온 사람을 체크하는 단순한 문제이다.단순하게 LIST에 추가하여 LEAVE가 나오면 제외하는 방식으로 풀어도 되지만입력의 숫자가 10^6으로 많다는 것을 고려해야한다.만약 모든 입력이 enter인 경우에 1+2+...+10^6-1번의 연산이 필요하다.즉, 리스트로 구현하는 경우 시간 제한에 걸리게 된다.탐색시간을 줄일 수 있는 방법인 set이나 dictionary를 통해 구현하면 탐색 시간은 항상 1 데이터의 갯수를 10^6으로 가정했을 때 충분히 시간 내에 구할 수 있다. 풀이n = int(input())names = dict()for i in range(n): data = input().split..
-
[백준] 10431번 줄세우기Algorithm Study/Python 2024. 7. 17. 16:17
https://www.acmicpc.net/problem/10431 풀이이 문제는 오름차순으로 insertion sort를 물어보는 문제와 동일하다. 새로 입력받은 숫자를 기존 리스트의 맨 끝 idx부터 비교하여입력받은 숫자보다 큰 경우 idx를 1칸씩 당겨가면서 비교한다.그리고 입력받은 숫자보다 작은 숫자가 나오면 그 뒤에 새로 입력받은 숫자를 삽입한다.이 경우 기존 숫자들은 1칸씩 밀리게 되기 때문에 이 때 이동이 발생하는 회수를 묻는 문제이다.문제의 테스트 케이스는 최대 1000개 입력 받는 숫자는 20이기 때문에 20*20*1000으로 400000정도 연산이 수행되기 때문에 위 방법으로 풀어도 요구 시간인 1초안에 풀 수 있게된다. data = list(map(int, input().split(..
-
[백준] 1009번 설탕 배달Algorithm Study/Python 2024. 7. 11. 23:51
https://www.acmicpc.net/problem/1009 풀이이 문제를 파이썬으로 풀 때는 직접 a**b 를 구한 다음 % 10을 해서 푸는 간단한 방법도 있지만파이썬 함수인 pow(A, B, 10) 을 하게되면 바로 (a^b)%10의 결과물을 얻을 수 있게 된다.%의 결과가 0인 경우만 10번 컴퓨터가 수행하는 것으로 출력을 변경해주면 간단하게 풀 수 있다.n = int(input())for i in range(n): a, b = map(int, input().split()) temp = pow(a,b,10) if temp == 0: print(10) else: print(temp)하지만 이 방법이 아닌 다른 방법으로 푸는 것이 이 문제..
-
[백준] 2839번 설탕 배달Algorithm Study/Python 2024. 7. 1. 23:23
https://www.acmicpc.net/problem/2839 풀이이번 문제는 copliot을 활용하여 문제를 풀어봤다.단순한 문제라면 질문을 잘하면 코드를 만들 수 있을 것 같았다.결과는 생각보다 놀랍게 2번의 질문 만으로 완성된 코드를 만들어냈다. 입력에 대한 부분은 일부 수정이 필요했지만 결과물을 잘 만들어서 생각보다 놀라웠다.먼저 copliot에게 질문을 하기 위해서는 이 문제가 원하는 요구사항을 이해해야한다.위 문제에서는 3과 5를 이용하여 입력받은 숫자를 만들 수 있는지 필요하고 그 숫자를 만들기 위해서는 3과 5를 최소로 사용한 값이 필요하다. 또 만들 수 없는 경우에는 -1을 출력하게 하였다. 그래서 위 조건으로 아래처럼 코드를 생성하였다.내가 입력 받은 숫자 N이 3과 5의 합으로..
-
[백준] 1940번 주몽Algorithm Study/Python 2024. 3. 22. 19:12
https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 풀이 2개의 숫자를 더해 특정 숫자 M이 나오는지 확인하는 문제이다. N은 최대 15000이고 모든 경우의 수를 구하게 되면 15000 * 15000 / 2 정도가 나오기 때문에 시간 초과가 발생하게된다. 즉 더욱 단순하게 풀 수 있어야 하는데 이런 경우에는 투 포인터를 이용하여 양쪽에서 검사하면 쉽게 풀 수 있다. 입력 받은 숫자를 정렬한 뒤 양쪽에서 확인하면 현재 숫자..