본문 바로가기

전체 글190

괄호변환 (구현, 재귀) 상당히 쉬운 문제인데 처음에는 문제를 보고 지나치게 쫄기도 했고(?) 문제를 잘못 읽어서 어디가 틀린거지 하고 꽤 오래찾은 것 같습니다. 문제는 u 문자열을 뒤집는 부분에서 저는 reversed 인줄 잘못 알고 있었던 것이었습니다. 문제에서 말하는 대로 재귀형태를 만들어 구현하면 쉽게 풀 수 있습니다. from collections import deque def checkCorrect(s): count = 0 for i in s: if i == '(': count+=1 else: if count == 0: return False count-=1 return True # st = deque() # for i in range(len(s)): # if s[i] == '(': # st.append(i) # el.. 2021. 6. 17.
연산자 끼워넣기 (dfs/ combinations/permutations) from itertools import permutations n = int(input()) nums = list(map(int,input().split())) plus, minus , mul, div = map(int,input().split()) operations = [] for i in range(plus): operations.append("+") for i in range(minus): operations.append("-") for i in range(mul): operations.append("*") for i in range(div): operations.append("/") per = list(permutations(operations,n-1)) mn = 1e9 mx = -1e9 def.. 2021. 6. 17.
인구이동 (bfs) 문제는 쉽다고 느꼈으나 정작 풀이시간에 꽤 많은 시간을 잡아먹었습니다. 저에게 구현 문제의 문제점은, 좀 쉬운 문제가 아니면 깔끔하게 풀리지 않고 몇 개의 테스트 케이스에서 꼭 예외결과가 발생하는데, 이럴때보면 구현에 항상 몇가지 잘못들이 있는 걸 발견하고 이걸 수정하는데 디버깅하면서 해결하느라 문제를 푸는데 시간이 제법 걸리는 것 같습니다. 오히려 이런 문제들은 공책에 써가며 처음부터 설계를 하고 예외가 생길 경우까지 생각해서 하는게 구현시간이 훨씬 빨라질 수 있을 것 같단 생각이 들었습니다. 대표적으로 이번 인구이동도 단순한 bfs를 응용한 문제이지만, 이중포문으로 visited처리를 하다보니 돌아서 연결되는 부분을 디버깅 도중에 발견하다던가, 처음 bfs에 넣을때 생기는 예외 조건들 처리 , 등 구.. 2021. 6. 17.
특정거리의 도시 (bfs/dfs) 어려운 문제는 아니지만 큐에 스타트를 넣고 진행하는 코드와 스타트 다음부터 시작하는 코드의 정오답 차이가 나서 이유를 한참 찾았습니다. 아직도 이유를 잘 몰라서 질문 게시판에 글을 올려놨는데 k가 0인것도 아닌데 어디서 오답이 나는 건지 너무 궁금하네요.. ->> 문제를 해결했습니다. 고민 결과 밑에 큐에 넣은 부분과 다른 부분이 어딘가 곰곰히 생각해봤더니, visited 부분을 append 할때 체크를 안한다는 점 같은 게 있었습니다. 해당 부분을 수정해 append 시 visited[i]!=1 일때를 조건으로 추가해주고 방문한 것도 visited처리를 해주면 올바르게 정답으로 출력됩니다. 이유가 뭘까 고민을 해봤더니, 그래프 그림과 다르게 생각해보면 1,2 1,2 이런 식으로 단방향 그래프는 맞지만 .. 2021. 6. 14.

티스토리툴바