Definition of Seon

1. 문제 이 문제는 배열을 한 변의 길이가 2 ** n인 배열을 Z 모양으로 탐색하며r행 c열을 몇 번째로 방문하는지 출력하는 프로그램이다.r과 c, 그리고 순서 모두 0부터 시작한다. 2. 풀이재귀적으로 접근하기! 4등분을 반복한다!1. 만약 size가 1이 될 경우 ans는 start로 초기화한다.2. size가 2 이상인 경우 배열을 4등분하여 r과 c가 어디에 위치하는지 확인한다.3. 해당 사분면에 대해서 r과 c의 값을 갱신하고 해당 조각의 가장 왼쪽 위가 몇 번째인지를 구한다.4. 위와 같은 방법으로 find 함수를 반복한 뒤 ans를 출력한다. 3. 코드import sysinput = sys.stdin.readlinedef find(start, size, r, c): global an..

1. 문제우선순위 큐, 힙큐를 활용하여 풀어야 하는 문제. 2. 풀이heapq의 기본적인 동작, heappush와 heappop만 활용하면 되는 문제이다. - heapq.heappush(배열 이름, 원소)- heapq.heappop(배열 이름) 이 두 가지만 알면 이 문제를 쉽게 풀 수 있다.단, 평소에 사용하던 기본 리스트나 deque의 사용법과는 좀 달라서 주의가 필요하다. 3. 코드import heapqimport sysinput = sys.stdin.readlinen = int(input())arr = []for i in range(n): x = int(input()) if x == 0: if len(arr): print(heapq.heappop(arr)..

1. 문제이 문제는 주어진 문제의 난이도를 절사평균으로 구하는 문제다.위아래 15%를 제외하고 평균을 계산하되, 정수가 아닌 경우 모두 반올림한다. 2. 풀이python의 내장 함수 round는 사사오입이 아니다.우리가 일반적으로 알고 있는 반올림은 사사오입.4 이하는 버리고 5 이상은 올리는 반올림이다.그러나 python의 round는 오사오입이다.5 미만과 5 초과를 기준으로 버림과 내림을 실행한다.5일 경우에는 짝수냐 홀수냐에 따라서 결과가 달라진다.즉, 이 문제에서는 python의 내장함수 round를 사용해서는 안 된다.1. n을 입력 받아서 만약 0명일 경우 난이도 0을 출력한다.2. 일반적인 반올림을 하기 위한 함수를 만든다.3.  score을 입력 받고 절삭할 인원수를 반올림하여 찾는다.4..

1. 문제 독서실에서 원하는 자리를 이용 가능한 시간을 구하는 문제다.1, 2번 규칙에 따라 새로 온 사람이 이용하는 좌석을 파악해 문제를 해결해야 한다. 2. 풀이1. 0900 ~ 2100 이라는 숫자로 나오지만 이걸 분 형태로 바꿔주어야 계산이 편함 (아니면 9시 ~ 10시가 100분이 됨..!)2. 사람들이 선호하는 좌석을 구하는 함수 만들기3. heapq를 사용하여 새로운 사람이 오면 추가하고 visited를 True로 바꾸어주기4. 정답은 720에서 시작해서 자리를 사용할 수 없는 시간 만큼 빼기1. max_dist, best_seat 변수 초기화2. 1부터 n+1까지 돌려서 각각 좌석 번호에 대하여, 이미 방문하지 않은 경우에만 실행3. left_dist, right_dist를 무한대로 초기화..

1. 문제 이 문제는 풍선 m개를 만드는데 걸리는 최소 시간을 구하는 문제이다.스태프마다 만드는 속도가 다른 상황에서 짧은 시간 안에 최소 시간을 구해야 한다. 2. 풀이1. l, r을 양 끝 숫자 0과 max(time) * m으로 초기화한다.2. l보다 r이 크거나 같은 동안 반복문을 실행한다.3. 두 수의 중간값 mid에 대하여 스태프마다 해당 시간에 몇 개를 만들었는지 그 합을 구한다.4. 그 값이 m보다 크거나 같을 경우 답을 mid로 초기화하고 최솟값을 찾기 위해 r을 mid - 1로 바꾼다.5. 아닌 경우 l을 mid + 1로 바꾸어 계속 탐색한다.3. 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())time = li..

