문제 NxM 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 있는 부분을 1로 설정한다. 구멍이 뚫린 부분이 서로 붙어 있다면 큰 한 덩어리로 간주한다. 얼음 틀이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하라. 입력 조건 1. 첫 번째 줄에 얼음틀의 세로 길이 N과 가로 길이 M이 주어진다. 2. 두 번째 줄부터 N+1번째 줄까지 얼음 틀의 형태가 주어진다. 출력 조건 1. 한 번에 만들 수 있는 아이스크림의 개수를 출력한다. 내 코드 # 맵 크기 입력받는다. n,m = map(int,input().split()) # 맵 모양 입력받는다. graph = [] for i in range(n): graph.append(list(map(int,input()))) def icy(x,y): if..
DFS와 BFS에 들어가기 전에 DFS, BFS 알고리즘은 코딩 테스트의 대표적인 탐색 문제 유형이다. 이를 제대로 이해하기 위해서는 스택과 큐에 대한 사전지식이 전제되어야 한다. 스택과 큐는 자료구조에서 핵심적인 개념으로, 삽입(Push)과 삭제(Pop)로 구성된다. 이 외에도 수용가능한 크기를 넘어서는 상태에서 데이터가 삽입되는 오버플로, 비어있는 데이터에 삭제연산을 수행하여 발생하는 언더플로 등을 고려해주어야 한다. 스택 박스쌓기로 비유하면 편하다. 가장 최근에 쌓은 박스가 가장 먼저 빠진다. (후입선출) 명령어는 빈 배열에서 삽입 시 append(), 삭제 시 pop()를 사용한다. 리스트의 가장 뒤 쪽에서 데이터를 삽입(순방향)하고, 가장 뒤 쪽에서 데이터를 꺼낸다. 큐 큐는 역방향으로 데이터를..
문제 맵 안에서의 캐릭터 이동을 구현시키는 문제이다. NxM 크기의 맵은 육지 또는 바다로 구성돼 있다. 캐릭터는 동서남북 중 한 곳을 바라본다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 또한 다음 매뉴얼을 따른다. 매뉴얼1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 매뉴얼2. 캐릭터의 바로 왼쪽 방향에서 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 매뉴얼3. 만약 네 방향 모두 이미 가본 칸이거나 바다로 되어 있는 칸인 경우에는, 바라보는 방향을 유지한 채로 ..
문제 나이트는 8x8 좌표 평면으로 이루어진 왕실 정원 안에 있으며, L자 형태로 이동할 수 있다. 정원 밖으로는 이동할 수 없다. 이 때 말하는 L자 형태의 이동은 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동 이처럼 좌표상에서 나이트의 위치가 주어졌을 때 나이트가 이동 가능한 경우의 수를 출력하는 프로그램을 작성하시오. 이때 행 좌표는 1부터 8로, 열 좌표는 a부터 h로 표현한다. 입력 조건 1. 첫째 줄에 8x8 좌표 평면 상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다. 출력 조건 1. 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오. 내 ..
구현? 코딩 테스트에서 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 어떤 문제를 풀던 간에 소스코드를 작성하는 과정은 필수이므로, 지엽적인 개념이라고도 볼 수 있다. 그러나 문제 해결 분야에서의 구현은 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다. 구현을 위해선느 프로그래밍 언어의 문법을 정확히 인지하고 있어야 한다. 또한 문제 속의 조건이나 요구사항을 잘 충족하는지 고려해야 한다. 본 교재에서는 두 가지 유형의 구현 알고리즘을 다루고 있는데, 모든 경우의 수를 전부 계산하는 완전 탐색 알고리즘과, 문제에서 제시한 알고리즘을 한 단계식 차례대로 수행하는 시뮬레이션 알고리즘이다. 주의사항 파이썬 환경에서는 다른 언어들과 달리 정수 길이에 따른 자료형을 고려할..
문제 어떠한 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. 과정1. N에서 1을 뺀다. 과정2. N을 K로 나눈다. 입력 조건 1. 첫째 줄에 N(2
문제 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 아래 게임 룰을 지키며 카드를 뽑는다. 게임 룰 1. 숫자가 쓰인 카드들이 NxM 형태로 놓여 있다. 이 때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 2. 먼저 뽑고자 하는 카드가 포함돼 있는 행을 선택한다. 3. 그 행에 있는 카드 중 숫자가 가장 낮은 카드를 뽑는다. 입력 조건 1. 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1
문제 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속 K번 초과하여 더해질 수 없다. 예시 예를 들어 순서대로 2,4,5,4,6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 입력 조건 1. 첫째 줄에 N (2
국내 알고리즘 교재에서 '탐욕법'으로 소개되는 그리디 알고리즘은 나중에 미칠 영향을 고려하지 않고 당장 좋은 것만 고르는 방법이다. 진정한 상남자식 알고리즘이다. 기본 구조를 암기해야 하는 정렬 알고리즘이나 최단 경로 등과 달리, 비교적 사전 지식으로부터 자유롭다는 특성을 갖고 있다. 바꿔 말하면 그만큼 다양하게 출제될 수 있기 때문에, 많은 유형을 접해보고 공부하는 훈련이 필요하다. 창의성과 아이디어는 덤이다. '가장 좋은 것'이라는 판단을 위해서는 기준이 주어져야 하는데, 그리디 알고리즘 유형의 문제들에서는 '가장 큰 순서대로' 혹은 '가장 작은 순서대로' 등의 기준을 알게 모르게 제시해 준다. 특히 정렬 알고리즘과 짝을 이뤄 출제된다. 예제 3-1 거스름돈 당신은 음식점의 계산을 도와주는 점원이다...
전공 영상처리 과목에서 numpy로 파이썬을 처음 접하였기 때문에, 차마 몰랐던 개념이나 라이브러리 함수들이 보였습니다. 따라서 이 책을 학습하기 전 코딩테스트를 위해 필요한 파이썬 기본 라이브러리나 문법을 한 번 훑으려 합니다. 0. 학습계획 알고리즘 공부에 사용할 교재는 이것이 코딩 테스트다 (나동빈 저)입니다. 줄여서 이코테라고 부르고, 코딩테스트에 입문하는 데에 바이블 격으로 정평이 나있는 책입니다. 금학기 내로 책을 다 뗄 계획에 있으며, 약 4달이 되는 기간 중 6주는 이론과 실전 문제를, 나머지 10주는 유형별 기출문제를 풀어보며 블로그와 깃허브에 아카이빙하려 합니다. 1. 리스트 컴프리헨션 리스트를 초기화하는 방법 중 하나로, 대괄호 안에 조건문과 반복문을 넣는 방식으로 사용한다. 특히 코..
