Archive

문제수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.입력첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.출력수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.예제 입력 / 출력5 17 4힌트수빈이가 5 → 10 → 9 → 18 → 17 순..

문제n개의 음이 아닌 정수들이 있습니다.이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다.예를 들어, [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 가지 방법이 있습니다.-1 + 1 + 1 + 1 + 1 = 3+1 - 1 + 1 + 1 + 1 = 3+1 + 1 - 1 + 1 + 1 = 3+1 + 1 + 1 - 1 + 1 = 3+1 + 1 + 1 + 1 - 1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때,숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성하세요. 제한사항숫자의 개수: 2개 이상 20개 이하각 숫자: 1 이상 50 이하 자연수타겟 넘버..

문제정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.X가 3으로 나누어 떨어지면, 3으로 나눈다.X가 2로 나누어 떨어지면, 2로 나눈다.1을 뺀다.정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 입력첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. 출력첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다. 풀이 #1각 숫자 인덱스에 연산 횟수를 저장하여 조회할 수 있도록 하였다. 그러나 이 풀이는 Bottom-up 방식으로, for문을 통해 1부터 n까지 모든 값을 계산하기 때문에 실제로 n의 최소 연산 횟수를 구하는 데 불필요한 값들까지 모두 연산하게 된다. 그리고 파이썬에서 list..

문제NxN 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1x1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다.아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다.아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다.아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같다.더 이상 먹을 수 있는 물고기가 공간에 없다면 아기 상어는 엄마 상어에게..

문제상어 초등학교에는 교실이 하나 있고, 교실은 NxN 크기의 격자로 나타낼 수 있다.교실은 NxN 크기의 격자학생 수는 N^2명학생은 1번부터 N^2번까지 번호가 매겨져 있고, (r,c)는 r행 c열을 의미한다. 교실의 가장 왼쪽 윗 칸은 (1,1)이고 가장 오른쪽 아랫칸은 (N,N)이다선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다.이제 다음과 같은 규칙을 이용해 정해진 순서대로 학생의 자리를 정하려고 한다.한 칸에는 학생 한 명의 자리만 있을 수 있고, |r1 - r2| + |c1 - c2| = 1 을 만족하는 두 칸이 (r1, c1)과 (r2, c2)을 인접하다고 합니다.비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.1을 만족하는 칸..

문제 입력출력로봇 청소기가 작동을 시작한 후 작동을 멈출 때까지 청소하는 칸의 개수를 출력한다.내 풀이로봇 청소기는 N×M 크기의 맵에서 청소를 수행한다.각 칸은 벽(1) 또는 빈 칸(0)으로 구분된다.로봇의 행동 규칙:현재 위치를 청소한다.왼쪽부터 차례대로 4방향을 탐색하며, 청소하지 않은 칸이 있으면 이동한다.4방향 모두 청소가 완료되면 후진을 시도한다.후진이 불가능하면 작동을 멈춘다.DFS(깊이 우선 탐색)를 사용하면, 재귀적으로 청소와 이동을 구현할 수 있다.n, m = map(int, input().split()) # 세로, 가로r, c, d = map(int, input().split())graph = []result = 1for _ in range(n): graph.append(lis..

집합 순서와 중복이 없는 원소들을 갖는 자료구조  상호배타적 집합 : 교집합이 없는 집합 관계그래프 알고리즘에서 많이 활용된다.활용 분야이미지 분할 / 도로 네트워크 구성 / 최소 신장 트리 알고리즘 구현 / 게임 개발 / 클러스터링 작업 앞으로 글의 내용에서 집합을 상호배타적 집합이라 가정한다. 집합의 연산집합의 표현 방법 : 배열을 활용한 트리로 구현집합의 대표적인 연산합치기 (유니온)탐색 (파인드)배열을 활용하여 트리로 집합 표현각 집합 에는 대표 원소가 있어야 한다.집합의 원소 중 집합을 대표하는 역할집합의 형태를 트리로 표현할 것이므로 대표 원소를 루트 노드라 가정한다.하나의 배열로 상호배타적 관계를 가지는 집합을 모두 표현한다.배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.disjoi..

큐뜻 줄을 서다자료구조 먼저 들어간 데이터가 먼저 나오는 자료구조 (FIFO, 선입선출)ADT연산 isFull 큐에 들어 있는 데이터가 maxsize인지 확인isEmpty 큐에 들어있는 데이터가 하나도 없는지 확인해 boolean 값을 반환front === rear인 경우push 큐에 데이터를 푸시pop 큐에서 처음에 푸시한 데이터를 팝하고, 그 데이터를 반환상태front 큐에서 가장 처음에 팝한 위치를 기록rear 큐에서 최근에 푸시한 데이터의 위치를 기록data[maxsize] 큐의 데이터 배열 구현1. shift 메서드 이용const queue = [];queue.push(1); // 큐에 데이터 추가let firstItem = queue.shift(); // 큐의 맨 앞 데이터 제거2. 배열 이용..

1. 스택 개념스택 : 먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조LIFO (Last In First Out) : 먼저 들어간 것이 마지막에 나오는 규칙push : 스택에 삽입하는 연산pop : 스택에서 꺼내는 연산최근에 삽입한 데이터를 대상으로 연산해야 한다면 스택을 떠올리는 것이 좋음 2. 스택의 정의스택의 ADTADT란 ?Abstract Data Type의 약자추상 자료형 (인터페이스만 있고 실제로 구현은 되지 않는 자료형)일종의 자료형의 설계도정의해야 할 연산 : push , pop ,  isFull , isEmpty 정의해야 할 상태 : top , data[maxsize]  데이터가 없으면 top = -1 스택 세부 동작1. push(3) 호출2. isFull()을 수행하여 data..

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(n)의 생성자라..

문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수의 범위는 -231 보다 크거나 같고 231보다 작다. 출력 M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다. 내 풀이 n = int(input()) fa = set(list(map(int, input().split(" ")))) m = int(inp..

문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM 앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2인 경우를 생각해보자. [1,2,3,4,5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람들이 돈을 뽑을 때까지 기다려야 하기 때문에, 3 + 1 + 4 = 8분이 필요하게 된다. ..

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정ㄴ 대표적인 탐색 알고리즘: DFS & BFS자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조ㄴ 스택과 큐 : 자료구조의 기초 개념ㅤ> 삽입 (Push) & 삭제 (Pop)을 핵심으로 하여 구성됨ㅤ> 오버플로 (특정한 자료구조가 수요할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생) & 언더플로 (특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행)도 고민해야 함 스택스택 = 박스 쌓기 = 아래에서부터 위로 쌓임 = 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야 함 = 선입후출 구조 (First In Last Out) = 후입선출 구조 (Last in First O..

문제 유진수는 어떤 수를 10진수로 표현한 뒤 그 수를 두 부분으로 나눴을 때, 앞부분 자리수의 곱과 뒷부분 자리수의 곱이 같을 때를 말한다. 예를 들어, 1221은 유진수이다. 12와 21로 나눴을 때, 앞부분 자리수의 곱 1*2는 뒷부분 자리수의 곱 2*1과 같기 때문이다. 1236도 마찬가지로 유진수이다. 하지만, 1234는 아니다. 수를 나눌 때 항상 연속된 자리수를 나눠야하고, 각 부분에 적어도 한자리는 있어야 한다. 예를 들어, 12345는 총 4가지 방법으로 나눌 수 있다. 1-2345, 12-345, 123-45, 1234-5 어떤 수 N이 주어질 때, 이 수가 유진수인지 아닌지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수 N이 주어진다. 이 수는 2,147,483,647보다 작거나 ..

문제 오민식 선생님은 올해 형택초등학교 6학년 1반 담임을 맡게 되었다. 오민식 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 오민식 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자. 위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반..

문제 동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다. 이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다. 하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자. 입력 첫째 줄에 구간의 시작과 끝을 나타내는 정수 A, B(1 ≤ A ≤ B ≤ 1,000)가 주어진다. 즉, 수열에서 A번째 숫자부터 B번째 숫자까지 합을 구하면 된다. 출력 첫 줄에 구간에 속하는 숫자의 합을 출력한다. 내 풀이 n, m = map(int, input().split(" ")) k = 1 ..

문제 어떤 단어를 뒤에서부터 읽어도 똑같다면 그 단어를 팰린드롬이라고 한다. 'radar', 'sees'는 팰린드롬이다. 수도 팰린드롬으로 취급할 수 있다. 수의 숫자들을 뒤에서부터 읽어도 같다면 그 수는 팰린드롬수다. 121, 12421 등은 팰린드롬수다. 123, 1231은 뒤에서부터 읽으면 다르므로 팰린드롬수가 아니다. 또한 10도 팰린드롬수가 아닌데, 앞에 무의미한 0이 올 수 있다면 010이 되어 팰린드롬수로 취급할 수도 있지만, 특별히 이번 문제에서는 무의미한 0이 앞에 올 수 없다고 하자. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. 출력 각 줄마다 주어..

문제 영식이는 직사각형 모양의 성을 가지고 있다. 성의 1층은 몇 명의 경비원에 의해서 보호되고 있다. 영식이는 모든 행과 모든 열에 한 명 이상의 경비원이 있으면 좋겠다고 생각했다. 성의 크기와 경비원이 어디있는지 주어졌을 때, 몇 명의 경비원을 최소로 추가해야 영식이를 만족시키는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다. 출력 첫째 줄에 추가해야 하는 경비원의 최솟값을 출력한다. 내 풀이 row, col = map(int, input().split(" ")) status = [] sec_row = 0 ..

문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. 내 풀이 # 문제 : https://www.acmicpc.net/problem/1193 num = int(input()) cpy = n..

문제 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. 입력 첫째 줄에 알파벳 대소문자로 이루어진 단어가 주어진다. 주어지는 단어의 길이는 1,000,000을 넘지 않는다. 출력 첫째 줄에 이 단어에서 가장 많이 사용된 알파벳을 대문자로 출력한다. 단, 가장 많이 사용된 알파벳이 여러 개 존재하는 경우에는 ?를 출력한다. 내 풀이 word = input().lower() num = [0] * 26 for i in word : j = int(ord(i)) - 97 num[j] += 1 maxNum = max(num) c = num.count(maxNum) if c != 1 : print("?") ..