알고리즘 공부 22일차

오늘은 설이라 친척들도 보고 가족들과 시간을 보내다 보니 이렇게 새벽에 밖에 시간이 나지 않았다. 설이지만 AI tech 2차시험이 코앞이라 더 열심히 해야한다. 그래서 남은 시간 최대한 많이 풀려 했지만 5문제 밖에 풀지 못했다. 프로그래서므 2단계를 계속 풀면서 느끼는 것은 난이도가 너무 천차만별인 것 같다. 심지어 아직 한문제는 구현을 끝내지 못했다. dfs를 이용해서 해결하고 싶은데 구현부분에서 지금 좀 버벅거리고 있다. 놓친 조건도 있는 것 같아 내일 더 제정신일 때 고쳐보려 한다.

그래서 오늘은 푼 문제 중 가장 시간이 오래 걸렸던 프로그래머스 교점에 점 만들기 문제를 풀어보려 한다.

https://school.programmers.co.kr/learn/courses/30/lessons/87377

프로그래머스

이 문제를 보았을 때의 아이디어는 직선이 주어졌을 때 교점을 구하는 함수를 짜고 그 교점이 정수일 경우 남겨 그림을 그리면 될 것 같았다. 그런데 생각보다 구현에서 신경써야 하는 것들이 좀 있어서 시간이 걸렸다. 아래는 내가 짠 코드다.

def meet(line1,line2):
    x=0.1;y=0.1
    if line1[0]*line2[1]-line1[1]*line2[0]!=0:
        x=(line1[1]*line2[2]-line1[2]*line2[1])/(line1[0]*line2[1]-line1[1]*line2[0])
    if line1[1]*line2[0]-line1[0]*line2[1]!=0:
        y=(line1[0]*line2[2]-line1[2]*line2[0])/(line1[1]*line2[0]-line1[0]*line2[1])
    return x,y

def solution(line):
    answer = []
    stars=set()
    result=[]
    for i in range(len(line)):
        for j in range(i+1,len(line)):
            x,y=meet(line[i],line[j])
            if x%1==0 and y%1==0:
                stars.add((x,y))
    for i in stars:
        result.append(list(i))
    result.sort()
    column=result[-1][0]-result[0][0]+1
    left=result[0][0]
    result=sorted(result,key=lambda x:x[1])
    row=result[-1][1]-result[0][1]+1
    up=result[-1][1]
    for i in result:
        i[0]-=left;i[1]=abs(i[1]-up)
    print(result)
    for i in range(int(row)):
        a=''
        for j in range(int(column)):
            if [j,i] in result:
                a+='*'
            else:
                a+='.'
            if j==int(column)-1:
                answer.append(a)
    return answer

좀 많이 지저분 하다. 일단 직선간의 교점을 구하는 식은 잘 기억이 안나 그냥 종이에 적어서 내가 도출해 낸 것이다. 만약 저 분모가 0이 된다면 두 직선은 평행한다는 것으로 교점이 발생하지 않는다. 그런 경우에는 x,y를 0.1이라는 실수로 보내 정수만 고르는 과정에서 거르도록 유도했다. 그 뒤로는 남은 별이 들어가는 좌표들을 이용해 구현했다. 여기서 많이 헷갈린 부분이 row와 column을 x,y좌표계에 대입하는 것이었는데 양수, 음수를 계속 신경써야 해서 많은 실수가 발생했다. 그리고 처음엔 "."로 필드를 채운 후에 *이 들어가야 하는 곳만 바꿔주려 했는데 str에서는 그런게 많이 힘들어 위에 구현한 것처럼 필드를 짤 때 조건문을 통해 *을 채워줬다.

 

오늘 공부를 하며 느낀것인데 나는 아직 bfs/dfs에 많이 약한 것 같다. 또 이코테에서 봤던 많은 방법들을 좀 잊은 것 같아 다시 복습을 해야겠음을 느꼈다. 내일은 오늘 못푼 문제와 dfs/bfs 문제 최단거리 문제를 풀어보아야 겠다.