All-rounder developer

1. 개요DFS 알고리즘을 적용한 문제 유형으로 2차원 배열에 포함된 특정 영역의 최대 개수를 구하는 문제가 많이 출제된다.아래 두 문제를 풀어보며 이러한 문제 유형에 대해 이해하게 되어, 그 내용을 정리해보려고 한다. 이 글에서는 내가 이해한 개념을 자세하게 풀어서 정리하고, 관련 문제의 코드도 함께 살펴 볼 예정이다.  단, 이 글은 DFS 알고리즘에 대해 이해하고 있다는 가정 하에 설명을 진행한다.만약 DFS 알고리즘의 개념이나 원리를 잘 모른다면 아래 글을 참고하기를 추천한다.https://developer-zoyh.tistory.com/17 [알고리즘] DFS(Depth-First Search)와 BFS(Breadth-First Search)0. IntroductionDFS와 BFS를 별도 게시..

오늘의 학습 키워드메모이제이션, 시뮬레이션 오늘의 회고🌱 오늘의 문제피보나치 문제의 변형된 문제이다. 피보나치 문제가 특정 위치 n의 값에 대하여 n-1, n-2 연속된 두 값의 합으로 구해나갔다면, 이 문제는 n-1, n-3과 같이 한 칸을 띄운 두 값의 합으로 구하는 문제이다.이 외의 조건이 크게 달라지는 부분은 없어 기존의 피보나치 구하는 방식으로 구하면 크게 문제될 것이 없다. 🌱 나의 시도입력 값의 최대값이 116으로 크지 않아 복잡한 알고리즘을 사용하기 보다는 짧고 가독성 좋은 코드를 사용하는 것이 좋다는 판단을 했다. 동일한 연산을 반복하지 않으므로 재귀 함수가 불필요하며, 이전 연산 값을 저장해두고 사용할 수 있는 메모이제이션 정도면 충분하다. 현재 단계적으로 문제를 풀기 때문에 시간 ..

정의: 넓게는 알고리즘을 소스 코드로 바꾸는 것을 의미한다. 좁게는 문제에서 제시하는 제약 조건들에 대해 문법 및 라이브러리를 활용하여 꼼꼼하게 풀어내는 것을 의미한다.대표 예시- 완전 탐색: 문제에서 나올 수 있는 모든 경우의 수에 대해 계산하는 문제 유형- 시뮬레이션: 문제를 해결하기 위하여 각 절차를 한 단계씩 순차적으로 해결해나가는 문제 유형주의사항: 입력 조건이 자세하게 명시되며 문제의 길이가 긴 편이다.참고: 파이썬은 C, C++, JAVA에 비해 난이도가 낮은 반면 속도가 느리다는 단점이 있다. 이를 개선하기 위해 코딩 테스트 시 개발 환경에 PyPy를 지원한다면 PyPy를 선택하자. (실행 속도가 더 빠름)

이미지 출처: https://www.scholarhat.com/tutorial/datastructures/complexity-analysis-of-data-structures-and-algorithms 정의: 알고리즘의 성능을 나타내는 척도종류: 시간 복잡도, 공간(메모리) 복잡도* 일반적으로 복잡도라고 하면 시간 복잡도를 의미한다.표기 방법: 빅오 표기법* 빅오(Big-O) 표기법이란, 구현한 알고리즘을 시간 혹은 메모리에 대한 함수로 나타낸 후, 그 함수의 상한만을 고려한 표기방식이다.주의 사항: 소스 코드를 정확히 분석하여 복잡도를 계산하여야 한다. 만약 내부적으로 함수를 호출한다면 내부 함수도 복잡도를 계산해주어야 한다.코딩 테스트 시 제한 기준 (일반적인 상황)- 시간 복잡도: 1초, O(N^3..