백준

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

[python] 백준 - 2178. 미로 탐색

문제 해결 1. BFS 기본 문제. S1 2. 출발점을 1로 만들고 한칸씩 전진하며 1씩 더해준다. - BFS 이용 (1) 4 방향 탐색을 위해 dx, dy 를 만든다 ( 상하좌우). (2) 리스트(여기서는 디큐를 사용함)에 출발점을 넣어준다. (3) 탐색이 언제 끝날지 모르니까 while 문을 사용한다. (4) 리스트에서 pop(0)(여기서는 popleft())을 이용해 하나씩 꺼내준다. ( 0번을 꺼내는 이유는 BFS 기법을 사용해야 하기 때문에) (5) 꺼낸 지점에서 4방향 탐색을 해준다. (6) 탐색한 곳(nx, ny)이 '1' 인 경우 그 칸에 현재 칸(x, y) 숫자의 +1을 해주고, 리스트에 append해준다. (7) (4)번부터 다시 반복한다. 3. 각 숫자가 이동한 칸의 갯수를 나타낸다...

[python] 백준 - 1051. 숫자 정사각형

문제 해결 1. (부르트포스) 완전탐색 문제이다. 2. '가장 큰' 정사각형을 구하라고 했으므로 만들수 있는 최대 크기에서부터 하나씩 줄여나갔다.(시간 효율) 3. 네 꼭지점의 크기가 같을 때 return + break를 걸어주어 바로 탐색을 종료 + 난이도가 적당한 2차원배열 + 완전탐색 문제이다. 소스 코드 def find_squre(s): # 정사각형의 꼭지점의 숫자 크기가 같은 경우를 찾는다. for i in range(n-s+1): for j in range(m-s+1): if numbers[i][j] == numbers[i][j+s-1] == numbers[i+s-1][j] == numbers[i+s-1][j+s-1]: return True return False n, m = map(int, ..