본문 바로가기

컴퓨터공학/자료구조&알고리즘

코딩테스트> 그래프 고급 탐색 ( 다익스트라, 크루스칼) 2021. 8. 29. 다익스트라 10282번 백준 아이디어 다익스트라로 시작점에서 모든 점의 최저 거리가 있는 배열을 만들고 지나가는 점과 가장 긴 거리를 골라서 출력 5719번 백준 아이디어 최단 거리로 나온 결과값은 빼고 거기서 또 최단 거리를 뽑는다. 다익스트라 이중 처리 다익스트라를 점검할 때 이전에 적용이 되었는지 조건문에 추가 최단 거리를 다 구하면 최단 거리 값에서 역순으로 경로를 찾는다. 경로를 찾아가면서 이전에 적용됐다는 표시를 한다. 크루스칼 1774번 백준 아이디어 우주신인지 뭔지 복잡하게 씌여있지만 크루스칼 알고리즘을 사용하면된다. 이 문제의 특징은 이미 연결되어 있는 간선이 있다는 점이다. 그리고 기존은 간선이 있는 그래프를 정렬하여 사용했지만 이번에는 모든 간선을 만들고 정렬하는 방법을 사용했다.
알고리즘> 그래프> 최소신장트리> 크루스칼 알고리즘 2021. 8. 28. 크루스칼 알고리즘 모든 간선을 리스트에 최소값부터 나열한다. 하나씩 뽑으면서 사이클이 생기면 빼고 사이클이 안 생기면 연결한다. 사이클 확인하는 법 Union find 알고리즘을 사용 각 노드의 루트 노드를 불러와서 같으면 사이클이 생긴다는 의미 다르면 연결한다. 합치는 방법 막무가내로 합치다가 최악의 상황이 다음처럼 될 수 있음.. 루트 노드 찾는데 N개의 노드 모두를 순례할 수 있음.. 효율적으로 하기위해 다음과 같은 방법이 사용된다. Union by rank 기법 각 트리 높이를 기억하고 union 시 두 트리 높이가 다르면 작은 트리를 큰 트리에 붙인다. 높이가 다를 경우 높이가 같을 경우 링크드리스트처럼 길어지게 만드는 게 아니라 차곡차곡 쌓이게 하는 과정이다. 따라서 N개 계산되는 것을 막고 ..
알고리즘> 피보나치 2021. 7. 26. 1. 재귀적 풀이법 엄청나게 간단하지만 단점은 수가 크면 클수록 시간 복잡도가 엄청나게 증가한다. 이 알고리즘의 원리는 원래 문제를 해결하기 위해서 작은 문제를 푸는 방식이다. 부분 문제(subproblem) 푸는 방식이자 재귀 풀이법이다. 문제는 작은 값을 만나기까지 계속 쪼개지면서 너무나도 부분 문제가 중복된다는 점이다. 위 그림을 보더라도 F(n-3)이 4번 나온다. 2. 동적 풀이법 각 부분문제를 해결할 때마다 그것을 저장하고 필요할 때마다 가져다 쓰면 되는 것 즉 동적 프로그래밍 성격이다.
코딩테스트> 그래프 기본 탐색 ( BFS, DFS ) 2021. 7. 20. 백준 1697번 if not 의미는 if not 다음에 False가 오면 실행한다는 뜻이다. 0은 False를 의미하므로 array_list 배열 안 값이 0이면 실행한다는 뜻 이 유형은 BFS 와 DFS 를 약간 변형해서 푼다. 따라서 BFS와 DFS의 구조를 외워야 한다. 핵심은 BFS는 0번째 요소를 뽑고, DFS는 마지막 요소를 뽑는 것 리스트가 오름차순이라면 순서가 뒤에서 앞으로 방향이다. 앞에서 뒤로 하려면 sort로 내림차순으로 정렬하고 마지막 요소를 뽑으면 된다. 2606번 백준 백준 1012번 백준 1325번
코딩테스트> 동적 프로그래밍 2021. 7. 12. 백준 1904번 수열 문제를 풀듯이 점화식을 세워서 푸는 문제 유형이다. 대부분의 문제가 그렇듯 나열을 하고 규칙을 찾아서 풀면 된다. 백준 12865번 처음에는 물건 가치의 최대값을 구하라고 해서 그리디 알고리즘을 이용하는 줄 알았다. 하지만 그리디 알고리즘을 사용하지 말아야 한다. 백준 11053번 백준 9251번 백준 1495번 백준 2655번 내가 쓴 답변 결과는 나오나 비효율의 극치인 것 같고 답이 틀리다고 나옴... 문제 푸는 원리는 같은데 말이지... 넓이 순서로 나열하고 순서를 깨지 않고 거기서 무게 순서대로 뽑는다는 원리는 맞게 접근했으나 최대값을 뽑는 동적프로그래밍을 어떻게 해야 할 지 아이디어가 떠오르지 않았음. 최대값을 가지고 역으로 뽑는 것도 떠오르지 않았음 원리를 이해하고 그걸 ..
코딩테스트> 고급 탐색 알고리즘 2021. 6. 28. 백준 2250번 백준 1939번 이것은 마치 다익스트라와 푸는 방식이 유사하다.. 처리하는 노드를 리스트에 넣고 하나씩 꺼내면서 인접한 노드값을 꺼내 방문한 적이 있는지 확인하고 방문한 적이 없으면 처리하는 리스트에 집어넣는 방식.. 깊이 우선 탐색과 연관되어 있다.. 백준 1927번 최소값을 구하는 것. 물론 sorted 를 이용하여 최소값을 뽑을 수 있지만 heap을 이용하면 쉽게 뽑을 수 있다. 백준 1715번 sorted를 이용하여 key 값에 기준을 잡고 그리디로 뽑을 수 있지만 heap으로 최소값을 뽑을 수 있다. 백준 1766번 위상정렬의 원리를 이용해서 풀면된다.. 부모에서 자식으로 관계를 설정할 때는 배열을 이용하고 자식에서 부모 연결 관계를 확인할 때는 차수를 이용한다.
알고리즘> 버블정렬, 선택정렬, 삽입정렬, 병합정렬 2021. 6. 28. 버블정렬 선택정렬 최소값을 선택해서 정렬한다 라고 기억하면 쉽다. 반복문이 두 개이므로 시간 복잡도는 삽입정렬 병합정렬
코딩테스트> 기본 탐색 알고리즘 2021. 6. 22. 백준 1543번 등호 부등호를 잘못써서 틀렸지만 고치니까 맞았다. 백준 1568번 백준 1302번 이렇게 하면 max 함수로 최대값이 나오긴 하는데 문제가 같은 값이 있을 경우이다. 그럴 경우 먼저 나온 값이 뽑힌다. a가 j 보다 알파벳이 앞에 있어도 먼저 들어간 j가 나온다. 위에는 print(bookList)를 임의로 넣어서 테스트해봤다. 해결책은 최대값을 따로 배열에다가 정리하고 sorted( ) 함수를 이용하여 알파벳 순서를 적용하는 것이다. 그런 다음 맨 앞에 값을 뽑으면 된다... 백준 1668 백준 1236 문자열을 각 글자마다 쪼개고 싶다면 list( 문자열 ) 이렇게 안에다가 넣으면 된다. 백준 2100

티스토리툴바