종우의 삶 (전체 공개)

알고리즘 문제에는 소수와 관련된 문제가 많이 등장한다. 무지 짜증난다. 해당 숫자가 소수인지 알수있는 알고리즘은 여러가지가 있는데 소수 여부를 알고싶은 숫자 N에 대해,1) 직접 모든 수를 집어넣어 N의 약수가 1만 존재하는지 확인하는 방법과2) 에라토스테네스의 체 방법이 대표적이다. 1번 방법은 어떻게 구현하느냐에 따라 시간복잡도가 길어지거나 짧아질 수 있는데, N의 약수인지 확인할 숫자의 범위를 지정해주면 조금은 빠르게 수행할 수 있겠다. def is_prime(n): if n 소수가 아님 return False # 위 3개 조건에서 걸러지지 않으면, (25 이상의 2, 3 배수가 아닌 수들) i = 5 while i * i  사실 소수의 검증을 ..

알고리즘 공부를 시작할 때 들어본 DFS, BFS를 드디어 만났다. 깊이 우선 탐색, 너비 우선 탐색 그래 말은 좋다 이거야문제를 읽어본 결과 하나도 모르겠다는 것이 나의 결론이었다.어쨌든 정리를 하면서 살펴보자. 정점과 노드를 혼용하여 사용할것이나 같은 의미로 생각하자.  0. 정점(vertex)과 간선(edge)우선 말이 어렵다. 정점은 무엇이고 간선은 무엇인가. 코드에 적어야 할 vertex와 edge를 우선 알아야 하겠다. 정점(또는 노드)과 간선은 그래프에서 쓰이는 말이다. 그래프는 정점과 간선으로 이루어져있는 조직도로 생각하면 되는데정점은 데이터가 저장되는 곳이고, 간선은 그 정점들을 연결하는 선이다.   좌측에 있는 그래프를 보면 번호가 들어있는 정점(동그라미)와, 그 정점들을 연결하는 간선..

(제목은 거짓입니다.)무언가 알고리즘다운 알고리즘을 처음으로 알게 된 것은 이진 탐색부터라고 할 수 있겠다. 정렬하고 뽑아내는 것도 물론 쉽지 않지만, 애초에 정해진 방법이 있는 알고리즘을 처음 배운것이다. 사실상 단어 뜻만 가지고서는 이걸로 뭘 하는건가 싶은데 가끔씩 실생활에서도 사용을 하는.. 그런 방법이었다. 원리는 간단하고 사용할 조건도 필요하다. (간단?)이 알고리즘은 특정 숫자를 찾는 업 - 다운 게임을 생각하면 되겠다. 근데 이걸로 끝이겠냐? 사실상 개념은 익숙한 편이고 그리 어렵지 않지만 이것을 배우는 이유는 문제 해결을 위해서다.수많은 데이터들 중에서 원하는 데이터를 찾을 수 있는 방법.. 중 하나인 것이다. 좀더 자세히 알아볼까? (2분 초과) 이진 탐색꺼무위키에서 찾은 수도코드를 살펴..

https://www.acmicpc.net/problem/18870 이러한 문제가 있다. 좌표압축 어쩌고인데대충 구하는 로직은 어렵지 않았지만 입력값이 100만개에 육박하기때문에 시간복잡도를 줄이는 것이 관건이었다. 나의 스무스한 흐름대로 적어본 최초의 코드는 이러하다. n = int(input())coordinates = list(map(int, input().split()))set_coord = sorted(set(coordinates))answer = []for i in coordinates: answer.append(set_coord.index(i))print(*answer) 대충 입력을 받고, set으로 좌표들을 저장하고 정렬하여 입력받은 coordinate의 값들의 인덱스 값을 알아내면 ..

오늘은 힙과 해시 테이블에 대해 알아보았다. 왜 이렇게 진도가 빠른가 하면 나도 잘 모르겠다. 어찌되었든 내일은 더 어려운 것들이 나타날 것이기에.. 어쨌든 힙이라 함은 다양한 곳에서 마주친 경험이 있는데, 이렇게 알고리즘으로 접근한 것은 이번이 처음이라 쉽지는 않았다.---  힙이란..정해진 우선순위에 따라 원소를 추가, 삭제가 가능한 자료구조이다. 정말 고맙게도 파이썬에서는 heapq 라이브러리를 지원하여 힙을 편리하게 사용할 수 있다. 최소, 최대 힙 같은 최소, 최대값과 관련하여 힙이 자주 등장하는듯 하다. 최소힙에 대한 기본 예제 같은것이 등장해서 한번 겪어볼 수 있었다. import sysfrom heapq import *n = int(input())nums = list(int(sys.stdi..

Stack과 Queue는 같이 붙어다닌다. 자바로 공부를 했을 때 큐는 들어가지 않아서 개념에 대한 이해가 부족한 것 같다. 먼저 들어간 것이 먼저 나온다.. 어찌보면 당연? 한걸지도 모르지만 세상에 당연한것이 얼마나 있겠는가.. 문제를 마주하니 당연한 것은 거의 없었다. 큐에서 대부분 요소들을 빙빙 돌려 인덱스가 왔다갔다하는 것이 머리에 잘 안들어 온 것이다. 파이썬은 비슷한 함수들로 스택 큐 리스트 등등 많은 것들을 적용하는데 사실 쓰다보면 편하긴 하지만 무엇에 어떤 개념을 사용해야 하는지 정확히 알아야 할 필요가 있겠다. 아웃!

자주 만나는 행렬 문제들을 풀어본다. 쉬운 문제는 어떻게 풀긴 하겠다. 하지만 인덱스를 고려하고, 2차원 행렬을 탐색하고 여행하는 과정은 무척이나 머리가 아팠다. 오늘의 실패 문제를 알아보자. 숫자 정사각형 - https://www.acmicpc.net/problem/1051각 꼭지점의 숫자를 찾아낼 인덱스를 어떻게 정의하고 찾아내는지가 풀이의 방법이었다. 결과 풀이 : 더보기48ms# 방식은 알았으나 구현이 힘들었음. 자료 참고하여 품n, m = map(int, input().split())max_length = min(n, m) # 정사각형 한변의 최대 길이numbers = [input().strip() for _ in range(n)]# for문 3개를 이용함. -> 처음엔 2개로만 쓰려고 했는데..

한번쯤은 겪어야할 상황이었다. 주어진 리스트를 오름차순이든, 내림차순이든 정렬하는 방법에 대한 내용이다. # 언제 발생 한 일인가?무의식 적으로 리스트의 값을 오름차순으로 정렬하여 표현하려고 했다.이를테면 이런식 print(list.sort())해보면 알겠지만 이러한 방법은 동작하지 않는다!! 자동완성으로 .sort가 뜨길래 아무생각없이 사용했었다.그리고 list의 값이 분명 존재하지만 list.sort()를 출력해보면 none이라고 뜬다.print(list.sort())print(sorted(list)) 원하는 출력을 하려면 sorted()라는 함수 안으로 집어넣어야 한다. 이 차이는 무엇일까? --- # 어떤 차이가 있는가? 우선 둘은 메서드와 함수의 차이가 있다. list의 sort() 메서드와 s..