supergravity

목차 -시작 -문제 1 -문제 2 -문제 3 -문제 4 -백준에서 풀어보면 좋은 문제들 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 코딩테스트 연습 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr 시작 이번 시간에는 기본 graph 알고리즘 지식을 바탕으로 실전 문제를 풀어볼 것입니다. 실전 문제에서는 2차원 행렬이 주어질 때 회전과 방향을 고려하여 해결하는 문제가 대부분입니다. 실전 문제는 프로그래머스와 백준의 문제를 사용하고 있습니다. 문제의 생각 흐름을 보기 전 먼저 해당 사이트에 접속해 문제를 푸는 것을 추천드립니다. 그러면 바로 문제로 들어가 봅시다. 문제 1 : 행렬의 회전 다루기 - 행렬 ..

목차 -시작 -문제 1 : 가장 비효율 적인 코드부터 효율적인 코드까지 -실전 문제 : 카카오 보석 쇼핑 문제 풀기 시작 이번 시간에는 투 포인터 알고리즘에 대해 알아보겠습니다. 투 포인터 알고리즘은 리스트에서 연속된 구간을 처리하는 데 사용합니다. 투 포인터 알고리즘의 경우 예제 보면 쉽게 이해할 수 있습니다. 바로 예제로 들어가 봅시다. 문제 1번 : 가장 비효율 적인 코드부터 효율적인 코드까지 길이가 N이고 자연수로 구성된 리스트 a와 정수 target이 인풋으로 주어집니다. sum(a [i:j+1]) == target인 i , j 중 j-i가 가장 작은 값을 리턴하여라. 리턴 형식은 [i, j]처럼 리스트로 하면 된다. 가장 작은 값이 여러 개 존재한다면 i가 작은 값을 리턴하면 됩니다. (단 N..

목차 -시작 -문제 1: 백준 - 1, 2, 3 더하기 -문제 2: 백준 - 정수 삼각형 -문제 3: 백준 - 스티커 -문제 4: 백준 - 평범한 배낭 -문제 5: 최장 공통부분 문자열

목차 -시작 -플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) -다익스트라 알고리즘(Dijkstra algorithm) -벨먼-포드 알고리즘(Bellman-Ford algorithm) -문제 시작 최단 경로 알고리즘은 graph가 주어 질 때 최단 경로를 찾는 방법입니다. graph는 node와 edge로 구성된 집합입니다. 만약 위의 문장이 생소하다면 여기를 클릭해 주세요. 클릭 이전에 배운 BFS 또한 최단 거리 알고리즘이라 할 수 있습니다. BFS는 weight가 없는(edge의 거리가 모두 1인) graph가 주어질 때 시작 node에서 모든 노드로 가는 최단 거리를 구하는 알고리즘이었습니다. BFS가 크리스털 클리어하지 않다면 여기를 클릭해 주세요. 클릭 최단 경로 알고리즘..

목차 -시작 -이진 탐색 알고리즘 -이진 탐색 감잡기 -tree 자료구조와 이진 탐색 -시간복잡도 -구현 -bisect 라이브러리 -정리 시작 binary search algorithm에 대해서 알아봅시다. binary search algorithm은 한국어로 이진 탐색 알고리즘이라고 불리고 있습니다. 이번 글에서 이진 탐색 알고리즘이라고 부르겠습니다. 이진 탐색은 탐색 방법의 한 종류입니다. 이진 탐색은 정렬된 리스트가 있을 때 target과 같은 값이 리스트에 있는지 찾는 탐색 방법입니다. 이진 탐색은 이름을 보면 어떤 알고리즘 인지 대략적으로 이해할 수 있습니다. 이름의 이진은 두 부분으로 라는 뜻을 가지고 있습니다. 그래서 이진 탐색은 "두 부분으로 나누어 찾는 방법이다"라고 이해할 수 있습니다...

목차 -graph? 어떻게 학습해야 하나 -directed graph, undirected graph -neighbor -graph 구현 -graph에 사용되는 기본적인 알고리즘 2개(bfs, dfs) -문제 graph? 어떻게 학습해야 하나 그래프가 뭘까요? 그래프는 아래의 그림과 같이 원안에 데이터를 포함하는 노드와. 노드들을 연결하는 엣지로 구성됩니다. 노드와 엣지로 구성된 그래프는 현실 문제를 표현하고 해결하기 참 좋습니다. 그래서 코딩테스트에서는 현실 상활을 응용한 문제들이 출제되고 있습니다. 현실 문제를 그래프로 표현하는 방법은 node를 현실에 존재하는 객체로 표현하고, 엣지를 객체들의 관계로 표현하면 됩니다. 예를 들어 도시의 교통문제를 해결하기 위해 도시와 이들의 관계를 graph로 표현..

목차 -시작 -기본 -lambda 함수 -거꾸로 정렬 -2중 정렬, 다중 정렬 -문제 시작 파이썬 내장함수인 sorted를 잘 활용하면. 정렬관련 문제는 거뜬히 해결할 수 있습니다. sorted는 여러개의 조건을 충족시키는 정렬을 진행할 수 있는데. 이 기능은 간결한 코드로 문제를 해결할 수 있는 실마리를 제공합니다. 그러면 시작해 봅시다. 기본 sorted()는 리스트와 같은 반복가능한 객체를 파라매터로 받고. 이를 정렬된 리스트로 리턴합니다. sorted()는 파라매터로 반복가능한 객체 iterable을 받기때문에. dictionary, set, tuble, string, generator 모두 사용이 가능합니다. a = [1,3,1,2,3,4,56,6,2,8,3,7,6 ] print(sorted(a..

목차 -재귀함수? -간단한 재귀함수 동작 -피보나치 재귀함수 동작 -정리 재귀함수 재귀함수는 함수 안에 함수를 호출하는 함수를 말합니다. 예를 들면. 아래와 같은 코드가 재귀함수입니다. def go_to_zero(n): if n == 0: return 0 print(n) return go_to_zero(n-1) 재귀함수는 자기 자신을 호출하기 때문에 실수하면. 무한히 자기 자신을 호출하게 됩니다. 그래서 탈출 조건이 필수입니다. 위의 코드의 경우 함수의 파라매터가 호출될 때마다 1식 감소하고. 만약 0이 되면 탈출하는 조건을 포함하고 있습니다. 그러면 이 함수가 잘 동작하는지 확인해 봅시다. 인풋을 10을 넣으면 -1씩 감소하면서 함수를 호출하다. 0이 되면 빠져나오는 것을 확인할 수 있습니다. 간단한 ..