코딩테스트

어려움이라고 적혀있어서 상당히 쫄아이거 얼마나 걸릴까 싶었지만 생각 정리해서 푸니까 금방 풀었다.약간 버블 sort와 비슷하다는 생각이 들었는데 결론적으로 누가 어디로 가는지 확인한 다음그 결과를 기반으로 얼마나 움직여야 하는지backtracking 하면 된다.  결과적으로 가야 하는 자리가 현재 자리에서왼쪽인지 오른쪽인지에 따라 swap 방향을 다르게 해 주면 된다.import sys# 입력 처리 단계n, m = list(map(int, sys.stdin.readline().split()))lines = []people = [i for i in range(1, n+1)]for _ in range(m): lines.append(list(map(int, sys.stdin.readline().split..

굉장히 시간이 오래 걸렸다 호호~~ 처음에는 1) 재귀를 통해 중복을 포함해 모든 경우의 수를 생성하고,2) 중복되는 경우의 수를 빼준다음3) sort를 한번 해주고 각각 이웃하는 선분을 비교했으나 시간초과가 걸렸다.  sort 해주는 것이 시간복잡도를 증가시키는 것 같아 그것을 제거했으나 여전히 시간초과...그래서 해설을 봤다. 여기에서는 중복을 포함해 모든 경우의 수를 생성하지 않고재귀를 두 가지 조건으로 돌려 문제 조건을 만족시켰다.  def recursion(cnt): global candidate if cnt == n: if len(line_bag) > candidate and not check_connect(line_bag): candidate = l..

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai재귀에 젬병이던 나에게 개념 정리를 해주는 문제가 나타났다.항상 마지막 return 할 때 값을 바꿔줄지, 값을 리턴할지어떤 조건으로 이어갈지, 배열에 값을 추가하고 빼낼 때 어떤 순서로 해야 하는지 헷갈렸는데 이 문제를 통해 조금이나마 확실하게 알게 되었다.사실 이 문제 해설을 한번 보고 다 닫은 다음에 다시 짜봤는데 연습이 되었다. 아름다운지 확인하는 부분에서 나는 같은 숫자가 나오는 전체 갯수를 세고 그것이 그 숫자로 나머지 없이 나눠지는 지 확인했는데, 해설을 보면 22222222의 경우 22 22 2..

이번주는 코드 트리로 공부를 조금 해봤다. 사실 이번주부터 시작인 줄 알고 들어갔으나 저번주부터였다는 사실을 알고 반성하며..확실히 커리큘럼대로 학습하니까 내가 너무 맨땅에 헤딩하는 느낌이었다는 것을 느꼈다.  시뮬레이션 2 - dx, dy techniquedx = [1, 0, -1, 0]dy = [0, 1, 0, -1]이렇게 설정해 두고 갖다 쓰는 방식인데 회전 방향이나 문제가 요하는 부분에 따라 유연하게 배열을 구성하면 된다. 예전에도 비슷한 유형의 문제를 이상하게 풀었던 기억이 있는데 도구가 하나 더 생긴 느낌이다. 완전 탐색 1, 2가끔은 복잡하게 생각하는 것보다 완전 탐색이 쉬울 때가 있다. 일단 완전 탐색으로 생각을 하고 만약 시간초과가 뜬다면 부가적인 부분을 덜어내는 것이 좋은 방법이라고 생..