본문 바로가기

Algoritm

 (20)
[DP] 개념 정리 ※이것이 취업을 위한 코딩테스트다(파이썬) (저자: 나동빈) 책을 요약/정리한 내용입니다※ 다이나믹 프로그래밍 = 동적 계획법 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법 사용 예시 : 피보나치 수열 기본적인 구현방식 : 점화식 + 재귀 기본 방식의 문제점 : f(n)에서 n이 커지면 커질수록 수행 시간이 기하 급수적으로 늘어남. O(2^n) 분할정복과의 차이점 DP는 문제들이 서로 영향을 미치고 있다는 점이 다름. (한 번 해결했던 문제를 다시금 해결함) 따라서, 이미 해결된 부분 문제에 대한 답을 저장해두는 과정이 필요함. 재귀보다 반복문을 사용하는 것이 DP의 성능이 더 좋다 (오버헤드 줄일 수 있음) 완전 탐색 알고리즘으로 접근했을 때 시간이 오래걸리면 DP를 적..
[JAVA] Window 10 java 코딩 환경 구축 https://danmilife.tistory.com/7 [Java/Windows11] 이클립스 설치하기 1. JDK 버전 확인 cmd > java -version java -version 만약 설치가 되어 있지 않으면 JDK를 먼저 설치하고 이클립스를 설치하면 됩니다. JDK 설치, 환경변수 설정 [Java/Windows 11] JDK 1.8 설치, 환경변수 설정 1. JDK danmilife.tistory.com
[Python] 미로 찾기 내가 생각한 이 문제의 포인트 최단경로를 구하는 알고리즘 리스트 값 자체를 이동한 칸의 개수로 update 칸의 값이 '1'인 경우에만 count 하는 조건문 달아주기 (칸의 값을 update하는 과정이 포함되어 있어서 충돌을 방지하기 위함)
[DFS&BFS] 개념 정리 ** 본문의 내용은 '이것이 취업을 위한 코딩테스트다 with 파이썬 (나동빈)' 을 읽고 정리한 내용입니다 ** DFS 표현방법 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 마치 표처럼! 연결되어 있지않은 노드끼리는 무한의 값(99999999)을 가지고 있다고 작성함 모든 관계를 저장하므로, 노드 개수가 많을수록 메모리 낭비 인접 리스트 : 리스트로 그래프의 연결관계를 표현하는 방식 각 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장 연결된 정보만 저장하기 때문에 메모리 효율성 높음. 연결된 정보를 하나씩 확인 → 특정 두 노드가 연결되어있는지에 대한 정보를 얻는 속도가 느림 특징 like stack 구현시, 재귀 방법 이용 ( 재귀 함수는 내부적으로 스택 자료구조와 동일 ) ..
[Python]게임 개발 ** 내가 생각하는 이 문제의 point ** 맵 입력받기 이중리스트 이용 바라보는 방향 바꾸기 (왼쪽 회전) 기존에 바라보던 방향이 0(북쪽) 이었다면, 왼쪽 회전하면 3(서쪽)이 되고, 나머지 방향들은 -1만 해주면 됌 앞으로 이동 바라보는 방향 d를 dx, dy의 index라고 생각하고 dx,dy 값 설정하기 '한 칸 이동'을 리스트 값을 이용하여 표현하기 방문한 곳 확인하기 방문한 곳과 바다가 있는 곳을 따로 체크하기 네 방향 모두 갈 수 없는 경우 확인 몇 번 돌았는지 체크해서, 4번 돌았다면 네 방향 모두 갈 수 없는 경우로 취급 그리고 자꾸 입력받는 코드 까먹음.. map(int,input().split())....
[Python] 왕실의 나이트 import sys input = sys.stdin.readline now = input() pos = [1,1] pos[1] = int(now[1]) if now[0]=='a': pos[0] = 1 elif now[0]=='b': pos[0] = 2 elif now[0]=='c': pos[0] = 3 elif now[0]=='d': pos[0] = 4 elif now[0]=='e': pos[0] = 5 elif now[0]=='f': pos[0] = 6 elif now[0]=='g': pos[0] = 7 else: pos[0] = 8 # print(pos) new_pos = [0,0] cnt = 0 move= [[-1,-2],[1,-2],[-1,2],[1,2],[-2,-1],[-2,1],[2,-1],[..
[Python] 리스트 행렬 전환 arr = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] arr_T = list(map(list, zip(*arr))) print(arr_T)
Greedy "현재 상황에서 지금 당장 좋은 것만 고르는 방법" 정렬, 최단 경로 문제에서 기본 지식으로 사용됨 Dijkstra Algorithm 또한 greedy algorithm으로 분류됨 문제의 유형이 다양해서 암기로는 풀기 힘들다 -> 많은 유형의 문제를 접해보고 풀어보는 훈련 필요 "문제풀이를 위한 최소한의 아이디어를 떠올리고, 이것이 정당한지 검토하기"

티스토리툴바