본문 바로가기

분류 전체보기

 (60)
[AWS]EC2 인스턴스에 파일 전송하기(1/2) - 인스턴스 생성 및 Ubuntu 접속 간단한 웹 크롤링을 이용하여 영화 예매 알리미 텔레그램 봇을 만들었다. (인프런-파이썬으로 영화 예매 오픈 알리미 만들기 강좌 참고) 로컬에서 파일을 실행하지 않고도 별도의 서버에서 프로그램이 항상 실행되게 해야 진짜 알리미의 기능을 할 수 있게 된다. AWS에 배포하는 것까지 강좌에 있어서 그걸 토대로 포스팅을 하기로 했다. AWS의 EC2 인스턴스를 이용하여 서버를 만들고 이 서버에서 프로그램을 작동시켜 보자. AWS 홈페이지 접속 - 로그인 - AWS Management Console - 검색창에 EC2 검색 EC2 대시보드에서 인스턴스 시작 클릭 사용할 AMI 선택. 이 강좌에서는 Ubuntu Server 18.04 LTS(HVM) 를 사용했다. 프리티어에서 사용 가능한 t2.micro로 선택. ..
[Baekjoon]14502.연구소 14502.연구소 http://www.acmicpc.net/problem/14502 삼성 SW역량테스트 기출문제였다고 한다. 완전탐색+dfs or bfs 의 문제라고 생각했다. 먼저 구조를 생각해보면 벽을 3개 세운다. 바이러스를 퍼뜨린다. 안전영역의 개수를 센다. 최댓값인지 확인하고 아니면 1로 돌아가서 반복. 최댓값이면 리턴. 여기서 벽을 3개 세우는 것이 문제였다. map에서 0인 부분에서 3개를 골라서 벽을 세워야 하므로 조합개념을 사용해야 했다. 2차원 배열에서 모든 좌표를 다 해보는 방법을 몰라서 찾아본 결과 다음과 같은 방법으로 모든 좌표를 탐색할 수 있었다. N*M 2차원 배열이 주어졌을때 N*M개 중에서 3개를 뽑는다고 생각하면 된다. i를 0~N*M 까지 증가시키면서 (i/M, i%M)..
[SWEA]1226.미로 탐색 문제 중에 기본적인 문제다. bfs, dfs 둘 다 가능해보였는데 bfs로 풀었다. 좌표를 저장하기 위해 Point 클래스를 만들어서 사용했지만 다른 사람들 풀이에서는 그냥 2차원배열 인덱스를 이용했다. 탐색문제에서는 좌표나 노드 클래스를 만들어서 푸는 버릇이 있어서 이렇게 풀었다. 어떤게 더 좋은 방법인지는 모르겠다. q에 다음에 방문할 점을 넣으면서 반복문을 돌렸다. 크게 세가지 조건에 따라 반복문을 수행하도록 했다. 다음에 방문할 점이 도착지이면 반복문 종료 map의 범위를 벗어나면 pass. 이미 방문한 점이거나 벽이면 pass. 탐색문제에서 대부분 다루는 조건이기 때문에 특별히 어려운 건 없었다. 1227.미로2 문제도 있는데 단순히 map의 크기만 100*100으로 늘어난 문제였다.
[Baekjoon]12015.가장 긴 증가하는 부분수열2 Baekjoon #12015. 가장 긴 증가하는 부분 수열2 http://www.acmicpc.net/problem/12015 11053과 같은 문제이지만 N제한이 더 커서 O(N^2)의 방법으로 풀면 시간 초과가 난다. 따라서 O(NlogN) 방법으로 풀어야 한다. 이진 탐색을 활용한 lower bound 알고리즘을 사용했다. Lower Bound : 배열에서 찾고자 하는 값 k가 있을때 k보다 크거나 같은 값의 첫번째 인덱스를 리턴. 예) 배열 {1, 1, 3, 5, 6} 에서 k=1 일때 Lower Bound = 2(1보다 크거나 같은 값은 3이므로 3의 인덱스인 2를 리턴) 먼저 LIS를 저장할 빈 배열을 하나 생성하여 이를 갱신해나가면서 LIS를 구한다. 입력된 배열 a = {10, 20, 10..
[Baekjoon]11052.카드 구매하기(DP) Baekjoon#11052. 카드 구매하기http://www.acmicpc.net/problem/11052예전에는 붕어빵 판매하기 문제였는데 카드 구매하기 문제로 바뀐 것 같다. 문제를 읽어보니 내용만 다르고 문제에서 물어보는 것은 같은 것이었다. 카드 N개를 구매할 때 가장 비싸게 구매할 경우 가격 총합을 구하는 문제이다. 붕어빵 문제에서는 붕어빵 N개를 판매할때 최대 수익을 구하는 문제였다. 결국은 같은 말이다. 문제를 풀기 위해서 배열 d를 정의한다. d[n] : 카드 n개를 구매할 때 최대 가격 예전에 백준 알고리즘 인강을 들었을때 풀었던 방법을 참고했다. 1개를 살 때, 2개를 살 때, ..., n개를 살 때 각각 가격이 p[n]으로 다르다. 구매해야하는 총 카드의 개수가 n개이므로 먼저 1개를..
[Baekjoon]1699.제곱수의 합(DP) Baekjoon#1699. 제곱수의 합http://www.acmicpc.net/problem/1699수학적으로 좀 생각을 해봐야하는 문제였다. 어떤 자연수 n을 제곱수의 합으로만 나타낼 때 최소인 경우의 수를 구하는 문제이다. 예시는 문제에도 잘 나와있다. $$11=1^{2}+1^{2}+1^{2}+2^{2}+2^{2}$$ 11은 이렇게 5개의 합으로 나타낼 수도 있지만 이것이 최소인 경우는 아니다. $$11=1^{2}+1^{2}+3^{2}$$ 이처럼 3개의 제곱수의 합으로도 나타낼 수 있으므로 n이 11일때 답은 3 이다. 여기서 한가지 착각을 하기 쉬운데 나도 똑같은 생각을 했다. 제곱수의 합으로 나타낼 때 n보다 작은 가장 큰 제곱수를 사용하여 나타낼 때가 최소일 거라고 생각한것이다. 하지만 그렇지 ..
[Baekjoon]2579.계단오르기(DP) Baekjoon #2579. 계단오르기 http://www.acmicpc.net/problem/2579문제를 처음 읽었을때 포도주 시식 문제와 비슷한 문제라고 느꼈다. 다른 점은 이 문제는 종점이 마지막 계단으로 정해져 있다. 마지막 계단을 n번째 계단이라고 하고 n번째 계단에 도착하는 방법을 생각해 보면 다음과 같다. 1. 바로 이전 계단을 밟지 않고 오는 경우.2. 바로 이전 계단을 밟고 오는 경우. 1에서 바로 이전 계단을 밟지 않고 왔다는 것은 전전계단은 반드시 밟았어야 한다.(1칸이나 2칸씩만 올라갈 수 있으므로 !! 이 경우 두칸을 올라온 것임). 1 에서 바로 이전 계단을 밟고 왔다는 것은 두 계단을 연속으로 밟은 것이므로 전전계단은 반드시 밟지 않았어야 한다. 빨간색칸이 밟지 않고 온 칸이..
[Baekjoon]11054.가장 긴 바이토닉 부분 수열(DP) Baekjoon#11054http://www.acmicpc.net/problem/11054LIS문제의 원리를 이용하여 풀 수 있는 문제 중 하나이다. LIS 문제 해결 방법은 이전 포스팅을 참고하자. 여기 처음에는 i번째 수까지는 증가 수열, i번째 수 이후 부터는 감소 수열을 이루는 방법으로 접근했다. 두 문제 모두 풀어본 다음에 이 문제를 접했기 때문에 그런 아이디어를 떠올렸는데 반복문을 돌때 i도 변하는데 이 때 배열 d에 저장되는 값에 문제가 있는 것 같았다. 내가 구현을 못한거 같기도 하다. 다른 사람들의 풀이는 대부분 양방향에서 LIS를 사용하는 방법을 사용했다. 의미상 내가 생각했던 방법과 같지만 구현하는데 있어서 더 쉬운 방법인것 같다. 배열 a, d는 LIS 문제와 같이 정의하고 다음과 ..

티스토리툴바