Algorithm

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 탐색 알고리즘 DFS / BFS DFS(Depth First Search, 깊이 우선 탐색) 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 DFS 동작 과정 (스택 자료구조) 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2-1. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문 처리를 한다. "방문 처리"는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것 2-2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. DFS의 기능을 생각하면 순서와 상관없이 처리해..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 자료구조 기초 자료 구조(Data Structure): 데이터를 표현하고 관리하고 처리하기 위한 구조 기본 자료구조인 스택과 큐는 다음으로 구성된다. 삽입(Push): 데이터를 삽입한다. 삭제(Pop): 데이터를 삭제한다. 오버플로(Overflow): 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생 언더플로(Underflow): 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생한다. 스택(Stack) 선입후출(First In Last Out) 구조 또는 후입선출(Last In First Out) 구조 파이썬에서 스택을 이용할 때는 ..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어있는 공간에는 갈 수 없다. 캐릭터의 움직임은 다음 매뉴얼을 따른다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 2-1. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 2-2. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3. 네 방향 모두 이미 가본 ..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 8 X 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하라 이때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다. 나이트는 특정한 위치에서 2가지 경우로 이동할 수 있다. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 나이트는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 입력 조건 첫째 줄에 8x8 좌표 평면 상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 구현(Implementation) 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행 구현 시 고려해야 할 메모리 제약사항 변수의 표현 범위 int 자료형의 크기는 4바이트, long long 자료형은 8바이트이다. 더 큰 변수를 담기 위해 자바의 경우 BigInteger를 표준 라이브러리로 지원하지만, C++의 경우 표준 라이브러리에도 포함되어 있지 않다. 검색과 외부 라이브러리 사용이 가능한 환경인 경우 직접 작성하거나 가져와 사용하지만, 대체로 long long에서 다룰 수 있는 수보다..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하라 입력 조건 첫째 줄에 N(2

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 숫자가 쓰인 카드들이 N X M 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한 후 가장 숫자가 낮은 카드를 뽑는다. 입력 조건 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 각각 자연수로 주어진다. (1

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력한다. 입력 조건 첫째 줄에 N(2

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 그리디(Greedy) 알고리즘 (탐욕법) 현재 상황에서 지금 당장 좋은 것만 고르는 방법 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 알게 모르게 제시해 준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 그리디 알고리즘 문제는 주로 정렬 알고리즘과 짝을 이뤄 출제된다. [ 예제: 거스름돈 ] 거슬러 줄 수 있는 최소 동전의 수 # 거슬러 줘야 할 돈 N N = int(input()) # 동전 갯수 ans =..

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 복잡도 복잡도(Complexity): 알고리즘의 성능을 나타내는 척도 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도(Time Complexity) 알고리즘을 위해 필요한 연산의 횟수 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 공간 복잡도(Space Complexity) 알고리즘을 위해 필요한 메모리의 양 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 시간 복잡도 (Time Complexity) 시간 복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. 빅오 표기법은 간단하게 가장 빠르게 증가하는 항만 고려하는 표기법이다...