전체 글

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 설명코니는 영어 단어가 적힌 카드 뭉치 두 개를 선물로 받았습니다. 코니는 다음과 같은 규칙으로 카드에 적힌 단어들을 사용해 원하는 순서의 단어 배열을 만들 수 있는지 알고 싶습니다.원하는 카드 뭉치에서 카드를 순서대로 한 장씩 사용합니다.한 번 사용한 카드는 다시 사용할 수 없습니다.카드를 사용하지 않고 다음 카드로 넘어갈 수 없습니다.기존에 주어진 카드 뭉치의 단어 순서는 바꿀 수 없습니다.예를 들어 첫 번째 카드 뭉치에 순서대로 ["i", "drink", "water"], 두 번째 카드 뭉치에 순서대..

1. 분할 정복(Divide and Conquer)큰 문제를 작은 부분 문제로 분할하고, 각각의 작은 부분 문제를 해결하여 전체 문제의 해답을 구하는 알고리즘문제의 크기가 커서 직접적인 해결이 어려운 경우 유용하다.대표적인 예로, 정렬 알고리즘인 병합 정렬(Merge Sort)과 퀵 정렬(Quick Sort)이 있다. 2. 동작 방식문제를 작은 부분 문제들로 분할한다.분할된 부분 문제들을 각각 재귀적으로 해결한다.부분 문제들의 해답을 결합하여 전체 문제의 해답을 얻는다. 3.  시간 복잡도시간 복잡도는 일반적으로 부분 문제의 개수, 분할된 문제의 크기, 분할과정의 복잡도에 따라 결정된다.대부분의 경우, 분할 정복 알고리즘은 재귀적인 방법으로 문제를 해결하므로, 재귀 호출의 깊이에 따라 시간 복잡도가 결정..

완전 탐색알고리즘에서 사용되는 기법 중 하나로 '모든 가능한 경우의 수를 탐색'하여 '최적의 결과를 찾는 방법'을 의미합니다.💡 미 완전 탐색은 무엇일까?- 모든 경우의 수를 고려하지 더 이상 탐색이 필요 없는 경우 그 루트를 끊어버리는 것을 의미합니다.- 예를 들어서 재귀함수가 함수를 모든 경우의 수를 탐색하다 결과를 찾아서 탐색을 중지하는 경우 루트를 끊는 경우를 자치기(Pruning)라고 합니다. 이를 수행하면 불필요한 탐색을 줄일 수 있습니다.1. 브루트 포스(Brute-Force)난폭한 힘, 폭력 => 무식하지만 확실한 방식을 의미이는 수행하는데 오래걸리는 데다 자원이 많이 소요되지만 이론적으로 가능한 수를 모두 검색하기에 예상된 결과를 얻을 수 있습니다.'모든 경우를 다 탐색'하면서 결과를 ..

1.  이진 탐색이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘입니다. 이진탐색 알고리즘은 리스트 내 데이터가 어느 정도 정렬되어 있어야만 사용 가능하며 데이터가 무작위로 정렬되어 있다면 사용할 수 없습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효과적으로 문제를 해결할 수 있습니다.2.  이진 탐색의 동작 과정이진 탐색은 특정 데이터를 찾기 위해 리스트 내 기준점으로서 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다.  이진 탐색의 동작 순서는 아래와 같습니다. 1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.2️⃣ 중간 ..

플로이드 워셜플로이드 워셜 알고리즘을 쓰는 문제의 경우, 노드의 개수가 500개 이하일 경우가 많다.하지만 노드가 500개라고 해도 500 * 500 * 500 은 1억이 넘어가기 때문에 시간제한이 넉넉하지 않다면 시간초과에 걸릴 수도 있다.1. 플로이드 워셜 알고리즘 개요모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다.플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다.다만 매 단계마다 방문하지 않은 노드 중에 최단 거리를 갖는 노드를 찾는 과정이 필요하지 않다.플로이드 워셜은 2차원 테이블에 최단 거리 정보를 저장한다.플로이드 워셜 알고리즘은 다이나믹 프로그래밍 유형에 속한다.2. 플로이드 워셜 알..