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를 사용했다.

인구이동

• 문제
• 옛날코드
• 시간초과 해결 못함 pypy로 풀었을 때 통과
• 두번째 풀었을 때 코드
• 시간초과 해결
• 동빈북풀이

지금 풀이

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

• 만약 주변이 바뀌어서 나랑 그 주변에 차이가 경계가 열리는 범위 안에 들어간다고 해도 그 주변이 바뀐 친구를 검사하면서 포함될 것이다.
• 주변도 하나도 안바뀌고 나도 안바뀌었으면 여전히 난 주변인들과 범위 차가 범위 안에 들지 않아 검사할 필요가 없다.
  그래서 아래 코드에 search()로 넣어 주었다.

2. 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를 쓸지 고민이 된다.