1. 문제 이 문제는 각 단어별 가격이 있고 단어를 조합해서 목표 단어를 만들되, 가격을 최소로 하는 문제이다.2. 풀이알파벳의 개수와 같은 길이의 배열을 만들어 그 원소를 하나씩 비교한다.1. word 배열 -> t에 주어진 단어에 들어가는 알파벳 개수 표시2. arr 배열 -> 전공책 각각 주어진 단어에 들어가는 알파벳 개수 표시3. 금액은 inf로 초기화하고 x 배열을 넣어서 word_making 함수 실행4-1. x 배열의 어떤 원소가 word 배열의 원소보다 작은 경우    -> 단어를 만들 수 없으므로 result를 False로 바꾸고 반복문 탈출4-2. x 배열의 모든 원소가 word 배열의 원소보다 큰 경우    -> 단어를 만들 수 있다는 뜻 -> price 갱신 후 return5. 4-..

1. 문제 이 문제는 데스 나이트라는 새로운 말이 이동할 수 있는 위치를 정의하여시작 칸에서 도착 칸으로 이동하는 최소 이동 횟수를 구하는 문제다.2. 풀이지난주에 풀었던 7562번 나이트의 이동 문제와 비슷하다.그 때는 bfs를 사용해서 문제를 해결했는데 다른 문제를 풀면서heapq의 빠른 속도를 체감하고 새로운 방법으로 문제를 풀었다. 먼저 나이트가 움직일 수 있는 위치를 dx, dy 배열 안에 넣어준다.move 함수를 만들어 방문 여부를 체크할 수 있는 배열과우선순위 큐 적용을 위한 (cnt, r, c) 튜플을 넣은 배열을 만들어준다.시작하는 위치의 방문여부를 True로 설정하고 다익스트라 알고리즘에 따라 코드를 짰다.만약 도착 지점에 갔다면 cnt를 리턴해준다.나이트가 갈 수 있는 모든 방향에 대..

1. 문제이 문제는 1, 2, 3 세 수를 사용하여 어떤 정수의 합을 나타내는 방법의 수를 구하는 문제이다.특이한 점은 합을 나타낼 때 순서가 다르면 다른 방법이라는 것이다.1+2와 2+1은 각각의 방법으로 취급된다. 2. 풀이처음에는 dfs로 단순히 접근하여 모든 경우의 수를 확인하였다.작은 숫자에서는 문제가 없었으나 테스트케이스 중 숫자가 커지면 어마무시하게 recursion이 일어나는 모양이다.재귀 오류를 해결하니 시간 초과가 떠서 다른 방법으로 접근을 시도했다. dfs가 시간초과가 날 때는 bfs 또는 dp 등등 새로운 방법을 시도할 때라는 거다.dp를 사용하여 규칙성을 발견하였다. 처음에는 규칙을 잘못 발견했다.단순히 1, 2, 4, 7로 증가되는 것만 확인하여 각각 차이가 1, 2, 3이니까 ..

1. 문제이 문제는 배열을 반시계 방향으로 R번 회전시킨 결과를 구해 출력하는 문제이다. 2. 풀이귀찮고 오래 걸릴 것 같은 구현 문제였다.풀기 싫어서 이틀은 미루었다..ㅠㅠ 배열에서 어느 위치에 있느냐에 따라 돌렸을 때 자리까지 돌아오는 횟수가 달라진다.최대한 시간을 줄이기 위해 꼭 필요한 만큼만 돌려야겠다는 생각을 했다.즉, 다시 자기 자리에 돌아와 한 바퀴 회전하는 경우를 빼야 한다는 것.전체 길이로 돌리는 횟수를 나눈 나머지 만큼만 돌리면 된다. 2차원 배열로는 어려워서 1차원 배열로 바꾸기로 정했다.좀 지저분하지만 각각의 그룹을 모두 분리해냈고,그 뒤에 1차원 배열 내에서 돌리기를 쉽게 수행했다. 그 뒤 다시 2차원 배열로 바꾸어 출력해주었다. 3. 코드n, m, r = map(int, inpu..

1. 문제 이 문제는 직사각형 종이를 한 변이 1인 직사각형 모양의 조각으로 잘라서조각 안의 수를 왼->오, 위->아래로 붙인 수의 합을 최대로 만드는 프로그램을 짜는 문제이다.특이점은 종이의 크기가 최대 4*4로 작다는 점이다.2. 풀이이 문제는 다양한 시도를 했으나 그만큼 실패를 많이 경험했다.처음에는 단순히 생각해서 그냥 가로로 쭉 자른 종이들의 합, 세로로 쭉 자른 종이들의 합,이 두 값을 비교해서 큰 값으로 하면 되잖아? 라고 생각했다.왜냐면 종이를 쭉 이어서 자르지 않고 막 조각내면 자릿수가 작아지니까.근데 이건 잘못된 생각이었다.문제에서 나온 예시와 달리 '0'이 들어가는 경우에 이상한 상황이 생긴다. 예를 들어서, 아래와 같은 종이조각 말이다.0023001299990011 1. 가로로 쭉 ..