알고리즘/알고리즘
-
투 포인터 알고리즘알고리즘/알고리즘 2021. 1. 20. 18:13
시간이 없어 상당히 날림으로 썼으며, 생각나면 수정할 예정 programmers.co.kr/learn/courses/30/lessons/67258 투 포인터 알고리즘 배열에 시작점/끝점 포인터를 설정하고 포인터들을 이동시켜가면서 부분 배열을 비교하며 원하는 결과를 도출한다. 백준2003 - 수들의 합2 문제 (www.acmicpc.net/problem/2003) N개의 수로 이루어진 수열 A에서 A[i]~A[j]의 합이 M이 되는 모든 경우의 수를 구하는 문제다. 즉 부분 수열이 M이 되는 모든 경우의 수를 구하는 것이다. 가장 쉽게 생각할 수 있는 것은 3중 for문을 사용하는 것이다. 모든 수열의 크기에 대해 시작점을 바꿔가며 전부 선형으로 비교해보는 것이다. // 초기 입력 int n = scann..
-
(java) DFS로 순열 구하기알고리즘/알고리즘 2021. 1. 19. 14:38
DFS(Depth First Search)를 사용해서 순열 만들기 https://programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 문제를 해결하던 중 [+. -. *] 을 포함한 모든 경우의 수가 필요했다. 그래서 DFS를 이용한 순열을 구현해보았다. 아래 두 필드는 클래스(전역) 필드이다. ArrayList permutedOps = new ArrayList(); // 기호들을 담고 있는 리스트를 만들어야 하기 때문에 이중..
-
위상정렬 (Topological Sorting) (백준 3665 최종순위)알고리즘/알고리즘 2021. 1. 15. 10:37
순위를 찾거나, 선수과목(prerequiste) 구하기등 순서가 중요할 때 사용할 수 있다. 백준 3665 최종순위는 위상정렬을 사용해 풀 수 있다. 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬이란? 방향 그래프에 존재하는 정점들의 순서를 구하는 알고리즘이다. 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 순서를 구할 때 선행조건이 지켜져야 한다. (A를 하기 위해 B가 선행되야 한다 등의 조건들) 그러나 최종 순위처럼 한 가지 결과를 원할 때는 조건을 걸어서 2개 이상의 결과가..