[백준/파이썬Python] #1931 회의실 배정: 그리디는 어떤 기준을 세울지 생각하자 🤝

🤝 문제https://www.acmicpc.net/problem/1931한 개의 회의실이 있고, N개의 회의에 대하여 회의실 사용표를 만드려고 함회의 시간이 겹치면 안됨회의의 시작시간과 끝나는 시간이 같을 수도 있음회의의 최대 개수 찾기🧠 접근 방법회의 시간이 짧은 것을 기준으로 해야 최대한 많은 회의를 잡을 수 있을 것 같다.→ 회의의 스케줄링(겹치는 것)까지 고려해야 한다.→ 첫번째 회의만 잘 정하면 된다.→ 가장 처음에 빨리 끝나는 회의가 결국에는 처음에 가장 짧은 회의이다.입력N: 회의의 수~N+1: 회의의 정보(회의 시작시간, 끝나는 시간)출력최대 사용할 수 있는 회의의 최대 개수👩🏻‍💻 코드📑 전체 코드1차import sysN = int(sys.stdin.readline())meet..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 16.
• textsms

[백준/파이썬Python] #10844 쉬운 계단 수 : 점화식이 생각이 안 날 때는 뒤를 잘라보자 ⛰️

⛰️ 문제https://www.acmicpc.net/problem/10844인접한 모든 자리의 차이가 1인 수를 계단 수라고 함N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기0으로 시작하는 수는 계단수가 아님🧠 접근 방법가장 뒤에 오는 수를 기준으로 개수를 찾음입력N: 길이1보다 크거나 같고, 100보다 작거나 같은 자연수출력정답을 1000000000으로 나눈 나머지👩🏻‍💻 코드for i in range(10): if i == 0: continue DP[1][i] = 1길이가 1일 때의 초기값을 설정해줍니다.for i in range(2, N+1): for j in range(10): # 앞에는 1밖에 올 수 없음 if j =..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 15.
• textsms

[백준/파이썬Python] #2098 외판원 순회 : DFS를 이해합시다. 재귀도 🗺️

🗺️ 문제https://www.acmicpc.net/problem/20981~N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있음(길이 없을 수도 있음)외판원이 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 함.한 번 갔던 도시로는 다시 갈 수 없음(출발했던 도시로 마지막에 돌아오는 것은 예외)이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우기각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태(도시 i에서 도시j로 가기 위한 비용)비용은 대칭적이지 않음모든 도시간의 비용은 양의 정수W[i][i]는 항상 0도시 i에서 도시 j로 갈 수 없는 경우 => W[i][j] = 0N과 비용 행..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 15.
• textsms

[백준/파이썬Python] #2253 점프 : 퐁당퐁당 인덱스 머리쓰기 🪨

🪨 문제https://www.acmicpc.net/problem/2253N(순서대로 1, 2, …, N번 돌)개의 돌현재 1번 돌 위, 점프 하면서 N번째 돌로 이동을 하려 함이동은 돌 번호가 증가하는 순서대로만 할 수 있음제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못함.이전에 x칸 점프를 했다면, 다음번에는 x-1칸 점프하거나, x칸 점프하거나, x+1칸 점프를 할 수 있음. 물론 점프를 할 때에는 한 칸 이상씩 해야 함.몇 개의 돌은 크기가 너무 작기 때문에 올라갈 수 없음.위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수 구하기🧠 접근 방법이 문제는 위의 점화식을 사용하기 위해서 DP 테이블을 만드려면 인덱스가 헷갈립니다. 행 번호의 경우..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 15.
• textsms

[백준/파이썬Python] #11049 행렬곱셈순서 : 인덱스를 주의합시다... 🧮

🧮 문제크기가 N*M인 행렬 A와 M*K인 B를 곱할 때 필요한 곱셈 연산의 수는 총 N*M*K번행렬 N개의 크기가 주어졌을 때, 모든 행렬을 곱하는데 필요한 곱셉 연산 횟수의 최솟값을 구하기🧠 접근 방법결국에 최종적으로 만들어지는 두 개의 큰 행렬의 곱셈 연산 횟수를 구합니다.참고 링크: https://youtu.be/8Ni1gaP35i8, https://youtu.be/8Ni1gaP35i8이 문제는 행렬을 배우지 못한 세대인 제게는 볼 때부터 매우 두려운 문제였습니다. 하지만 문제에서 곱셈 연산의 수 공식을 알려주고 있기 때문에 그것만 이용하면 충분히 풀 수 있을 것 같습니다.(지금 생각해보면...) 유튜브 영상을 몇 번 돌려보고 같이 공부하는 팀원에게 설명도 몇 번 해보고, 친구의 도움도 받아서..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 15.
• textsms

[백준/파이썬Python] #9251 LCS : 문제를 부문제로 잘라보기 🛹

🛹 문제https://www.acmicpc.net/problem/9251LCS(Longest Common Subsequence, 최장 공통 부분 수열), 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾기ACAYKP 와 CAPCAK => ACAK(4개)🧠 접근 방법문자열의 가장 마지막을 비교해서 같은 경우/다른 경우를 나누는 부문제로 분할(DP, 다이나믹 프로그래밍)참고 영상: https://youtu.be/EAXDUxVYquY여러 블로그를 참고했지만 다들 DP 테이블에 값을 넣는 법을 주로 적어두어서 대체 DP 테이블의 규칙이 왜 그렇게 되는지 이해가 안돼서 받아들이지를 못했다. 그래서 강의를 찾아보았고 결국에는 최종 문자열을 작은 문자열로 쪼개서 생각한다는 DP적 사고 방식을 통해 나온 점화식으..

• format_list_bulleted 알고리즘/Python
• · 2024. 7. 15.
• textsms