![]()
📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 정렬(Sorting) 연속된 데이터를 기준에 따라서 정렬하기 위한 알고리즘 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 즉, 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하다. 정렬 알고리즘에는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등이 있고, 파이썬에서 제공하는 기본 정렬 라이브러리를 이용할 수도 있다. 아래의 예제는 모두 오름차순 정렬을 수행하고, 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다. 파이썬에서는 리스트의 원소를 뒤집는 메서드를 제공하기 때문에 오름차순 정렬을 수행한 뒤에 그 결과를 뒤집기(Reverse)하여 내림차순 리..
📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N X M 크기의 직사각형 형태의 미로에 갇혀 있다. 처음 위치는 (1, 1)이고, 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하라. 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 입력 조건 첫째 줄에 두 정수 N, M(4 = M: continue # 다음 값이 1이고, 이동 횟수가 크면 작은걸로 수정 if maze[ni][nj] == 1 and board[ni][nj] > step+1: board[ni][..
📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다. 문제 N X M 크기의 얼음 틀 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결된 것으로 간주한다. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 주어진다. (1 = M: continue if board[ni][nj] == '0' and visited[ni][nj] == 0: visited[ni][nj] = 1 check(ni, nj) cnt = 0 for i in range(0, N): for j in range(0, M): # 구멍이 뚫려있고 체크한 적 없으면 if board[i][j] == '0' and ..
📢 '이것이 코딩 테스트다 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
