211017 일 Algorithms TIL

괄호변환

  • 프로그래머스 lev2
  • 동빈북 ch13 DFS/BFS 문제
    문제
    코드

문제풀이

  • 동빈북한테 배울 점
    • 완전괄호 형태를 찾을 때 나는 요소들을 stack에 넣고 빼면서 확인했는지 동빈북은 count라는 int변수를 증감시키면서 해결했다는 점
    • u, v로 분리할 때도 나는 left, right 변수를 줬는데 동빈북은 left 변수 하나로 증감시키면서 해결했다는 점
  • 똑똑이 풀이한테 배울 점
    • '('를 ')'로 혹은 그 반대로 바꾸는 과정에 대해서 나는
        u = u[1:-1]
        #똑똑이(solution2)풀이는 lambda를 이용해서 한줄로
        new_u = ''
        for c in u :
            if c == '(':
                new_u += ')'
            else:
                new_u += '('
        u = new_u
    • 똑똑이는
    list(map(lambda x:'(' if x==')' else ')',p[1:i])))

연산자 끼워넣기

문제
코드
동빈북자바

내 풀이

permutation으로 해줬다.
set을 안하면 통과 x인데
set 하면 통과

재귀로 풀었을 때랑 시간차이가 5배 정도 난다

동빈북풀이

  • 이거 재귀로 중복을 허용한 조합의 수를 구하는 방식
  • 이 풀이에 저번 문제에서 동빈북은 dfs로 순열 구하는 방식 이용했는데 같이 보면 좋을 것 같다.
def dfs(i, now):
        print("=============")
        global min_value, max_value, add, sub, mul, div
        print(i, add, sub, mul, div)
        if i == n:
            min_value = min(min_value, now)
            max_value = max(max_value, now)
        else:
            if add > 0 :
                add -= 1
                dfs(i+1, now + data[i])
                add += 1
            if sub > 0 :
                sub -= 1
                dfs(i+1, now - data[i])
                sub += 1
            if mul > 0:
                mul -= 1
                dfs(i+1, now * data[i])
                mul += 1 
            if div > 0:
                div -= 1 
                dfs(i+1, now // data[i])
                div += 1 
  • 이 풀이를 보면서 이렇게 되면 전역변수가 계속 바뀌어서 다음 turn에서 전역변수가 바뀌어야 하는 것 아녀? 했는데 아니다.
  • 재귀가 될 때 해당 데이터들을 복사해서 들고 가서 가능한 풀이같다. 자바에서는 어떤지 궁금하다. 풀어보고 싶다.

    전역변수일 경우,
    한 depth 들어갈때(Depth1) 복사본을 저장합니다. (데이터가 map1이라고 하겠습니다.)
    다음 depth 들어갈때(Depth2) 또 복사본을 저장하고 (map2) 나올때 복원하면 전역변수에 저장된 map2가 복원됩니다.
    depth1으로 나와서 다시 return 될때에는 전역변수의 값으로 복원할텐데 이미 Depth2에서 map2로 덮어써졌기 때문에
    다시 복원된 결과가 map2가 됩니다.
    https://www.acmicpc.net/board/view/19295

product 이용한 풀이가 있는데 잘 모르겠다.

감시피하기

파이썬 이중포문 빠져나오는 방법

https://stackoverflow.com/questions/653509/breaking-out-of-nested-loops

  • else: continue를 이용한다
for x in xrange(10):
    for y in xrange(10):
        print x*y
        if x*y > 50:
            break
    else:
        continue  # only executed if the inner loop did NOT break
    break  # only executed if the inner loop DID break

동빈북 풀이

  • 나는 dfs를 써보고자 combinations를 안쓰고 했는데 동빈북은 combinations를 사용했다.

인구이동

지금 풀이

일단 시간을 줄이는 방법에서 2가지가 있었다.
1. for문을 2번씩 while문으로 도는 것이 아니라 추가할 친구들만 넣어주는 것. 이번 초에서 변경이 안된 친구들은 다음판에 굳이 확인할 필요가 없다.

  • 만약 주변이 바뀌어서 나랑 그 주변에 차이가 경계가 열리는 범위 안에 들어간다고 해도 그 주변이 바뀐 친구를 검사하면서 포함될 것이다.
  • 주변도 하나도 안바뀌고 나도 안바뀌었으면 여전히 난 주변인들과 범위 차가 범위 안에 들지 않아 검사할 필요가 없다.
    그래서 아래 코드에 search()로 넣어 주었다.
  1. visited를 매 초마다 그래프를 생성하지 않고 방문한 초를 저장하도록 하면 이번판에서 방문 안한 친구들이 구분할 수 있다.

그런데 중요했던 건, 이 visited를 언제 처리해줄지에 따라서 답이 달랐다.

지금 풀이 자바

와 너무 오래걸렸어. 파이썬 푼 방법으로 풀면 안풀리고 그냥 동빈북 풀이 응용해서 풀었다. 파이썬 풀이는 도대체 왜 자바에서 안되는 것일까

옛날 풀이

  • 나는 DFS를 이용해서 풀었는데 그렇게 되면 런타임에러가 났다. 왜그런지 이렇게 저렇게 찾아보니 RecursiveError : maximum recursion depth exceeded while pickling an object 일 것이라고 생각했다.
  • https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=luiz4our&logNo=220642911892 여기를 보고
  • import sys
    sys.setrecursionlimit(10000)
  • 이를 작성하여 늘려줬더니 해당 부분은 통과했지만 시간 초과가 났다.
  • 이 문제는 Queue를 이용해서 풀어야 하나보다. 언제 DFS를 쓸지 고민이 된다.

좋은 웹페이지 즐겨찾기