본문 바로가기

Programming Test98

[알고리즘 공부] 음료수 얼려 먹기 음료수 얼려 먹기 유형 : DFS 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ 규칙 NxM 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때, 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 입력 조건 첫 번째 줄에 얼음 틀의 세로 길이 N과 가로 길이 M이 조어진다. (1 2024. 3. 24.
[알고리즘 공부] 게임 개발 게임 개발 유형 : 구현 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ ★ 규칙 첫째 줄에 맴의 세로 크기 N과 가로 크기 M을 공백으로 구분하여 입력한다. (3 2024. 3. 24.
[알고리즘 공부] 왕실의 나이트 왕실의 나이트 유형 : 구현 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ 문제 & 규칙 행복 왕국의 왕실 정원은 체스판과 같은 8x8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 수평으로 두 칸 이동한 뒤에는 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에는 수평으로 한 칸 이동하기 이처럼 8x8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출.. 2024. 3. 22.
[알고리즘 공부] 시각 시 각 유형 : 구현 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ 문제 & 규칙 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다. 00시 02분 55초 01시 27분 45초 조 건 입력 조건 : 첫째줄에 N이 입력된다. (0 2024. 3. 22.
[알고리즘 공부] 1이 될 때까지 1이 될 때까지 유형 : 그리디 알고리즘 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ 규 칙 어떠한 수 N이 1이 될 때까지의 다음 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다. N에서 1을 뺀다. N을 K로 나눈다. 문 제 N과 K가 주어질 때, N이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 조 건 첫째 줄에 N(2 2024. 3. 20.
[알고리즘 공부] 숫자 카드 게임 숫자 카드 게임 유형 : 그리디 알고리즘 출처 : 이것이 취업을 위한 코딩 테스트다. with Python 프로그램 언어 : Python 난이도 : ★ 규 칙 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다. 그 다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 한다. 문 제 카드들이 NxM 형태로 놓여 있을 대, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오. 조 건 첫째 줄에 숫자 카드들이 놓인 .. 2024. 3. 20.
[알고리즘 공부] 그래프 알고리즘 그래프 알고리즘 오늘은 그래프 알고리즘에 대해 알아보도록 하겠습니다 (이번에는 간단히 이론만 하고 다음부터는 문제풀이 위주로 글을 작성하도록 하겠습니다). 이전 DFS/BFS와 최단 경로에서 배운 내용은 그래프 알고리즘의 유형으로 볼 수 있습니다. 이외에도 그래프 알고리즘은 다양한 유형이 있지만 코딩 테스트에서 출제 비중이 낮다고 하네요! 하지만 꼭 제대로 알고 넘어가야하는 알고리즘이라고 합니다. 이번에도 에 따라서 앞서 배운 내용들을 기반으로 하는 데, 크루스칼 알고리즘(Kruskal Algorithms)은 그리디 알고리즘으로 분류디고 위상 정렬 알고리즘(Topology Algorithms)은 앞서 배운 큐 자료 구조 혹은 스택 자료 구조를 활용해야 구현할 수 있습니다. 그럼 그래프 알고리즘에 대해서 .. 2024. 3. 20.
[알고리즘 공부] 최단 경로 최단 경로 (Shortest Path) 이번 말씀드릴 알고리즘은 '최단 경로'에 대해서 알아보도록 하겠습니다. 최단 경로는 말 그대로 가장 짧은 경로를 찾는 알고리즘입니다. 그리고 위 알고리즘은 다음과 같은 상황에 주로 사용됩니다. 예시 한 지점에서 다른 특정 지점가지의 최단 경로를 구해야 하는 경우 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 최단 경로 문제는 보통 그래프로 표현하는데 각 지점은 그래프에서 '노드'로 표현되고 지점간 연결된 도로는 그래프에서 '간선'으로 표현됩니다. 또한 실제 코딩 테스트에서 최단 경로를 모두 출력하는 문제보다는 단순히 최단 거리를 출력하도록 요구하는 문제가 많이 출제된다고 알려져 있습니다. 오늘도 참고서인 에 따라서 최단 거리 알고리즘의 종류.. 2024. 3. 15.
[알고리즘 공부] 다이나믹 프로그램 다이나믹 프로그래밍 (Dynamic Programming) 이번에는 다이나믹 프로그래밍에 대해서 알아보도록 하겠습니다. 최적의 해를 구하기에 시간이 매우 필요하거나 메모리 공간이 매우 많이 필요한 문제 등이 컴퓨터로 해결하기 어려운 문제입니다. 연산 속도의 한계와 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시키 때문입니다. 따라서 연산 속도 및 메모리를 최대한 활용할 수 있도록 알고리즘을 작성해야 하는 데, 메모리 공간을 약간 더 사용하면서 연산 속도를 비약적으로 증가 시킬 때, 사용하는 방식이 다이나믹 프로그래밍입니다. 이번 글에서는 다이나믹 프로그래밍의 고전적인 예제 중 하나인 '피보나치 수열'을 계산하는 코드를 통해서 살펴보도록 하겠습니다. 먼저, 피보나치 수열.. 2024. 3. 14.
[알고리즘 공부] 이진 탐색 이진 탐색 (Binary Search) 이번에도 내용을 바탕으로 "이진 탐색" 알고리즘에 대해서 알아보도록 하겠습니다. 먼저 이진 탐색은 정렬된 배열에서 특정 요소의 위치를 효율적으로 찾는 검색 알고리즘입니다. 기본 원리는 대상 값을 중앙 값과 비교하여 탐색 범위를 반으로 줄여나가는 것입니다. 일단은 이진 탐색을 본격적으로 알기 이전에 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 순차 탐색(Sequential Search)과 코드를 비교하면서 살펴보도록 하겠습니다. 순차 탐색은 말 그대로 순차로 데이터를 탐색한다는 의미입니다. 리스트 안에 데이터를 하나씩 방문하면서 특정한 문자열과 같은지 검사하므로 구현에 있어서도 비교적 쉬운 편입니다. 순차 탐색에 대한 간단.. 2024. 3. 14.
반응형

티스토리툴바