algorithm

[python] SWEA - 1946. 간단한 압축 풀기/ 1945. 간단한 소인수분해

1. 간단한 압축 풀기 문제 해결 1. 문자열 인덱싱 하기. D2 2. 하나의 변수를 만들고 알파벳과 그 알파벳의 갯수만큼 문자열로 더해준다. 3. 너비가 10이므로 변수를 길이가 10만큼씩 잘라서 출력해준다. 🌧 2번과 3번을 동시에 할 수도 있을 것 같다😶 소스 코드 T = int(input()) for tc in range(1, 1+T): n = int(input()) document = '' for _ in range(n): word, number = input().split() document += word*int(number) print('#{}'.format(tc)) for i in range(0, len(document), 10): print(document[i:i+10]) 출처: SW E..

[python] 백준 - 10799. 쇠막대기

문제 해결 1. 스택을 활용한 문제. S3 2. '(' 가 나오면 막대기의 시작점이라 생각하고 stack 에 쌓는다. 3. ')' 이 나왔을 때 두가지의 경우 (1) 이전에 '(' 가 나온 경우: 쇠막대기가 아니라 레이저 이므로 잘라준다. (2) 이전에 ')' 가 나온 경우: 쇠막대기의 끝 부분 이다. 4. 레이저로 자른경우는 stack 에 쌓여있는 막대기만큼 count를 더해준다. 5. 쇠막대기의 끝부분이 나온경우 막대히 하나만큼 count를 더해준다. 🚗 소스 코드 bars = input() stack = [] cnt = 0 # '('를 막대기의 시작점으로 주고 '()' 이렇게 여는괄호와 닫는괄호가 연속으로 나오면 레이저로 취급한다. for i in range(len(bars)): if bars[i]..

[python] 백준 - 2941. 크로아티아 알파벳

문제 해결 1. 단순 인덱싱 문제?. S5 2. 크로아티아 알파벳을 배열로 만든다. 3. 크로아티아 알파벳은 두글자 혹은 세글자 이므로 (1) 두글자일 때 한번 (2) 세글자일 때 한번 체크 해준다. (3) (1), (2)가 크로아티아 알파벳이 아니라면 한글자만 알파벳으로 체크하고 다음을 진행한다. ⛅ 소스 코드 word = input() croatia = ['c=', 'c-', 'dz=', 'd-', 'lj', 'nj', 's=', 'z='] idx = 0 cnt = 0 while True: if word[idx:idx+2] in croatia: idx += 2 cnt += 1 elif word[idx:idx+3] in croatia: idx += 3 cnt += 1 else: idx += 1 cnt ..

[python] 백준 - 11399. ATM

문제 해결 1. 그리디 알고리즘. S3 2. 단순하게 정렬을 이용해서 문제를 해결했다. 3. 각각의 사람들이 기다리는 시간은 수학적으로 계산을 했다. ⛅ 생각보다 단순하고 쉬운 문제였다. 소스 코드 n = int(input()) people = list(map(int, input().split())) # 오름차순으로 정렬 people.sort() result = 0 # i번 째 사람이 인출 할 경우 i번 부터 i+n까지의 사람들은 *n시간 기다려야 한다. # 그러므로 n을 곱해서 더해준다. for i in range(len(people)): result += people[i] * (len(people) - i) print(result) 출처: BACKJOON ONLINE JUDGE 문제: https://..

[python] 백준 - 11047. 동전 0

문제 해결 1. 그리디 알고리즘. S1 2. 큰 동전부터 순차적으로 for문을 돌리며 (1) 목표값 k 보다 작은 동전이 나왔을 때 그 동전의 값을 뺄 수 있는 만큼 빼준다. ex) 45원이 남았을 때 10원짜리 동전이 나왔다면 계산을 통해 10원을 4번 빼주고 카운트를 4 올려준다. (2) 빼준 값만큼 k값을 줄여가며 동전을 0원으로 만든다. (3) 누적된 cnt 값을 출력해주면 끝 🌞 탐색알고리즘을 해결할 땐 시간을 최적화 하는게 중요한 것 같다. ❓처음 해결방법: 동전값을 찾았을 때 while문으로 동전을 하나씩 빼줬는데 시간 초과가 났다. ❓두번째 해결방법: k값이 0이 됐음에도 불구하고 나머지 for문을 돈다고 생각하여 break문을 추가했다. 이것도 시간 초과. 사실 별로 도움이 안된거 같다...

[python] 백준 - 1697. 숨바꼭질

문제 해결 1. BFS 기본 문제. S1 2. 주어진 범위 100,000까지의 배열을 만든다. 3. BFS를 활용해 현재위치와 다음위치를 배열에 넣고 while문을 돌린다 (1) 각 지점에 도달하기 까지의 최소 시간으로 업데이트 해준다. (2) 이렇게 코드를 짜는 경우 시간초과가 생길 수 있으므로 deque()를 사용하고 (3) 한번도 방문한 적이 없거나, 최소시간으로 방문할 때만 다음 지점으로 나아갈 수 있게 한다. 4. 현재 위치가 목표 지점에 도달하면 break로 while문을 빠져나와 답을 출력한다. 🌞 처음에 범위를 100001까지 잡았더니 인덱스가 마지막이 될 경우에 런타임에러가 발생한다. 그래서 100002로 바꿔줬더니 해결했다. 재귀로 풀어 봤지만 maximum recursion depth..