💭    Algorithm

어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 첫째 줄에 1,000

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같

백준 BOJ 9663 N-Queen 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N 풀

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 3 그리디 예제 3-1 거스름돈 87p타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 3 그리디 실전문제 3-2 큰 수의 법칙 92p여기서 큰 수의 법칙이란 다양한 수로 이뤄진 배열이 있을 때 주어진 수들을 M번 더해 가장 큰 수를 만드는 법칙단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 3 그리디 실전문제 3-3 숫자 카드 게임 96p여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임단, 게임의 룰을 지키며 뽑아야함숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 3 그리디 실전문제 3-4 1이 될 때까지 99p어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 함단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음N에서

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 3 구현실전문제 4-1 상하좌우 110p여행가 A는 N × N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 × 1 크기의 정사각형으로 나누어져 있다.가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 4 구현실전문제 4-2 시각 113p정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 4 구현실전문제 4-3 왕실의 나이트 114p행복 왕국의 왕실 정원은 체스판과 같은 8 × 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서있다.나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 4 구현실전문제 4-4 게임 개발 118p현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 X 1 크기의 정사각형으로 이뤄진 N X M 크기의 직사각형으로, 각각의 칸은

PPT로 뚝딱뚝딱...ㅋ ![](h

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 5 구현실전문제 5-3 게임 개발 149pN × M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우

교재 : 이것이 코딩 테스트다 with 파이썬 >CHAPTER 5 DFS/BFS >실전문제 5-4 미로 탈출 152p 미로 탈출 문제 N x M 크기의 직사각형 형태의 미로에 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 현재 위치는 (1, 1)이고 미로의 출

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 5 DFS/BFS실전문제 5-3 DFS 142pDFS graph의 노드당 인접 노드가 배열로 주어질 때 방문 순서 프린트 하기DFS스택 사용재귀함수 사용이것이 코딩 테스트다 with 파이썬 - 나동빈 저

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 5 DFS/BFS실전문제 5-3 DFS 147pBFS graph의 노드당 인접 노드가 배열로 주어질 때 방문 순서 프린트 하기BFS큐 사용 ( 단 python의 경우 Queue말고 collections에서 de

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-1 선택 정렬 156p가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복하는 선택 정렬(Selection

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-2 삽입 정렬 161특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이트는 이미 정렬되어 있다고 가정하고 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-3 퀵 정렬 165기준 데이터(피벗,Pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸자가장 대표적인 분할 방식인 호어 분할 사용(Hoare Partition)리스트에

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-4 계수 정렬 171p별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다.제시된 데이터 : 7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2가장 큰 데이

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-2 위에서 아래로 180pN명의 학생의 성적 정보가 주어진다. 형식은 이름 성적 으로 주어지는데 이때 이들의 성적이 낮은 순으로 학생 이름을 출력하는 문제다.첫 번째 줄에 학생의 수 N이 입

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-2 위에서 아래로 178p하나의 수열에는 다양한 수가 존재하며, 이런 큰 수는 크기와 상관 없이 무작위로 주어진다. 이 수를 큰수 부터 작은 수까지 내림차순으로 정렬하면되는 문제다. 즉 수열

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 6 정렬실전문제 6-3 두 배열의 원소 교체 182p동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는모두 자연수이다동빈이는 최대 K 번의 바꿔치기 연산을

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 7 이진 탐색실전문제 7-1 이진 탐색 189주어진 입력값에 대해서 이진탐색 진행해 인덱스를 출력하자숫자의 갯수와 찾아야 할 숫자를 입력받고 다음줄에서 숫자 배열을 입력받는다찾은 곳은 인덱스를 출력하고 없다면

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 7 이진 탐색실전문제 7-2 부품 찾기 197p동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 7 이진 탐색실전문제 7-2 떡볶이 떡 만들기 201p오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.지구를 나타내는 수를 E, 태양을 나타내는 수를 S, 달을 나타내는 수를 M이라고 했을 때,

세준이는 1 \* 1크기의 그림으로 모자이크한 100 \* 100크기의 그림을 가지고 있다. 어느 날 이 모자이크 중 일부 그림이 너무 보기 싫어서 N개의 불투명한 종이로 그림을 가리기 시작했다. 불투명한 종이로 가린다고 항상 그 그림이 안 보이는 것은 아니다. 그 그

온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 작성하시오.첫째 줄에 온라인 저지 회원의 수 N이 주어진다. (1 ≤ N ≤ 100,

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.입력 예시출력 예시급해서

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d

요세푸스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모

상근이는 퀴즈쇼의 PD이다. 이 퀴즈쇼의 참가자는 총 8개 문제를 푼다. 참가자는 각 문제를 풀고, 그 문제를 풀었을 때 얻는 점수는 문제를 풀기 시작한 시간부터 경과한 시간과 난이도로 결정한다. 문제를 풀지 못한 경우에는 0점을 받는다. 참가자의 총 점수는 가장 높은

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 8 다이나믹 프로그래밍실전문제 8-1 피보나치 수열 213p피보나치 수열 구현하기점화식은 제대로 세운 것 같았는데 잘 안되는 것 같아서 결국 책을 참고했다... DP란 이런거구낭 ㅎㅅㅎ 근데 왜... 봐도 잘

재귀함수를 계산할 때 같은 값을 매번 계산해야 하는 상황을 방지하자큰 문제를 작은 문제로 나눌 수 있다.작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.TOP-DOWN 탑다운 방식재귀함수 사용큰 문제를 해결하기 위해 작은 문제를 호출Memoizatio

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 8 다이나믹 프로그래밍실전문제 8-2 1로 만들기 217p정수 X가 주어질때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.1) X가 5로 나누어떨어지면, 5로 나눈다.2) X가 3으로 나누어 떨어지

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 8 다이나믹 프로그래밍실전문제 8-3 개미 전사 220p개미전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 8 다이나믹 프로그래밍실전문제 8-3 개미 전사 220p문제가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 X 2의 덮개, 2 X 1의 덮개, 2 X 2의

교재 : 이것이 코딩 테스트다 with 파이썬CHAPTER 8 다이나믹 프로그래밍실전문제 8-5 효율적인 화폐 구성 226pN가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4

게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다."죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다.게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며

로또의 최고 순위와 최저 순위 문제 로또 6/45(이하 '로또'로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1 순위 당첨 내용 1 6개 번호가 모두 일치 2 5개 번호가 일치 3 4개

한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오.첫째 줄에 x, y, w, h가 주어진다.첫째 줄에 문제의 정답을 출력

N\*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.첫째 줄에 N과 M이 주어진다. N과 M은 50보다

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고,

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다

한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우출발 노드를 설정한다최단 거리 테이블을 초기화한다.방문하지 않은 노드 중 최단거리가 짧은 노드 선택해당 노드 거쳐 다른 노드 가는 것중 최단거리 테이블 갱신구현하기 쉽지만 느리게 동작 O(V^2)가장 가까웠던