Dev/알고리즘
-
[프로그래머스] 완주하지 못한 선수Dev/알고리즘 2020. 10. 26. 10:04
문제: programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr ArrayList를 쓰면 효율성 테스트 실패 HashSet을 쓰면 문제 조건을 맞추지 못함(HashSet은 중복을 허용하지 않기 때문) HashMap에 completion의 모든 값을 키로 넣어주고, 그것의 갯수를 체크해 값에 넣어준다. 이후 participant 배열을 하나씩 검색해 HashMap에 해당 participant가 있는지 확인한다. 1..
-
[트리] 백준 트리 순회, 트리의 부모 찾기Dev/알고리즘 2020. 9. 8. 15:16
트리 순회(1991) https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net HashMap 구조로 데이터를 변환한 후, 차례로 전위, 중위, 후위 순회를 수행한 후 결과 StringBuffer를 출력했다. 전위, 중위, 후위의 차이는 해당 문자가 왼쪽 자식을 찾는 모든 과정 이전에 출력될 경우 전위, 왼쪽 자식을 찾는 모든 과정 이후 오른쪽 자식을 찾는 과정 이전에 출력될 경우 중위, 왼쪽 자식을 모두 찾고, 오른쪽 자식도 모두 찾은 이후 출력될..
-
[그래프] 백준 5214Dev/알고리즘 2020. 8. 27. 17:01
BFS를 사용해서 구현하되, 각 역간의 직선 연결로 할 시 java에서는 무조건 메모리 초과가 나게 되는 구조이다. C, C++에서는 최대한 심플하게 인접 리스트를 활용하면 가능할 것으로 보인다. 해결 방법은, 각 역간을 연결하는 정보(하이퍼튜브)를 따로 리스트를 만들어 관리하고 각 역은 해당 하이퍼튜브를 바라보는 방향으로 인접 리스트를 구현하고 Queue를 이용해 최종 역을 찾아가는 과정을 수행하면 되는데, 최종 결과 출력 시 하이퍼튜브에 방문했던 수는 제외하고 각 역 간을 방문했을 때의 숫자만을 가지고 최종 결과를 만들어야 한다. 하이퍼튜브 방문 횟수를 빼기 위해 애초에 count를 계산할 때 역->하이퍼튜브 방문이면 +를 하지 않고, 하이퍼튜브->역 방문일 경우 +하는 방향으로 계산했다. 큐에 모든..
-
[그래프] 백준 5567: 결혼식Dev/알고리즘 2020. 8. 27. 10:38
문제는 간단하게 기준이 되는 1번의 친구들, 그 친구들의 친구들까지 초대(목록에 추가)한다는 내용이다. BFS를 사용해서 구현했다. 트리 구조를 활용해 기준이 되는 1번을 level 0으로 잡고, 1번의 친구들을 level 1, 1번의 친구들의 친구들을 level 2로 잡고 level 2까지의 사람들만 count해서 결과를 출력하는 방향으로 구현했으며 level은 따로 배열을 생성해서 정해줬다. 소스 코드는 다음과 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5..
-
[그래프, BFS&DFS] 1260, 2606 문제 풀이Dev/알고리즘 2020. 8. 26. 17:36
두 문제 다 DFS와 BFS, 그래프에 대한 개념 문제라고 생각한다. 1260 문제 풀이 그래프는 인접 리스트, 인접 행렬로 나누어짐 인접 리스트는 각 원소 별로 인접해 있는 주변 원소들을 각 원소와 연결시킨 리스트로 표현하는 것. 인접 행렬은 배열을 선언해 전체 배열 중 인접 원소들을 true 변환하는 것이라고 볼 수 있음. 인접 행렬로 문제를 푼 결과는 해당 페이지에서 확인 가능하다. github.com/saturdayAlgo/acmicpc/blob/master/sw/java/p01260/array/Main.java saturdayAlgo/acmicpc Contribute to saturdayAlgo/acmicpc development by creating an account on GitHub. gi..
-
[백준] 1822 java 풀이법Dev/알고리즘 2020. 6. 26. 17:28
분류가 어떻게 되는지는 모르겠다. 일단 풀이 방법은 각 배열 aSet, bSet을 오름차순으로 정렬해주고, 정렬한 후 aSet을 bSet과 비교하며 aSet의 각 원소가 bSet의 비교 대상 원소보다 클 때에는 bSet의 포인터를 1 증가하고, bSet의 원소가 aSet의 원소보다 클 때에는 결과 셋에 저장하면서 aSet의 포인터를 1 증가, aSet의 원소와 bSet의 원소의 값이 동일하다면 두 포인터 모두 증가시키는 방법으로 수행했다. 예시를 가지고 설명한다면 4 3 2 5 11 7 9 7 4 에서 정렬을 하고 나면 2 5 7 11 4 7 9 가 될 것이고, 2부터 비교를 시작한다면 2 2를 결과 셋에 저장 후 aSet 포인터 1 증가, 5>4 => bSet의 포인터를 1 증가, 5 5를 결과 셋에 ..
-
[알고리즘] DFS와 BFS 정리Dev/알고리즘 2020. 6. 12. 01:53
DFS: Depth First Search 깊이를 우선으로 하는 검색 방법이다. 재귀 함수, 스택으로 구현한다. BFS: Breadth First Search 너비를 우선으로 하는 검색 방법이다. 큐로 구현한다. 위의 그림은 7을 찾아가는 과정을 DFS, BFS로 표현한 그림이다. DFS는 빨간색으로, BFS는 파란색으로 그려봤다. DFS는 tree의 level과 관계 없이 최상단(1)부터 각각의 leaf node까지를 찾아본 후, 다음 leaf node까지를 계속해서 검색하다 7이 나오면 종료한다. BFS는 같은 level의 node들을 모두 검색하고, 검색한 node들의 하위 node들을 검색하는 방식으로 작업이 수행된다. 그래서 DFS의 경우 5번, BFS의 경우 6번만에 7을 찾아 작업을 종료했다.