목록분류 전체보기 (104)
개발자 김수진
[문제] www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [풀이] 표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다. 그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다. 이 구간의 합을 구해서 출력하면 된다. 처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다. 당연히 시간초과가 나왔고 다른 방법을 찾아봤다. 찾아보..
[문제] www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net [코드] N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다. 이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다. 학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다. Degree에 각 노드에 대한 연결 차수를 저장하고 연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다. [풀이] 시간 : 44ms..
[개념] 위상 정렬이란 ? 위상 정렬(Topology Sort) 알고리즘이란 순서가 정해진 작업을 차례대로 수행해야 할 때, 순서를 결정하기 위해 사용하는 알고리즘이다. 하나의 노드에 들어오기 위해 필요한 노드의 개수를 '진입차수'라고 한다. 위의 예제에서 보면 2번 노드의 진입차수는 13,7에 의해 2가 된다. 위상 정렬은 방향 그래프에서 진입차수가 0인 노드가 하나 존재해야 된다. 그리고 해당 노드가 위상 정렬의 시작 노드가 된다. 위상 정렬은 진입차수가 0인 노드를 시작으로 순서대로 queue에 넣어준다. 하나의 방향 그래프에서 여러 가지의 위상 정렬이 가능하다. 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐에서 꺼내고 해당 노드에 부속된 간선 삭제 1,2번을 계속 반복해가면서 모든 노드가 선..
[문제] programmers.co.kr/learn/courses/30/lessons/49994# 코딩테스트 연습 - 방문 길이 programmers.co.kr [풀이] 입력으로 움직이는 방향이 주어지고 이에 알맞게 움직이면 된다. 걸어간 길의 길이를 출력하면 된다. 단, 이미 지나왔던 경로는 포함하지 않는다. 또한 범위를 벗어나는 경우 움직이지 않는다. 따라서 좌표와 방향을 가지고 visited 배열을 사용해 이미 방문한 길은 포함하지 않도록 하였다. 문제에서 범위가 -5부터 5까지인데 배열은 index가 0부터 가능하므로 (0,0) ~ (10, 10)으로 변경했다. [코드] #include #define MAX 11 using namespace std; int solution(string dirs) ..
[문제] www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [풀이] DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다. bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다. 연산은 아래와 같이 3가지 연산이 있다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다. [코드] 시간 : 4ms #include #define MAX..
[개념] 구간 합을 구할 때 사용되는 알고리즘으로 배열의 길이가 짧은 경우 이중 for문을 사용해서 구하면 되지만 배열의 길이가 길어지면 시간 초과가 발생하므로 투 포인터 알고리즘을 사용한다. 아래 코드에서 보면 N은 배열의 크기, M은 구하고자 하는 합이다. 구간의 합이 M을 만족하는 경우의 수를 구한다고 하자. start, end 모두 배열의 첫번째부터 시작한다. - M = sum 구간의 합이 M과 같다면 경우의 수 total에 1을 추가한다. 그리고 end를 한칸 뒤로 움직인다. - M < sum 현재 구간의 합이 구하고자 하는 구간의 합보다 크다면 start를 1씩 증가시켜 주면서 구간의 범위를 좁혀준다. 이 때 start가 end보다 커지게 되는 경우 start, end를 같은 위치로 처리한다...
[문제] www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net [풀이] N,M이 주어지고 길이가 N인 배열에서 구간합이 M인 경우의 수를 찾아서 출력하는 문제 구간합 문제길래 이중 for문을 사용해서 풀려고 했다. 하지만 시간 제한이 0.5초인데 M의 범위가 1부터 3억이라서 이중 for문을 사용하면 시간초과가 발생한다. 따라서 구간합 구하는 알고리즘인 투 포인터 알고리즘을 사용해서 풀었다. start , end 를 배열의 첫번째 ind..
[개념] 크루스칼 알고리즘은 모든 노드들을 최소 비용으롤 연결하는 알고리즘이다. N개의 노드를 N-1개의 간선으로 연결 ex) 모든 도시를 도로로 연결할 때 가장 적은 비용으로 연결하는 방법 1. 노드 간의 연결 정보를 저장하고 비용을 기준으로 오름차순으로 정렬한다. 2. 비용이 적은 것부터 연결 이 때 사이클이 발생하지 않도록 주의 ==> Union-Find 를 사용해 확인, 노드를 연결할 때 부모가 같다면 이미 연결된 것이므로 제외 3. 현재 간선을 현재 MST 집합에 추가 아래 그림과 같이 가중치를 기준으로 오름차순으로 정렬한다. 가중치가 작은 것부터 선택하여 노드를 서로 연결한다. 해당 예제에서는 2번 노드와 5번 노드를 연결한다. (아래 그림에서 방향 그래프로 그렸는데 잘못 그렸습니다. 크루스칼..