코딩테스트/이론

인프런 김태원 님 강좌를 듣고 정리한 내용입니다. 냅색 문제? 짐 싸기 문제 또는 배낭 문제라고 불리며 범위가 늘어날수록 시간초과의 위험이 있어 DP(동적 계획법)으로 푸는 경우가 많다. 서로 다른 가치를 지닌 보석의 종류가 주어지고 가방에는 담을 수 있는 무게제한이 있을 때 보석을 최대한의 가치로 가방에다 담는 문제로 많이 출제된다. 즉, 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제이다. 강의에서는 두가지 방법으로 냅색문제를 푸는 방법을 제공한다. 1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터 해결한다. 2. 개수가 정해져 있을 때, 종류마다 한 개씩 존재, 유한개면 뒤에서부터 해결한다. 강의에 나온 예제를 두가지 방법으로 각각 풀어보자. 1. 동전교환(최소갯수 구하기..

패스트캠퍼스x야놀자 백엔드 부트캠프 중 [자료구조 및 알고리즘] 김태원 강사님 강좌를 듣고 정리한 내용입니다. 구현 문제란? 작은 의미로는 문제가 제시한 규칙에 따라 개체를 이동시키는 알고리즘을 의미하며, 큰 의미로는 문제가 요구하는 대로 시행되도록 코드를 구현하는 알고리즘이다. 개체이동방법 개체이동방법은 두가지가 있다. 4방향 탐색 8방향 탐색 4방향 탐색 방법 위와 같이 좌표를 가진 x, y 그래프를 코딩테스트에서는 2차원 배열로 표기가 된다. 구현 문제를 풀다보면 해당 좌표에서의 이동이 기본 베이스로 필요할 때가 있다. 우선 4방향 탐색을 알아보자. [r, c]의 상하좌우 이동 시 값의 변화 [2, 1] - 기본값 [1, 1] - 상 [3, 1] - 하 [2, 0] - 좌 [2, 2] - 우 [r,..

Do it! 알고리즘 코딩 테스트 자바 편 인프런 강좌를 기준으로 작성하였습니다. 알고리즘에서 시간복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측합니다. 시간 복잡도 정의하기 실제 시간 복잡도를 정의하는 유형은 3가지입니다. 빅-오메가 : 최선일 때(best case)의 연산 횟수 빅-세타 : 보통일 때(average case)의 연산 횟수 빅-오 : 최악일 때(worst case)의 연산 횟수 0~99 사이의 무작위값을 찾아 출력하는 코드입니다. 빅-오메가의 경우 최선의 때 이므로 무작위값이 1일 경우이므로 시간 복잡도는 1입니다. 빅-세타의 경우 평균이므로 2/N 번, 빅-오는 최악의 경우인 99가 나올 때이므로 시간..