알고리즘19 연산자 끼워넣기 (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. 가사 검색 (이진탐색/ binarysearch) 2020년 카카오 공채 문제중 하나인데, 시간이 꽤 걸렸고 문제를 일부분 제대로 안읽은 것을 뒤늦게 확인했습니다.. 검색문에 추가되는 ?는 접미사 혹은 접두사로만 포함되고 반드시 하나이상 포함됩니다. 문제는 찾으려는 query가 주어졌을때 존재하는 단어 리스트에서 ?를 포함해 존재하는 개수를 반환하는 것입니다. 각 쿼리에 대해 left, right를 찾아 개수를 구해주면 쉽게 구할 수 있고 처음에는 bisect_left, right를 사용하지 않았지만 사용시 보다 쉽게 풀 수 있습니다. (사용했었는데 처음에 문자열에 적용이 안된다고 나와서 그냥 구현으로 풀려 시도했습니다. 그런데 파이썬이 역시 그럴리가 없죠) 주의할 부분은 접미사 접두사에 따라서 문자를 뒤집어서 확인해줘야 올바른 사전순 탐색이 가능하기 .. 2021. 6. 14. 이전 1 2 3 4 5 다음