본문 바로가기

Python4

[알고리즘] DFS, BFS 알고리즘 DFS (Depth-First Search)깊이 우선 탐색, 한쪽 방향을 모두 탐색한다.BFS (Breadth-First Search)너비 우선 탐색, 가까운 노드부터 탐색한다 DFS 와 BFS 구현 방법 비교DFS - 스택과 반복문/재귀BFS - 큐둘 다 방문여부를 저장할 visited 리스트가 필요함. DFS 구현 방법스택 자료구조재귀스택&반복문으로 구현하기스택에 넣은것 = 방문한 노드스택에 뺀 것 = 인접노드 더이상 없음 1. 시작 노드를 스택에 넣고, 방문 처리2. 스택 최상단 노드에 아직 방문하지 않은 인접한 노드가 하나라도 있으면, 그 노드를 스택에 넣고 방문 처리방문하지 않은 인접 노드가 없다면, 스택에서 최상단 노드를 꺼냄3. 더이상 2번 과정을 수행할 수 없을 때까지 반복 재귀로 구현하기.. 2024. 7. 12.
[알고리즘] 구현 - 시뮬레이션, 완전탐색 구현 유형풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제 구현 유형 예시알고리즘은 간단한데 코드가 지나칠만큼 길어지는 문제실수 연산을 다루고 특정 소수점 자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제적절한 라이브러리를 찾아서 사용해야 하는 문제 2차원 공간은 행렬의 의미로 사용됨. 시뮬레이션 및 완전탐색 문제에서 2차원 공간에서의 방향벡터가 자주 활용됨. # 문제 1 # 해결import sysinput =sys.stdin.readlinedx=[0,0,-1,1] #행-세로축dy=[-1,1,0,0] #열-가로축move_types=['L','R','U','D']n=int(input().rstrip())plans=input().split()x,y=1,1for plan .. 2024. 7. 2.
[알고리즘] 그리디 알고리즘 그리디 알고리즘현재 상황에서 지금 당장 좋은 것만 고르는 방법그것이 결국 최적의 해가 되는지 정당성 분석이 중요함 # 문제 1 # 해결n을 k로 나눠 n을 작게 만드는게 포인트. 그래야 연산 시간이 적게 걸림. 시간복잡도가 logn 정도로 낮아진다는 점.import sysinput = sys.stdin.readlinen,k=map(int,input().split())cnt=0while True: target=(n//k)*k #target : k의 배수 중 n과 가장 가까운 수 (n보다 작은 수 중, n과 가까운수) cnt+=n-target #n이 target이 될때까지 1을 빼주는 과정을 횟수에 카운트 n=target # 이제 n은 k의 배수가 됨 n=n/.. 2024. 6. 29.
[python] 파이썬 2차원 배열 선언 하기 2차원 배열 선언 하기rows = 10cols = 5arr = [[0 for j in range(cols)] for i in range(rows)] 틀린 방법rows = 10cols = 5arr = [[0] * cols] * rows Python에서는 * 연산자를 이용해 배열을 선언하게 되면, 얕은 복사(shallow copy)가 진행된다.즉, 배열 내의 요소들이 같은 객체를 가리키게 되는 것이다.따라서, 이 방식으로 2차원 배열을 선언하고 요소를 변경하게 되면 다른 요소들의 값도 같이 바뀌는 것이다. https://velog.io/@sjy5386/Python-2%EC%B0%A8%EC%9B%90-%EB%B0%B0%EC%97%B4-%EC%84%A0%EC%96%B8%ED%95%98%EA%B8%B0 [Pyth.. 2024. 6. 19.