공부 기록 블로그

1. DFS/BFS: 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 삽입(Push)과 삭제(Pop) 함수로 구성 오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생스택선입후출(First In Last Out) 구조 or 후입선출(Last In First Out)stack = []# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()stack.append(5)stack.a..

1. 게임 개발난이도 중 | 풀이 시간 40분 | 시간제한 1초 | 메모리 제한 128MB 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 * 1 크기의 정사각형으로 이뤄진 N * M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다.현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.캐릭터의 바로..

1. 왕실의 나이트난이도 하 | 플이 시간 20분 | 시간제한 1초 | 메모리 제한 128MB 행복 왕국의 왕실 정원은 체스판과 같은 8 * 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다. 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기이처럼 8 * 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 ..

1. 아이디어를 코드로 바꾸는 구현: 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 구현 시 고려해야 할 메모리 제약 사항1. C/C++에서 변수의 표현 범위: 전통적으로 정수형을 표현할 때 int 자료형을 주로 사용 -> 4바이트기본 int 자료형의 표현 범위는 -2,147,483,648 ~ 2,147,438,647 ->  2,147,438,647보다 큰 수를 처리할 수 없다는 의미훨씬 큰 수를 담을 변수를 만들려면 흔히 BigInteger 클래스를 구현하거나 이용 반면 파이썬에서는 직접 자료형을 지정할 필요가 없..

1. 1이 될 때까지난이도 하 | 시간제한 1초 | 메모리 제한 128MB | 기출 2018 E 기업 알고리즘 대회 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.N에서 1을 뺀다.N을 K로 나눈다.예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력 조건첫째 ..

1. 숫자 카드 게임난이도 하 | 시간제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.카드들이..

1. 큰 수의 법칙난이도 하 | 플이 시간 30분 | 시간제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트 '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 ..

1. 당장 좋은 것만 선택하는 그리디: 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘국내 알고리즘 교재에서 단어 그대로 번역하여 '탐욕법'으로 소개된다. 욕심쟁이 알고리즘이라고도 한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'문제의 유형이 매우 다양하기 때문에 많은 유형을 접해보고 문제를 풀어보며 훈련해야 한다. 창의력을 요구한다. 다시 말해 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다. 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. -> 정렬 ..