알고리즘146 [Python] 백준 15649 N과 M 🧑💻 [Python] 백준 15649 N과 M Silver 3 - Backtracking 쉽게 itertools의 permutations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(l) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 dfs()를 다시 돈다 그리고 l.pop()을 해야, 리스트에 숫자가 사라지고, 다른 경우의 수를 넣을 수 있다 코드 백트래킹 사용 N, M = map(int, input().split()) l = [] def dfs(): if len(l) == M: print(" ".join(ma.. 2023. 4. 2. [Python] 백준 1213 팰린드롬 만들기 🧑💻 [Python] 백준 1213 팰린드롬 만들기 Silver 3 - Dictionary 딕셔너리에, 각 알파벳과 알파벳의 개수를 넣는다 key는 알파벳 | value에는 알파벳의 개수 알파벳 개수 중 홀수가 2개 이상이면, 팰린드롬을 만들 수 없다 if sum([al % 2 for al in al_dict.values()]) > 1: 홀수 이면 al % 2 를 할 때 1이 나온다 반대로 짝수면 0이다 즉 팰린드롬이 되려면, 모든 알파벳의 개수가 짝수거나, 개수 하나가 홀 수 일 때에 팰린드롬을 만들 수 있다 for key, value in sorted(al_dict.items()): 을 통해서, 알파벳을 정렬한다 코드 flag = True al_dict = {} alp = input() for a .. 2023. 4. 1. [Python] 백준 1915 가장 큰 정사각형 🧑💻 [Python] 백준 1915 가장 큰 정사각형 Gold 2 - Backtracking 행렬을 순회하면서, 1을 찾게되면, 그 1에 대한 모든 경우의 수를 가지고 최소값을 구하는 것이다 예) 찾은 1을 기준으로 1X1 색종이를 덮을 경우 예) 찾은 1을 기준으로 2X2 색종이를 덮을 경우 예) 찾은 1을 기준으로 3X3 색종이를 덮을 경우 예) 찾은 1을 기준으로 4X4 색종이를 덮을 경우 예) 찾은 1을 기준으로 5X5 색종이를 덮을 경우 56번째 줄이 끝나면, 대부분의 1은 0으로 바껴져 있을 것이다 (만약 한 사이즈의 색종이를 5장을 넘기면, 1로 유지가 될 것이다) 코드 matrix = [list(map(int, input().split())) for _ in range(10)] count.. 2023. 3. 31. [Python] 백준 1915 가장 큰 정사각형 🧑💻 [Python] 백준 1915 가장 큰 정사각형 Gold 4 - DP 인덱스가 벗어나지 않는 선에서, 위, 왼쪽, 외쪽 위의 숫자들 중 min 값을 구한 다음에 1을 더해준다 코드 N, M = map(int, input().split()) matrix = [list(map(int, input())) for _ in range(N)] dp_table = [[0] * M for _ in range(N)] for i in range(N): for j in range(M): if matrix[i][j] == 1: dp_table[i][j] = 1 if 0 2023. 3. 30. [Python] 백준 1389 케빈 베이컨의 6단계 법칙 🧑💻 [Python] 백준 1389 케빈 베이컨의 6단계 법칙 Silver 1 - BFS BFS 를 사용하면서 풀었다 각 숫자, 즉 1부터 N까지의 숫자와 친구의 거리를 모두 구해야 한다 for i in range(1, N + 1) 과 for j in range(1, N + 1)인 2중 for문을 통해서 각 친구들 간의 거리를 구한다 코드 from collections import deque def bfs(start, end, link_num): queue = deque() queue.append((start, 0)) visited = [0] * link_num visited[start] = 1 while queue: current, score = queue.popleft() if current == .. 2023. 3. 29. [Python] 백준 2841 외계인의 기타 연주 🧑💻 [Python] 백준 2841 외계인의 기타 연주 Silver 1 - 스택  코드 N, M = map(int, input().split()) stack = [[] for _ in range(7)] count = 0 for _ in range(N): l, p = map(int, input().split()) while stack[l] and stack[l][-1] > p: stack[l].pop() count += 1 if not stack[l] or stack[l][-1] < p: stack[l].append(p) count += 1 print(.. 2023. 3. 25. [Python] 백준 1018 체스판 다시 칠하기 🧑💻 [Python] 백준 1018 체스판 다시 칠하기 Silver 4 - 완전 탐색 코드 N, M = map(int, input().split()) board = [list(input()) for _ in range(N)] def chess(i, j): global result change_1,change_2 = 0, 0 for row in range(8): for column in range(8): if (row + column) % 2 == 0 and board[i + row][j + column] == "B": change_1 += 1 elif (row + column) % 2 == 1 and board[i + row][j + column] == "W": change_1 += 1 if (row .. 2023. 3. 24. [Python] 백준 10844 쉬운 계단 수 🧑💻 [Python] 백준 10844 쉬운 계단 수 Silver 1 - DP 코드 N = int(input()) stairs = [[0] * 10 for _ in range(N)] for i in range(1, 10): stairs[0][i] = 1 for i in range(1, N): for j in range(10): if j == 0: stairs[i][j] = stairs[i-1][j + 1] elif 0 < j < 9: stairs[i][j] = stairs[i-1][j+1] + stairs[i-1][j-1] elif j == 9: stairs[i][j] = stairs[i-1][j-1] print(sum(stairs[N-1]) % 1000000000) 2023. 3. 24. Udemy : 동적 계획법 (DP) Udemy : 동적 계획법 (DP) udemy 알고리즘 코딩 테스트 Dynamic Programming 문제를 쪼개서 작은 문제의 답을 구하고, 그걸로 더 큰 문제의 답을 구하는 것을 반복 분할정복과 비슷한 느낌 배열 또는 딕셔너리를 만들어서, 작은 문제의 답을 넣는다 메모이제이션 (Memoization) 구현 : 재귀 | 저장방식 : 메모이제이션 (Top-down) cache 방식이라고 할 수 있고, 중복연산을 방지한다 직관적이라 코드 가독성이 좋다 재귀함수 호출이 많이 해서 느릴 수 있다 타뷸레이션 (Tabulation) 구현 : 반복 | 저장방식 : 타뷸레이션 (Bottom-up) 테이블을 채워나가는 것 필요 없는 부분 문제까지 전부 구하는 것 시간과 메모리를 좀 더 아낄 수 있다 DP 테이블 채워.. 2023. 3. 23. 이전 1 ··· 7 8 9 10 11 12 13 ··· 17 다음
