본문 바로가기
728x90

코딩테스트/이코테23

[CH5 DFS/BFS] 꼭 필요한 자료구조 기초 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 탐색 (Search) "많은 양의 데이터 중에서 원하는 데이터를 찾는 과정" 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루는데, 대표적인 탐색 알고리즘으로 DFS와 BFS가 존재한다 위의 알고리즘들을 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다! 자료구조 (Data Structure) "데이터를 표현하고 관리하고 처리하기 위한 구조" 그중 스택과 큐는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성된다 삽입(Push) : 데이터를 삽입한다 삭제(Pop) : 데이터를 삭제한다 물론 실제로 스택과 큐를 사용할 때는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다 오버플로(Overflo.. 2021. 12. 20.
[CH4 구현] 게임 개발 실전문제3) 게임 개발 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다 캐릭터가 있는 장소는 1X1 크기의 정사각형으로 이뤄진 NXM 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다 캐릭터는 동서남북 중 한 곳을 바라본다 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽을부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다 캐릭터의 움직임을 설정하기 위해 정해 높은 매뉴얼은 아래와 같다 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽.. 2021. 12. 9.
[CH4 구현] 왕실의 나이트 실전문제) 왕실의 나이트 행복 왕국의 왕실 정원은 체스판과 같은 8X8 좌표 평면이다 왕실 정원의 특정한 한 칸에 나이트가 서 있다 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 이처럼 8X8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오 이 때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한.. 2021. 12. 8.
[CH4 구현] 아이디어를 코드를 바꾸는 구현 3 예제 4-2) 시각 정수 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 3중 반복문 사용 이러한 유형은 완전 탐색(Bruce Forcing) 유형으로 분류되기도 한다 완전 탐색 알고리즘은 가능한 경우의 수를 모두 검사해보는 탐색 방법이다 완전 탐색 문제 또한 구현이 중요한 대표적인 문제 유형인데, 일반적으로.. 2021. 12. 7.
[CH4 구현] 아이디어를 코드를 바꾸는 구현 2 예제 4-1) 상하좌우 여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다 이 공간은 1 X 1 크기의 정사각형으로 나누어져 잇다 가장 왼쪽 위 좌표는 (1,1)이며 가장 오른쪽 아래 좌표는 (N, N)에 해당한다 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 잇다 계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D중 하나의 문자가 반복적으로 적혀있다 각 문자의 의미는 다음과 같다 L : 왼쪽으로 한 칸 이동 R : 오른쪽으로 한 칸 이동 U : 위로 한 칸 이동 D : 아래로 한 칸 이동 이 때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다 ex).. 2021. 12. 6.
[이것이 코딩 테스트다 with python] 유튜브 강의 링크 https://youtu.be/Mf0pYO8VAZk [2021 ver] https://youtu.be/m-9pAwq1o3w 모르거나 헷갈리는 거 있으면 이거 참고하셈~~ 2021. 12. 6.
728x90