오구의코딩모험

문제 3줄 요약 1. 로봇 청소기가 청소를 한다. 2. 위의 3 가지 패턴을 반복하며 작동한다. 3. 로봇 청소기가 멈출 때까지 청소한 칸의 개수를 출력하라 내용이 길지만, 기능을 차근차근 하나씩 구현해보자! from sys import stdin ## 1번 기능 : 해당 칸 청소 def func_1(input_list,room): x = input_list[0] y = input_list[1] if room[x][y] == 0: room[x][y] = 2 return 1 return 0 ## 2번 기능 : 상하좌우가 청소된 경우 def func_2(input_list,room): x = input_list[0] y = input_list[1] direction = input_list[2] ## Righ..

문제 3줄 요약 1. 0은 빈칸, 1은 벽, 2는 바이러스 2. 벽이 세워지지 않는 빈칸에는 바이러스가 퍼진다. 3. 3개의 벽을 세워 바이러스 퍼지는 것을 최소화해라! 3개의 벽을 세울 수 있는 모든 경우의 수를 브루트포스 알고리즘을 이용하고 벽을 임의로 세우고 난 후, 바이러스를 BFS로 확산시켜 남아 있는 빈칸의 수를 최대가 나올 때까지 갱신시킨다. from sys import stdin # 좌표 넣을 구조체 class XY: def __init__(self, x, y): self.x = x self.y = y # 바이러스 확산 def BFS(copy_list, two): Q = [] for check in two: Q.append(check) ## 상하좌우로 확산 while(len(Q) != 0)..

문제 3줄 요약 1. A0 = 1 2. i 번째 값 = ⌊i/P⌋ 번째 값 + ⌊i/Q⌋ 번째 값 3. ⌊ x ⌋ = x를 넘지 않는 가장 큰 정수 ⌊ ⌋ 가 오타인가 싶었지만, 아래 힌트를 보니 위의 설명과 같은 기호였다. 위의 기호는 i/P 와 같은 나눗셈에서는 소수점을 지운 값 즉, 몫에 해당한다. 따라서 피보나치 함수에서 사용했던 상향식과 메모리얼을 이용하여 값을 구해주었다. from sys import stdin # 상향 접근 + 메모리얼 def func(num): if num == 0: return 1 else: if num//P not in num_dict: num_dict[num//P] = func(num//P) if num//Q not in num_dict: num_dict[num//Q]..

문제 설명 3줄 요약 1. 지민이는 과장해서 이야기하는 것을 좋아한다. 2. 그 이야기의 진실을 아는 사람을 최대한 피해서 과장되게 이야기 하고싶다. 3. 최대 몇개의 파티에서 과장되게 이야기할 수 있을까 처음엔 문제를 굉장히 쉽게 생각하여 set로 파티 인원과 진실을 아는 사람의 중복을 제거 하는 것으로 접근하려 했으나, 진실을 아는 인원과 파티를 즐긴 사람도 곧, 진실을 알게되는 인원인 것을 고려해주지 않았다는 것을 깨달았다. 때문에 진실을 아는 인원을 각 파티에 참여했던 인원을 반복해서 탐색하며 갱신해주고, 최종적으로 과장되게 이야기할 수 있는 파티의 수를 카운트 해주었다. from sys import stdin if __name__ == "__main__": ## 사람의 수 N, 파티의 수 M N..

문제 설명 3줄 요약 1. 3가지 연산이 가능한 큐 2. 첫 번째 요소 빼기, 두 번째 원소 왼쪽 한칸 이동, 세 번째 원소 오른쪽 한칸 이동 3. 주어진 원소를 빼려고 할 때, 왼쪽 또는 오른쪽 이동의 최솟값은 몇 번 일까요? 기존의 리스트를 사용하기엔 왼쪽 또는 오른쪽으로 이동할 경우, 모든 원소를 한칸씩 값을 옮겨줘야한다는 문제가 생기기 때문에 링크드리스트로 값을 연결해주어 해결하였다. from sys import stdin # 링크드리스트에 사용할 원소 class Node: def __init__(self,data,next=None): self.data = data self.next = next # 링크드리스트 및 기능 class LinkedList: def __init__(self): self...

