본문 바로가기

분류 전체보기 39

[백준,Python]15649번 N과 M (1)(Backtracking) 이런 유형의 탐색 문제를 만났을 때,가장 먼저 모든 경우의 수를 다 계산해야 풀 수 있는 가를 생각해본다.그렇지 않다면 함수로 조건문을 사용하여 빠르게 탐색않해도 될 부부을 정의할 수 있는 방안이 무엇인지 생각한다.예를 들어, 이 문제에서는 중복된 수열에 대해서는 탐색하지 않아도 된다. 실제로 수열의 크기가 커진다면 굉장히 Critical 해질 수 있는 부분이다. ( 1 1 2 3 4 5 6 7 8 ...) 또한 사전 순으로 증가하는 순서로 출력하는 부분에서 탐색 범위가 한정되었다. Brute Force 로 접근할 경우,수열의 크기가 커질 경우,  가능한 모든 조합을 찾고 그 중에서 필터링하는 방법은 시간이 굉장히 오래 걸리고 비효율적이다. 따라서 처음 빈 수열을 입력 받아 , 조건이 맞을 때 출력을 하.. 2024. 5. 11.
[백준,Python]11651번 좌표 정렬하기 2(Sort) 처음 문제를 풀 때, 생각 없이 아래와 같이 Bubble Sort로 접근하였다. import sysinput = sys.stdin.readlinenum = int(input())s_list = []for i in range(num): N,M = map(int, input().split()) s_list.append([N,M])c = 0 while c s_list[c+j][1]: s_list[c], s_list[c+j] = s_list[c+j], s_list[c] c += 1for k in s_list: print(k)하지만 Bubble Sort 방식으로 접근하면 O(n^2) 시간 복잡도를 가진다. 문제에서 점의 개수(N)이 최대 100,000이라고 주어졌으.. 2024. 5. 6.
수학 공식을 만드는 인공지능(AI) 수학 공식을 만드는 인공지능(AI) 오랫동안 수학의 역사를 살펴보면 가설(Conjecture)은 천재들의 전유물이었다. 지난 100년동안 발견한 중요한 수학 공식은 수십개에 불과했다. 또한 많은 수학자들이 하나의 공식을 생성하기 위해 몰두하고 있다. 그러나 최근 AI 가 이를 대신하기 시작했다. 지난 10일 미 과학 전문지 'ZME사이언스'는 테크니온 이스라엘 공과대학에서 지난 2019년 개발한 인공지능이 당초 목표대로 가설(Conjectures)을 생성하기 시작했다고 보도했다. 이는 수학자들이 해야 할 새로운 추측을 컴퓨터가 대신할 수 있다는 것을 말해주고 있다. 알고리즘이 많은 양의 데이터 패턴을 감지하는 기계 학습은 이미지 인식에서 신약 발견에 이르기까지 다양하게 적용돼 왔다. 그러나 보다 더 근본.. 2021. 2. 27.
[백준,Python]7576번 토마토(Graph Search/BFS, 시간초과 해결) [백준,Python]7576번 토마토(Graph Search/BFS) www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 테스트 케이스들을 모두 통과하도록 코드를 짰지만 , 반복문이 많이 들어가서 불안했는데 '시간초과'가 발생하였다. 시간초과가 발생했던 코드와 개선하여 효율적으로 짠 코드를 비교해가며 이번 문제를 설명하려 한다. 1. 처음 코드( 시간 초과) import sys input = sys.stdin.readline m,n = map(i.. 2021. 2. 21.
[자료구조]Stack, Queue, Deque [자료구조]Stack, Queue, Deque 알고리즘 문제를 풀다 보면 자료구조를 활용하여 효율적인 코드를 짤 수 있는 경우들을 볼 수 있다. 예전에 배웠던 내용들인 자료구조에 대한 이해가 부족하고 복습을 할 겸 내용을 정리해 보려고 한다. 스택(stack) 스택은 젠가 모형과 같이 차곡차곡 쌓아 올린 자료구조를 말한다. 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근을 할 수 있다. 즉 삽입하거나 삭제하거나 등 자료를 처리해야 하는 상황에서 top에 있는 데이터만 접근을 하여 push나 pop을 진행할 수 있다는 것이다. 따라서 후입선출방식인 Last In First Out 구조이다. 활용 예) - 웹페이지 뒤로가기 - 실행 취소(undo) : 가장 나.. 2021. 2. 21.
[백준,Python]15903번 카드 합체 놀이(Greedy) [백준,Python]15903번 카드 합체 놀이(Greedy) www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 이번 문제의 알고리즘은 Greedy이고, 1. 처음 푼 풀이와 2. 효율적인 풀이를 비교하며 설명하려고 한다. 1. 처음 푼 풀이 import sys input = sys.stdin.readline a,b = map(int, input().split()) card = list(map(int,input().spli.. 2021. 2. 19.

티스토리툴바