본문 바로가기

분류 전체보기91

백준(BOJ) 11003 최솟값 찾기(Python) 덱으로 바로 풀 수 있는 문제. 최소 힙으로 최솟값을 뽑아낼 생각이었는데, O(nlogn)이라 그런지 python이랑 pypy 둘 다 시간 초과가 터졌다. 그래서 생각한 게, 덱을 써서 항상 최솟값이 덱 맨 앞에 있도록 하는 것이다. 탐색 범위에 있지 않은 값을 덱에서 빼고, 현재 덱에 삽입될 값보다 큰 값을 가졌으면 덱에서 빼는 식으로 덱을 수정해나갔다. 결국 O(n)으로 해결할 수 있었다. ​ 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setrecursionlimit(100000000) n,l=map(int,.. 2022. 7. 9.
백준(BOJ) 18170 두 동전 언리미티드(Python) BFS 문제였다. 두 개의 동전을 체크해야하기 때문에 visited 리스트를 2개 만들어 사용했고, 두 동전의 위치가 모두 visited에 걸리면 queue에 append하지 않는 식으로 구현했다. 그 외에도 두 동전이 모두 떨어진 경우 append하지 않았고, 한 동전이 다른 동전의 위치로 움직이는데 다른 동전이 움직이지 않는 경우 append하지 않았다. queue에는 현재 움직인 횟수와 첫번째 동전의 x,y좌표값, 두번째 동전의 x,y좌표값을 집어넣었다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import deque import heapq import copy #input=sys.stdin.readline #sys.setre.. 2022. 7. 8.
백준(BOJ) 2180 소방서의 고민(Python) 그리디 문제였다. at+b 꼴의 일차 함수에서 단순히 a와 b값만으로 정렬해서 문제를 풀 수 없다고 생각했고, 느낌상 b/a로 정렬하면 될 것이라고 생각했다. 그러나 확신이 없어서 결국 검색해보니 내 감이 맞았다. 당연히 b/a 값이 같다면 a값이 더 큰 순으로 정렬해야 더 효율적이기 때문에 key는 b/a, -a 순으로 오름차순 정렬했다. 그러나 여기서 문제는 a가 0인 경우 어떻게 할 것인가인데, a가 0인 경우에는 t에 상관없이 진화 시간이 똑같으므로 b의 크기에 관계 없이 우선 순위의 맨 뒤에 위치해야한다. 따라서 b/a 자리에 INF를 넣어주면서 알고리즘을 완성시켰다. 코드는 다음과 같다. # -*- coding: utf-8 -*- import sys from collections import .. 2022. 7. 8.
프로젝트 정리 & 7월 동안 진행해야 할 내용 프로젝트 1. 뉴스 분석 기반 기업 주가 등락 판단 AI를 이용한 투자 모델링 ​ 개인적으로 이번 방학 내에 꼭 마무리하고 싶은 프로젝트다. 구상은 작년 초부터 했는데 이제야 진행하게 됐다. ​ 주가 데이터를 수집할 상장기업 50개 선정 위에서 선정한 기업의 분 단위 주가 데이터 API 연동 - 크레온 API 사용 예정 일별 뉴스 기사 & 주가 데이터 축적 - 매일 진행해야 할 것 뉴스 기사 분류 & 영화 리뷰 분류 AI 코드 리뷰 및 접목 - 사용할 AI 개발 위 4개를 7월 동안 진행할 예정이다. ​ 프로젝트 2. 개인 프로필 웹사이트 개발 ​ Node.js, React.js를 비롯한 프론트엔드 공부가 목적이다. 사실 파이썬을 하기 때문에 Django를 써도 되겠지만, 일단 스탠다드부터 공부해보고 싶.. 2022. 7. 8.
백준(BOJ) 1027 고층 건물(Python) 간단한 브루트포스 문제이다. n의 크기가 그리 크지 않기 때문에 따로 시간복잡도 계산을 하지 않고도 브루트포스 문제임을 쉽게 알 수 있었다. 현재 서있는 빌딩에서 보고 싶은 빌딩을 고르고, 그 빌딩과의 선분을 연결한 뒤 기울기와 y절편을 이용해 두 빌딩 사이에 있는 빌딩 중 선분보다 높은 빌딩이 없다면 ans에 1을 더하고, 그렇지 않으면 continue하는 방식으로 알고리즘을 구현했다. ​ 코드는 다음과 같다. n=int(input()) L=list(map(int,input().split())) ans=0 for i in range(n): c=0 for j in range(n): if i==j: continue a=(L[j]-L[i])/(j-i) b=L[j]-a*j if i=a*k+b: flag=1 b.. 2022. 7. 8.
백준(BOJ) 1799 비숍(Python) DFS를 두 번 해주면 되는 문제였다. 아이디어는 다음과 같다. 기본적으로 체스판은 흑과 백 격자로 나누어져있다. 비숍은 체스판에서 대각선으로만 움직이는데, 그렇게 되면 흰 칸에 위치한 비숍은 흰 칸으로 밖에 움직일 수 없고, 검은 칸 역시 마찬가지이다. 즉, 흰 칸의 비숍과 검은 칸의 비숍은 서로 영향을 줄 수 없는 것이다. 왼쪽 위 칸에서부터 우상향 대각선의 번호를 매기고, 왼쪽 아래 칸에서부터 우하향 대각선의 번호를 매겨 각 격자의 새로운 고유 넘버를 지정해줬다. 그렇게 하면 대각선 상에 비숍이 하나만 위치해도 그 칸의 고유 넘버와 같은 고유 넘버를 공유하는 칸에는 모두 비숍이 위치할 수 없게 되는 것이다. 예를 들면, (0,1)에 비숍이 위치해있다면 (0,2)와 (2,1)은 각각 첫번째 고유 넘버.. 2022. 7. 8.

티스토리툴바