공부 및 코딩 일지

백트래킹이란? 문제 설명에 들어가기 전, 해당 문제는 백트래킹을 사용하는 문제이다. 따라서 백트래킹의 개념에 대해 간단히 짚고 넘어가도록 하자. 백트래킹을 간단하게 요약하면, 모든 경우의 수를 살펴가며 Decision Space를 만들고, 가능성이 없는 것들은 탐색을 중지하고 뒤로 돌아가는 방법이다. 간단하게 예시를 통해 백트래킹에 대해 알아보자. 우리는 일상생활에서 휴대폰을 이용해 전화를 걸 때, 전화기 다이얼을 사용한다. 아래의 다이얼을 살펴보면, 숫자 위에 알파벳들이 나열되어 있는 것을 확인할 수 있다. 여기서 알파벳을 이용해 숫자 '25'를 나타내고 싶다고 가정해 보자. '25'를 나타낼 수 있는 모든 알파벳 조합을 나열하면 다음과 같다. [[AJ, AK, AL], [BJ, BK, BL], [CJ..

작년 11월 초부터 코테 스터디를 들어가게 되면서 파이썬으로 코테 문제를 꾸준히 문제를 풀기 시작했다. 실력이 이전보다 늘긴 했지만, 여태까지는 문제를 풀면서 내가 생각했던 내용들을 정리하지 않고 단순히 문제만 푸는 것에 급급했다. 어느 순간부터 더 이상 발전이 없는 느낌을 받았고, 공부 방식을 바꿔야겠다는 생각이 들었다. 따라서 내가 이 문제를 어떠한 방식으로, 어떻게 접근했는지 등의 과정을 글로 정리하면 나중에 비슷한 문제를 풀게 됐을 때 내가 어떠한 부분이 부족했는지 좀 더 쉽게 파악할 수 있고, 스스로 해결 과정을 정리해 나감으로써 한 번 더 내용을 상기시킬 수 있을 것이라는 생각이 들어 이 글을 기점으로 알고리즘 문제 풀이 블로그 작성을 시작하겠다. 문제 설명 & 풀이 https://www.ac..

이 글은 유튜버 '동빈나'의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 강의를 보고 작성한 글이며, 강의 링크는 아래를 참고하면 된다. https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성된다. 탑다운 위에서부터 아래로 내려간다고 하여 하향식 방식이라 부른다. 보텀업 아래에서부터 위로 올라간다 하여 상향식 방식이라..

이 글은 유튜버 '동빈나'의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 강의를 보고 작성한 글이며, 강의 링크는 아래를 참고하면 된다. https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 탐색 탐색(Search)이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다. DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다. DFS와 BFS를 이해하기 위한 자료구조 및 알고리즘에 대해 살펴보도록 하자. 스택 자료구조 📚 스택 자료구조는 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다. ..

이 글은 유튜버 '동빈나'의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 강의를 보고 작성한 글이며, 강의 링크는 아래를 참고하면 된다. https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 구현 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 말한다. 흔히 알고리즘 대회에서 구현 유형의 문제는 풀이는 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 의미한다. 구현 유형의 예시 알고리즘은 간단한데, 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해..

이 글은 유튜버 '동빈나'의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 강의를 보고 작성한 글이며, 강의 링크는 아래를 참고하면 된다. https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC 그리디 알고리즘 (Greedy Algorithm) 그리디 알고리즘(탐욕적인 방법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요하며, 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토하는 과정이 필요하다. 예시 [문제 상황] 루트..