본문 바로가기

algorithm6

[알고리즘] 자물쇠와 열쇠 (Brute force-LV3) 📘 알고리즘 노트 문제를 풀기위해 구현해야되는 기능 정리 필요한 기능 ✨ 2차원 리스트를 회전하는 기능 ✨ 자물쇠의 요소가 1로만 채워져 있는지 확인하는 기능 ✨ 자물쇠 배열확장 후 중앙부분에 기존의 자물쇠 넣기 문제 설명 주어진 조건으로 자물쇠를 풀수 있는지 없는지 확인하는 문제 자물쇠 N X N 그리고열쇠 M X M 는 2차원 행렬 조건 열쇠는 회전과 이동이 가능 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답 제한사항 key = (3 MxM # 열쇠는 회전과 이동 가능 # 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채워야 정답 def rotate_a_matrix_by_90_degree(a): n = len(a) # 행 길이 m = len(a[0]) # 열 길이 result = [[.. 2023. 3. 21.

[알고리즘] 최대점수구하기 (DFS-재귀) 목적: DFS 알고리즘의 재귀적 특성을 이해하기 위해서 문제 설명(요약): N개의 문제에 대한 각 점수와 각 문제를 풀기 위한 시간이 주어졌을 때, 정해진 M시간 내 에서의 최대 점수를 찾는문제 해결전략: 노드를 탐색하며(L++) 주어진 입력(점수,시간)을 쓴다 안쓴다 (sum++ or sum, time ++ or time) -> 재귀 함수로 구현 재귀함수에 대한 이해: arr = [[점수,시간],[점수,시간],,,,,,[점수,시간]] DFS(L+1,sum+arr[L][0],time+arr[L][1]) # 노드를 사용한다 1번 DFS(L+1,sum,time) # 노드를 사용하지 않는다 2번 1번 함수를 호출 했을 때 -> 만약에 시간이 초과되면 return 후 돌아와서 2번함수 호출 (stac.. 2023. 3. 18.

[알고리즘] 적록색약 (BFS-GoldⅤ) 목적: BFS 알고리즘의 Queue 자료구조를 이해하기 위해서 문제 설명(요약): N*N 행렬에 R,G,B 문자열(색상) 요소가 들어있다. 상하좌우를 탐색하며 인접하고 같은 색상끼리 구역을 나누어 총 구역의 개수를 구하는 문제 이때 적록색약인 사람은 R,G를 구분하지 못한다. 해결 전략: 1. 적록색약인 Case와 아닌 Case를 나누어 노드를 탐색 (적록색약인 경우는 'G'요소를 'R'로 할당해줌) 2. 주변의 인접한 노드를 탐색하기 위하여 BFS(너비 우선 탐색) 알고리즘을 사용 3. 방문했던 요소는 탐색하지 않는다. 4. BFS가 한번 돌때마다 cnt +=1 Queue자료구조에 대한 이해: queue 안의 모든 요소가 없어질 때 까지 while문을 돌림 상하좌우로 탐색한 모든 요소가 co.. 2023. 3. 18.

[알고리즘] 합분해 (DP-GoldⅤ) 목적 : dp 테이블 손으로 써서 푸는 습관을 들이기 위해서 문제 설명(요약) : 0~N까지의 숫자 중 K개를 택해서 택한 숫자의 합이 N이 되는 경우의 수를 구하기 조건 -> 중복 허용, 숫자 위치만 바꾼 것은 다른 경우로 count 해결 전략: 1. 머리로 풀다가 이차원 dp형태로 풀어야 겠다 싶어 손으로 풀기 시작 2. 1~6까지의 경우의 수를 직접 구해봄 (조합,순열) 3. 피보나치 수열 인줄 알았는데 단순 대각선 합이였음 4. 점화식 세움 5. 끝 직접 그려본 dp 테이블 : 점화식 : dp[i][j] = dp[i-1][j] + dp[i][j-1] 2023. 3. 18.

[알고리즘] 가장 긴 증가하는 바이토닉 부분 수열 (DP-Gold IV) 목적 : 다른사람의 매우 직관적인 풀이를 복습하기 위해서 문제 설명(요약) : 증가 or 감소 , 증가+감소, 감소+증가 의 특징을 가진 바이토닉 수열 중에서 가장 긴 수열을 찾아 길이를 구하면 되는 문제 나의 시도 : 1. 가장 긴 증가 or 감소 수열에서 기울기 부호가 바뀌는 지점의 인덱스를 구해 그 후 가장 긴 반대 수열 길이 더하기 깨달은 것: 가장 긴 증가 수열이 아니더라도 가장 긴 바이토닉 수열이 될 수있다. 반대의 경우도 마찬가지 해결 전략: dp 배열에는 해당 인덱스 값마다 최대 길이가 들어있으므로 해당 시점에서의 증가수열길이 + 감소수열길이 -1 을 해주면 된다. 단 감소 수열은 top-down 방식으로 증가 수열의 길이를 할당 해줘야 겹치는 부분에서 길이 합을 구할 때 제.. 2023. 3. 18.

[알고리즘] 다익스트라 최단경로 알고리즘 목적 : 다이크스트리아 알고리즘의 용도 사용법을 익히기 위해 📘 '이것이 취업을 위한 코딩테스트다' 책을 통해 공부하였습니다. [최단 경로의 Case] 한 정점에서 다른 한 정점까지의 최단 경로 한 정점에서 다른 모든 정점까지의 최단 경로 🥇 모든 정점에서 다른 모든 정점까지의 최단 경로 이 글에서는 다익스트리아 알고리즘으로 해결되는 한 정점에서 다른 모든 정점으로 가는 최단 경로를 구해보겠습니다. 다익스트리아 알고리즘에서는 한 정점에서 다른 모든 정점으로 가는 최단 경로를 결정할 때 그리디한 방법으로 결정합니다. (매 상황에서 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문입니다) 위 그래프를 보시면 시작점을 1로 잡았을 때 연결노드들의 가중치는 1,2,5 인걸 알 수있.. 2023. 3. 18.

이전 1 다음

티스토리툴바