저별이의 초보 코딩

https://www.acmicpc.net/problem/10815

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제입력

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제출력

1 0 0 1 1 0 0 1

코드 및 설명

import sys
input=sys.stdin.readline
n=int(input())
card=list(map(int,input().split()))
m=int(input())
card2=list(map(int,input().split()))
card.sort()
#이분탐색 시작
def search(target,line, st, ed):
    if st>ed:
        return 0
    mid=(st+ed)//2
    if line[mid]>target:
        ed=mid-1
        return search(target,line,st,ed)
    elif line[mid]<target:
        st=mid+1
        return search(target,line,st,ed)
    else:
        return 1
    return 0

num_card=[]
for i in card2:
    start=0
    end=n-1
    re=search(i,card, start,end)
    num_card.append(re)
for i in range(m):
    print(num_card[i],end=" ")

이 문제는 이분탐색으로 풀 수 있는 문제이다.

그래서 '이분탐색'이라는 개념을 알아야 풀기 수월하다.

일단 간단하게 '이분탐색' 개념을 알아보자

이분탐색은 오름차순으로 정렬된 리스트에서 탐색 범위를 절반씩 좁혀나가면서 데이터를 탐색하는 방법이다.

그래서 정렬된 리스트에 중간지점을 지정하고 목표 숫자와 비교해나가면서 탐색범위를 조절한다.

코드도 이를 반영해 보여준다.

주어진 리스트와 크기 정보들은 기본 입출력 부분이기에 설명을 생략한다.

함수를 호출하고 이에 대한 함수만 설명하려고 한다.

일단 특정한 숫자를 호출하기 위해서는 탐색할 범위를 지정해주어야 한다.

그래서 start와 end라는 변수를 통해 처음과 끝을 선언해주고 이를 바탕으로 함수를 호출한다. 

여기서 re는 함수가 리턴되었을 때 받은 숫자를 저장하려고 사용하였다.

그리고 이를 마지막 출력을 위해 리스트에 추가해주었다.

이분탐색을 위해 생성한 함수를 설명해보자면 일단 기준점, 즉 start 부분이 end를 넘어가게 되면 에러가 나고 더이상 숫자를 찾을 수 없는 것을 의미하기에 0을 리턴하게 하였다.

그리고 중간 위치는 start와 end를 더해 1/2로 나누어주면 찾을 수 있기에 매번 이를 활용하도록 하였다.

조건문을 이용하였는데 찾고자하는 숫자보다 중간지점이 크다면 중간지점보다 작은 범위에 있다는 것을 의미한다.

그래서 end부분을 중간지점-1로 설정해 주었다. 이 경우에는 시작점은 변화가 없다.

이 위치를 바탕으로 다시 함수 호출해서 숫자를 탐색한다.

찾고자하는 숫자보다 중간지점이 작다면 어떻게 될까??

그러면 중간지점보다 큰 범위에 있다는 것을 의미하게 된다. 그렇기 때문에 시작지점을 변경해주어야 한다.

start 부분을 중간지점+1로 설정한다. 반대로 이 경우에는 끝지점이 변화가 없게 된다.

여기에서도 역시 다시 함수 호출해서 숫자를 탐색한다.

만약 찾고자 하는 숫자와 중간지점이 같다면,

그대로 return 값을 1로 설정해주면 된다.

이렇게 이분탐색을 진행하면된다.

이분탐색이 개념만 볼 때에는 굉장히 쉬워보이지만 코드를 짤 때는 조금 어렵게 느껴지는 개념이라고 생각한다.

이분탐색을 활용해 문제를 푸는 연습을 많이 해봐야 좀 더 쉽게 접근할 수 있을 것 같다.

https://www.acmicpc.net/problem/13305

문제

어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다.

처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여 이동할 때 1km마다 1리터의 기름을 사용한다. 각 도시에는 단 하나의 주유소가 있으며, 도시 마다 주유소의 리터당 가격은 다를 수 있다. 가격의 단위는 원을 사용한다.

예를 들어, 이 나라에 다음 그림처럼 4개의 도시가 있다고 하자. 원 안에 있는 숫자는 그 도시에 있는 주유소의 리터당 가격이다. 도로 위에 있는 숫자는 도로의 길이를 표시한 것이다. 

