전체 글207 [BaekJoon 1920번] 수 찾기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net [문제 설명] N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. [입력] 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1],.. PS/BaekJoon 2022. 8. 31. [Algorithm] 이분 탐색(Binary Search) 이분 탐색에 대한 내용을 정리해보려고 합니다. 이분 탐색 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다. 이분 탐색을 사용해야하는 이유 ? 우리가 일반적으로 알고있는 선형 탐색의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 시간 복잡도는 배열의 원소의 개수 만큼(O(n))이 됩니다. 만약 원소의 개수가 무수히도 많아진다면 굉장히 비효율적인 알고리즘이 되겠죠. 하지만 이분 탐색은 탐색 범위를 절반으로 나누어서 탐색하기 때문에 시간 복잡도는 O(log n)로 탐색이 가능합니다. 이분 탐색 동작 이분 탐색의 동작을 알아보도록 하겠습니다. 예를 들어서 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15} .. Algorithm 2022. 8. 31. [BaekJoon 2011번] 암호코드(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net [문제 설명] 상근이와 선영이가 다른 사람들이 남매간의 대화를 듣는 것을 방지하기 위해서 대화를 서로 암호화 하기로 했다. 그래서 다음과 같은 대화를 했다. 상근: 그냥 간단히 암호화 하자. A를 1이라고 하고, B는 2로, 그리고 Z는 26으로 하는거야. 선영: 그럼 안돼. 만약, "BEAN"을 암호화하면 25114가 .. PS/BaekJoon 2022. 8. 30. [BaekJoon 1629번] 곱셈(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net [문제 설명] 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. [출력] 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. [입.. PS/BaekJoon 2022. 8. 29. [BaekJoon 18352번] 특정 거리의 도시 찾기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net [문제 설명] 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호.. PS/BaekJoon 2022. 8. 29. [BaekJoon 1717번] 집합의 표현(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net [문제 설명] 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. [입력] 첫째 줄에 n.. PS/BaekJoon 2022. 8. 28. [Algorithm] 유니온 파인드(Union-Find) 그래프 알고리즘 중 Union-Find 에 대해서 공부한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 유니온 파인드(Union-Find)란? 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속해있는지 판별하는 알고리즘입니다. 그래프에서 사이클이 존재하는지 여부를 판별할 때 유용하게 사용됩니다. 유니온 파인드(Union-Find) 그림 설명 위 그림과 같이 여러개의 노드가 모두 연결되지 않고, 자기 자신만을 집합의 원소로 가질 때 모든 값이 자기 자신을 가르키도록 합니다. 그리고 표를 보면 i는 노드 번호, parent[i]는 부모 노드 번호를 의미합니다. 즉, 자기 자신이 어떤 부모에 포함되어있는지를 의미합니다. 자 이제, .. Algorithm 2022. 8. 28. [Programmers Level2] 큰 수 만들기(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주.. PS/Programmers 2022. 8. 26. [Programmers Level2] 배달(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [문제 설명] N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 .. PS/Programmers 2022. 8. 25. [BaekJoon 11779번] 최소비용 구하기 2(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net [문제 설명] n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 .. PS/BaekJoon 2022. 8. 25. [Algorithm] 다익스트라(Dijkstra) 다익스트라 알고리즘을 공부한 내용을 바탕으로 작성한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 다익스트라(Dijkstra)란? 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 중 하나입니다. 도착 정점뿐만아니라 다른 모든 정점을 방문하며 각 정점까지의 최단 경로를 찾게됩니다. 동작 과정 1. 출발 정점과 도착 정점을 정합니다. 2. '최단 거리 테이블'을 초기화합니다. 3. 현재 정점에서 인접한 정점 중 방문하지 않은 정점들을 구별하고 방문하지 않은 정점들 중 가장 최단 거리의 정점을 선택합니다. 4. 해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려하여 최단 거리를 업데이트합니다. 5. 3~4번을 반복합니다. 동작 예시 출발 정점은 .. Algorithm 2022. 8. 23. [BaekJoon 1753번] 최단경로(C++) ※주의※ 저의 풀이가 정답은 아닙니다. 다른 코드가 더 효율적이거나 좋을 수 있습니다. 언제나 다른 사람의 코드는 참고만 하시기 바랍니다. [문제 풀이 사이트] 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net [문제 설명] 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. [입력] 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, .. PS/BaekJoon 2022. 8. 22. 이전 1 ··· 5 6 7 8 9 10 11 ··· 18 다음