개발 공부/알고리즘 (6) 썸네일형 리스트형 최소 신장 트리 (MST) - 크루스칼/프림 알고리즘 (ft.백준 1197) 트리인데 모든 정점이 사이클없이 연결된 트리!실생활에서는,여러 도시를 도로, 전력선, 수도관 등으로 연결할 때, 건설 비용이나 유지비를 최소화하는 경로를 찾는 데 활용된다고 한다.꽤나 유용한 알고리즘이다. 보통 아래 두가지 알고리즘을 사용한다. Kruskal 크루스칼 알고리즘 (간선이 적을 때)Prim 프림 알고리즘 (간선이 많을 때) 적다, 많다 기준을 정하기가 애매하긴 한데 두가지 방법으로 모두 백준 풀어보았다. • 다음 간선 선택 기준의 범위: • 크루스칼: 전체 간선 중에서 최소 간선을 선택 (전역적으로 선택) • 프림: 현재 MST와 연결된 간선 중에서 최소 간선을 선택 (동적으로 확장) • 알고리즘의 흐름: • 크루스칼: 간선을 하나씩 추가하면서 사이클 없이 트리를 .. [Python] 백준 9935 문자열 폭발 문제 (스택, 문자열 메서드 join) 백준 9935 문자열 폭발 문제를 파이썬으로 풀어보자 스택을 이용하여 괄호 문제를 풀었다면 쉽게 이해할 수 있는 문제이다.대신 join() 메서드를 알고 있으면 좋다. import sysinput = sys.stdin.readlinestack = []n = input().strip()bomb = input().strip()stack = []for char in n: stack.append(char) if len(stack) >= len(bomb): if ''.join(stack[-len(bomb):]) == bomb: stack = stack[:-len(bomb)]if stack: print(''.join(stack))else: print("FRULA") 배운 점 문자열 .. [Python] 백준 10971 외판원순회2 - 완전탐색, DFS, 시간복잡도 개선 외판원이 원을 둘러싼 뭔가 판인가.. ? 했는데외부 판매원이었다 하하하뭔가 예에에에에전에 번역한 문제를 typical하게 불러서 가끔 용어가 이상한게 있는 것 같다.Traveling Salesman Problem (TSP) 라고 부른다고 함. 보부상 문제라고 하면 좋을 것 같음ㅋㅋㅋㅋㅋ팀원의 말에 의하면 GPT도 가장 어려운 알고리즘 문제중에 하나로 꼽는,,, 그런 문제다. 처음에 문제만 읽고 대충 구조는 짰는데, 첫번째 도시와 마지막 도시 처리하는 부분에서 애를 먹었다.결국 여러 블로그를 참고해서 가장 이해가 잘 가는 코드를 기반으로 수정했다.아직.. 난이도 실버 문제를 혼자 맞추기는 어렵다.그래도 대충 구조 자체는 짤 수 있어서 일주일 만에 엄청난 성장을 했다! 아래 코드로 제출함. 첫번째 코드#.. [Python] 백준 1065번 한수 풀이 백준 1065번 한수 구하기 문제를 파이썬으로 풀어보자 가장 처음 아무것도 검색안하고 타이핑만 친 코드 import sys# X가 한수인지 체크하는 함수def is_hansu(a): a_list = list(map(int, str(a))) for i in a_list: if a_list[i+1]-a_list[i] == a_list[i+2]-a_list[i+1]: continue return 1n = int(sys.stdin.readline())count = 0for j in range(n): if is_hansu(j) == 1: count += 1 내가 놓친 부분 1. 입력한 숫자가 1자리나 2자리수일 때는 무조건 등차수열 > 입력값에 주의하자2. 어차피 등차수열에서.. 시간복잡도 / 공간복잡도 / 빅오표기법(Big-O) 시간 복잡도는 속도, 공간 복잡도는 메모리 사용량을 나타냄✔ 둘은 반비례하는 경향이 있지만, 항상 그런 것은 아님✔ 보통 알고리즘의 성능은 “시간 복잡도”를 더 중요하게 고려✔ 하지만, 메모리 제약이 있는 문제에서는 “공간 복잡도”도 고려 🔹 시간 복잡도(Time Complexity) • 입력 크기(N)에 따라 연산이 얼마나 많이 수행되는지 나타냄 • O(빅오 표기법)으로 표현 (O(N), O(log N), O(N²), etc.) 🔹 공간 복잡도(Space Complexity) • 입력 크기(N)에 따라 메모리를 얼마나 사용하는지 나타냄 • 변수, 리스트, 재귀 호출 등이 영향을 미침 ❓빅오 표기법주로 최악의 경우 시간 복잡도를 나타낸다.아무리 많이 걸려도 최대 이 시간 안에는 끝난다는 것’을 나.. [Python] 백준 9020번 골드바흐의 추측 # 골드바흐의 추측import sysdef is_prime(A): if A 소수를 구하는 문제같은 경우는 코드를 어떻게 짜야하는지 이해하면 어렵지 않고 함수로 만들어볼 수 있다. def is_prime(A):A가 2보다 작으면 소수가 아니니까 False 를 반환한다.(처음에는 A==1이면 False를 반환하라고 작성했었는데, 2보다 작은 수를 제외하는게 더 정확한 표현이다.)그리고 A를 2부터 A까지 차례대로 나눠본다.만약에 나머지가 0이면 False를 반환한다. A보다 작은 수로 나눴을 때 나머지 없이 나눠지면 소수가 아니기 때문.그리고 이외 경우 소수로 True를 반환한다. 테스트 코드 T번 입력할 수 있는 입력 창을 만들고,for문을 통해 골드바흐 파티션을 출력한다. 먼저 짝수를 입력받는다.. 이전 1 다음
