분류 전체보기207 [BaekJoon 2252번] 줄 세우기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net [문제 설명] N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 .. PS/BaekJoon 2022. 10. 11. [Algorithm] 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 위상 정렬(Topology Sort)이란? 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 쉽게 이야기 하자면 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용합니다. 위상 정렬의 실생활 예시는 대학교의 선수 과목 구조를 예로 들 수 있습니다. 웹 프로그래밍 과목을 듣기 위해 컴퓨터 기초, 컴퓨터 프로그래밍 그리고 UNIX 시스템 과목을 먼저 들어야 합니다. 이렇게 순서가 있는 작업이 있을 때 작업을 정확하게 정렬해주는 위상 정렬 알고리즘을 사용합니다. 위 예시의 순서를 찾는다면 아.. Algorithm 2022. 10. 11. [BaekJoon 11659번] 구간 합 구하기 4(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net [문제 설명] 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에.. PS/BaekJoon 2022. 10. 2. [BaekJoon 1644번] 소수의 연속합(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [문제 설명] 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 .. PS/BaekJoon 2022. 9. 26. [BaekJoon 2003번] 수들의 합 2(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 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개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 .. PS/BaekJoon 2022. 9. 26. [BaekJoon 2230번] 수 고르기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net [문제 설명] N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M .. PS/BaekJoon 2022. 9. 22. [Algorithm] LCS(최장 공통 부분 수열) LCS(최장 공통 부분 수열)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! LCS(최장 공통 부분 수열)이란? '두 문자열을 비교할 때 공통적으로 나타나는 부분 문자열 중 가장 긴 것' 이해를 위해 예를 들어 "ACAYKP" 문자열과 "CAPCAK" 문자열이 주어졌다면, ACAYKP CAPCAK 두 문자열을 비교할 때 공통적으로 나타나는 부분 문자들 중 가장 긴 것은 ACAK이고 길이는 4입니다. LCS(최장 공통 부분 수열) 동작 과정(LCS 길이 구하기) 위에서 예를 든 "ACAYKP"와 CAPCAK" 문자열의 LCS 길이를 구한다면 어떻게 구해야할지 생각해봅시다. ↪ LCS는 다이나믹 프로그래밍을 이용하여 풀 수 있는데, 2차원 배.. Algorithm 2022. 9. 10. [BaekJoon 9655번] 돌 게임(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net [문제 설명] 돌 게임은 두 명이서 즐기는 재밌는 게임이다. 탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다. 두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다. [입력] 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000) [출력] 상근이가 게.. PS/BaekJoon 2022. 9. 9. [BaekJoon 2839번] 설탕 배달(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net [문제 설명] 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬.. PS/BaekJoon 2022. 9. 6. [Programmers Level3] 섬 연결하기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 .. PS/Programmers 2022. 9. 5. [BaekJoon 1197번] 최소 스패닝 트리(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net [문제 설명] 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. [입력] 첫째 줄에 정점의 개수 V(.. PS/BaekJoon 2022. 9. 5. [Algorithm] 크루스칼(Kruskal) 크루스칼 알고리즘에 대한 내용을 정리해보려고 합니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그리디 알고리즘으로 분류됩니다. 그렇다면 크루스칼 알고리즘에 대해서 생각해봅시다. 아래 그림과 같은 그래프를 가장 적은 비용으로 모든 노드를 연결하기 위해선 어떻게 해야할까요? 의외로 간단합니다. 간선의 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. ↪ 간선 정보를 오름 차순으로 정렬하고 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. 일단 위 그림과 같이 모든 간선 정보를 저장합니다. 노드 1번부터 7번까지의 모든 간선 정보를 저장한 것이고, 노드6.. Algorithm 2022. 9. 5. 이전 1 ··· 4 5 6 7 8 9 10 ··· 18 다음