전체 글 (87) 썸네일형 리스트형 [파이썬 문법] 나는 재귀를 안 썼는데 왜 recursionError가? 최근 백준 문제를 풀다가 좀 편하게 짜려고 이상한 코드를 하나 짰었다.백준 게시판에 질문도 했었는데 아무도 답이 없었고, 이상한 짓이 굉장히 하고싶어지는 시험기간의 영향으로 해결하게 된 문제이다. 문제는 요약하면 문자열 여러개가 주어지고 배치되는 순서가 주어지면 그거에 맞춰서 문자열을 배치하면 되는 문제이다. n이 50만이나 되고, 문자열 길이의 총합도 50만까지 가능하다. 따라서 일반적으로 문자열을 합치는 방식으로 풀게된다면 시간 초과가 나게 된다. 그 이유는 파이썬 문자열 연산은 최종적으로 완성되는 문자의 길이만큼의 시간이 소요된다. 조금 깊게 가보면 파이썬 문자열은 "불변성"을 갖고, 뒤에 추가되는 것이 아닌 불변하는 여러개의 문자열에서 문자를 긁어와 새로운 문자열을 만드는 것이기 때문이다.a라는 .. 백준 9663 NQueen 파이썬으로 다양하게 풀어보기 1년에 한두번씩은 꼭 푸는 것 같은 NQueen 문제, 옛날 풀이부터 차근차근 한번 되짚어 보자, 기본적인 틀은 다 같다. 백트래킹을 사용하며, 한 행을 기준으로 백트래킹을 진행하며, 가능한 위치를 찾아 퀸을 배치한다. 0. 배치할 수 있는지 8방향 탐색해서 판별하는 경우배열에 퀸을 놓고, 현재 놓을 위치 기반으로 8방향을 탐색해서(6방향만 탐색해도 문제 없다, 왜냐하면 한 행에는 하나의 퀸만 놓을 수 있기 때문에) 퀸이 존재한다면 불가능할 것이고, 퀸이 존재하지 않는다면 가능할 것이다.노란색이 이미 배치된 퀸이고, 주황색에 배치가능한지 판별하려 했을 때 저 8방향을 모두 탐색해서 다른 퀸이 존재하는지 아닌지 판별한다.존재한다면 넘어갈 것이고, 존재하지 않는다면 배치할 것이다.불필요한 탐색이 굉장히 많다.. 코드포스 블루 달성! 이번에 그렇게 잘 풀었다고 생각 안했는데 운좋게 블루에 올라갈 수 있었다. ( 드디어..! ) 그래프는 "그 1년반"을 제외하면 꾸준히 우상향,, 아마 졸업 전까지 퍼플까지 노려보지 않을까 싶다. 지금까지 꾸준히 블루퍼포가 나오고 있어서 고점이 터진다면 충분히 가능하지 않을까 싶다. 색깔 참 이쁜 것 같다. 이전 1 2 3 4 ··· 29 다음