문제 3줄 요약 1. 흔히 알던 피보나치 수열을 구현한다. 2. 기본 값인 0과 1을 몇 번 호출하는지 알아보고자 한다. 3. ex) 3 = 2+1 = 1+0+1 이므로 0은 1번 호출, 1은 2번 호출이다. 위의 피보나치 코드는 재귀 함수를 통해 실행 되며, 하향식 구조이다 보니 그대로 실행하면 시간 초과가 생긴다. ex) 3 = 2+1 = 1+0+1 따라서 반복문을 통해 상향 구조로 코드를 작성, 한번 실행한 피보나치 값들은 리스트에 담아주어 재사용하는 방식으로 시간 초과를 해결하였다. ex) 0=0, 1=1, 2=1+0, 3=1+0+1 from sys import stdin T = int(stdin.readline()) def fibonacci(target): # 리스트의 첫 번째 값은 0의 호출수..

문제 설명 3줄 요약 1. 두 좌표에 터렛이 각각 존재한다. 2. 두 터렛에서 타겟까지의 거리가 주어진다. 3. 타겟이 존재할 수 있는 위치의 수를 구하여라. 알고리즘의 분류가 수학, 기하학인 것처럼 문제 설명이 굉장히 길지만 두 원의 접점을 구하라는 문제이다! 각 중심(좌표)과 반지름(타겟까지의 거리) 가 주어졌을 때, 겹치는 접점의 경우의 수는 위의 그림을 참고한다면 쉽게 알 수 있다! 기본적으로 두 원이 일치할 때, 답은 -1 (2) 두 원이 외접할 때, 답은 1 (3) 두 원이 내접할 때, 답은 1 (4) 두 원이 서로 떨어져 있고 만나지 않을 때, 답은 0 (5),(6) 한 원이 다른 원의 내부에 있고 두 원이 만나지 않을 때, 답은 0. (1)과 같은 나머지 경우, 답은 2 6 가지 정도로 분..

문제 3줄 요약 1. 8x8 체스판을 만들 것이다. 검은색,흰색 패턴인지 흰색,검은색 패턴인지 고려해야한다. 2. 틀린 패턴이 있다면 다시 색칠한다. 3. 크기가 다양한 체스판에서 최소한으로 고쳐서 색칠하여 만들 때, 수정하는 최솟값을 구하자! 알고리즘 분류가 브루트포스 알고리즘이었다. 즉, 완전탐색 알고리즘, 모든 경우의 수를 탐색하면서 요구 조건에 충족되는 결과만 가져오는 알고리즘이다. 따라서 틀을 먼저 만들고 필요한 모든 조건을 생각해보자! # N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수 입력 V,W = map(int, input().split()) chess = [] count = 0 count_list = [] color_list = ["W","B"] if __name__ == ..

문제 설명 3줄 요약 1. 길이가 N인 수열 P(0부터 N-1까지의 수를 한번씩 포함), 길이가 N인 배열 A, 길이가 N인 배열 B가 있다. 2. 수열 P를 배열 A에 적용하면 배열 B가 된다. B[P[i]] = A[i] 3. 배열 A가 주어졌을 때, 수열 P를 적용하면 비내림차순이 된다. 수열 P를 찾아라! 문제에서 포인트는 비내림차순 과 B[P[i]] = A[i] 식을 만족하는 것! 여기서 비내림차순은 이해하기로는.. 오름차순에서 같은 원소가 있을 때를 고려해준 정렬 방법이라고 이해하고 풀었다! Ex) 1, 2, 3 = 오름차순, 비내림차순 1, 2, 2, 3 = 비내림차순 이해했다면 입력 조건을 만족하는 틀 부터 짜보자! # 배열 A의 크기 N 입력, ex) 3 N = int(input()) # ..

문제 설명이 복잡해보이지만 제한 조건과 예시를 보면 보다 쉽게 이해할 수 있다! 첫 줄은 집합 S의 크기, 두 번째 줄은 집합의 원소들, 세 번째 줄은 정수 n 따라서 크기가 4인 집합 S = [1, 7, 14, 10] 에서 2를 포함하는 좋은 구간을 구하라! 라고 해석할 수 있겠다. 좋은 구간의 원소들은 집합 S에 속하지 않으므로 [1,2]가 아닌 2부터 시작하고, A