본문 바로가기

Problem Solving15

[백준] 10451. 순열 사이클 (+파이썬 코드) Question. 백준 10451. 순열 사이클 Answer. cycle의 개수를 세는 문제이다. sol 1) 이 문제에서 배열의 번호(start node)와 배열의 값(destination node)을 이용해 graph를 만들었다. 위 문제에서는 인접행렬이나 인접리스트로 그래프를 만들 필요는 없어서 일차원 배열로 graph를 만들었다. 그리고 union-find를 통해 cycle의 개수를 구하면 된다. 1) 배열의 번호가 start node를 의미하고, 배열의 값이 destination node를 의미하는 1차원 배열의 graph를 만든다. graph = [0] + list(map(int, input().split())) 2) start node와 destination node의 parent가 같지 않.. 2021. 2. 15.
[백준] 11724. 연결 요소의 개수 (+파이썬 코드) Question. 백준 11724. 연결 요소의 개수 Answer. 프로그래머스의 "네트워크"랑 비슷한 문제여서 자세한 풀이는 생략한다. sohyunwriter.tistory.com/90 [프로그래머스] "네트워크" (+파이썬 코드) Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. b.. sohyunwriter.tistory.com sol 1) 인접리스트 + dfs 반복문 주의사항 1) sys.stdin.readline 써야 시간초과 안 남 2) dfs 돌릴 때, visited한 node.. 2021. 2. 15.
[프로그래머스] "네트워크" (+파이썬 코드) Question. 프로그래머스 깊이/너비 우선 탐색(DFS/BFS) > 네트워크 Answer. computers라는 인접행렬(adjacency matrix) graph가 주어지는데, 해당 graph에서 connected component가 몇 개인지 구하는 문제이다. bfs로 풀 수도 있고, dfs로 풀 수도 있다. 주어진 인접행렬을 이용해 DFS로 풀면 다음과 같다. sol1) 인접행렬 + dfs 1) i번째 노드를 방문하지 않았다면, 스택에 i번째 노드를 넣는다. 2) stack의 요소를 하나씩 pop 하며 visited 배열에 해당 노드를 true 처리한다. 3) 해당 노드와 연결된 노드들 중 방문하지 않은 노드들을 스택에 넣어준다. ---> dfs 함수 부분 4) 1~3을 n개의 노드에 대해 반복.. 2021. 2. 14.
여러 좌표가 주어질 때 이쁘게 별(*) 찍기 오늘 코딩테스트를 보다가 오랜만에 '별 찍기' 문제를 보게 됐다. 해당 문제에서 좀 까다로웠던 부분만 하위 문제로 새롭게 만들어봤다. Q. 여러 좌표가 주어질 때 이쁘게 별(*) 찍기 (-1, 0), (1, 0) 과 같은 좌표가 주어지면, 주어진 좌표는 '*'로 표시하고, 나머지는 '.'로 표시한다. 즉, ['*.*'] 로 출력한다. 물론 board의 크기 제한은 없지만, ['...', '*.*']로 출력하면 안 된다. 즉, '...'는 굳이 필요 없으므로 제거한다. 별로 어렵지 않은 문제인데, 구현을 어떻게 하면 간단히 할까라는 생각을 시험 끝나고 생각해보다가, 다음과 같이 함수화시켜봤다. points_to_star 함수는 점들이 주어지면 해당 점들에 대해 '*'로 board에 표시해주는 함수다. 코드.. 2021. 2. 7.
[백준] 2748. 피보나치 수 2 - 문제 풀이 (+파이썬 코드) Question. 백준 2748. 피보나치 수 2 Answer. 사실 이 문제는 파이썬에서는 "백준 2747. 피보나치 수" 문제와 동일하다. 파이썬은 int, long 구분을 할 필요가 없고, 숫자가 아무리 커져도 다 담을 수 있기 때문에 2747번에 pass한 코드를 그대로 제출하면 된다. 그러나 cpp, java의 경우 long long 등으로 선언해, 피보나치 수의 값이 int 범위를 넘어갈 경우에도 해당 값을 담을 수 있도록 해야 pass 한다. 아래 파이썬 코드는 [백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드)과 동일하다. sol 1) recursion with memoization # recursion with memoization # time complexity : O(N).. 2021. 2. 5.
[백준] 2747. 피보나치 수 - 문제 풀이 (+파이썬 코드) Question. 백준 2747. 피보나치 수 피보나치 수열을 구현하는 문제이다. 예전에는 면접 질문으로도 자주 나왔다고 하는데, 요즘은 쉬워서 잘 안 나오는 것 같다. 다만, '피보나치 수를 구현하는 모든 방법은?', '피보나치 수를 각각 반복법, 재귀로 구현해보면?' 이런 식으로 물어볼 수는 있겠다. Answer. 피보나치 수열을 구현하는 방식은 크게 3가지가 있는데, 1) 재귀 2) recursion with memoization 3) for문 이용해 구현 하지만 이 문제는 1)의 방식대로 재귀로 풀면 '시간초과'가 난다. O(N)에 풀어야 하는 문제이기 때문에, 재귀로 풀 경우, memoization을 해야 한다. sol 1) recursion with memoization 재귀로 구현하되 mem.. 2021. 2. 5.
728x90

티스토리툴바