제일 왼쪽 도시에서 6리터의 기름을 넣고, 더 이상의 주유 없이 제일 오른쪽 도시까지 이동하면 총 비용은 30원이다. 만약 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 3리터의 기름을 넣고(3×2 = 6원) 다음 도시에서 1리터의 기름을 넣어(1×4 = 4원) 제일 오른쪽 도시로 이동하면, 총 비용은 20원이다. 또 다른 방법으로 제일 왼쪽 도시에서 2리터의 기름을 넣고(2×5 = 10원) 다음 번 도시까지 이동한 후 4리터의 기름을 넣고(4×2 = 8원) 제일 오른쪽 도시까지 이동하면, 총 비용은 18원이다.

각 도시에 있는 주유소의 기름 가격과, 각 도시를 연결하는 도로의 길이를 입력으로 받아 제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다. 

출력

표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다. 

예제입력

4
2 3 1
5 2 4 1

예제 출력

18

코드 및 설명

import sys
input=sys.stdin.readline

n=int(input())
road=list(map(int,input().split()))
pay=list(map(int,input().split()))

money=0
now=pay[0]
for i in range(n-1):
    if pay[i]<now:
        now=pay[i]
    money+=now*road[i]
print(money)

일단은 그리디 알고리즘 문제이다.

문제 상으로 어떻게 그리디인지는 잘 모르겠지만 정리해보려고 한다.

이건 하다보면 알 수 있을 수도...

일단 입출력 빠르게 입력 받는 것 설정과 지점간 도로 길이와 지점 기름 가격을 입력 받는 것은 그렇게 어렵지 않다.

문제는 이 정보를 바탕으로 총 가격을 계산해주는 것이 중요하다.

money 라는 변수는 총 사용되는 기름 비용이고 now는 현재 가장 싼 기름 가격이다.

이후 for문을 돌리면서 탐색을 해준다.

만약 현재 위치의 기름 값이 기록된 기름값보다 싸다면 now라는 가장 싼 기름 가격으로 바꿔준다.

그 이후 혹은 if 상황에 적용되지 않는다면 이제 기름 비용을 계산해주면 된다.

현재 기름 값 선택한 결과와 도로길이를 곱해서 총 기름을 사용한 비용을 계산해주면 된다.

이렇게 과정을 짜는 것이 조금 어려운 문제라는 생각이 든다.

중앙동아리에서 2022-1학기부터 진행한 주식 자동매매기 개발

그리고 뒤엎기도 하고 본격적으로 뛰어든 것은 아마 여름방학 때 활동 재개하면서이다.

언제까지 메인 개발이 이루어질지 모르겠지만 이번 포스팅에서는 지금까지 진행한 내용을 정리해보려고 한다.

현재 진행하고 있는 개인적인 개발 부분은 아래 링크에서 볼 수 있다.

https://github.com/yujin37/Auto_Trading

여름방학 초기

분업화되기 시작했다. 여름방학 초기에는 기존 코드를 분석을 많이 했던 것 같다.

학기중에 바쁘다는 이유로 제대로 된 코드 분석을 하지 않고 봤기 때문에 제대로 보려고 했다.

구독 관련 기능을 진행하고 있었고 이 문제가 잘 해결되지 않아 애를 먹었었다.

여름방학 중기~

중간에 갑자기 개발 진행이 바뀌게 되었다. 좀더 간편하면서도 잘 진행되는 코드를 찾았기 때문이다.

기존에는 pyqt의 designer를 이용하지 않았기 때문에 하나하나 기능을 직접 배치를 진행해야 했다.

그리고 코드 역시 호출 방식으로 하는데 잘 되지 않았기 때문에, 그리고 이 과정을 잘 이해하지 못했기에 새롭게 개발하기로 하였다. 그래서 처음 부분인 매수, 매도부터 찾은 자료를 적용하여 개발하기 시작하였다.

그리고 이를 바탕으로 기존에 있었던 기능들과 적용할 수 있는 조건들을 파악하며 조절해 나가고 있다.

이전보다는 더욱 간편해졌고 어렵지만 조금은 나아가지는 것 같다.

다음 포스팅에서는 여름방학 때 진행한 기능들을 소개하도록 하겠다.