https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. Logic - 기본 다익스트라 문제이다. 문제에서 나온대로 한 정점에서 모든 정점으로의 최단 경로를 구하는 다익스트라 알고리즘을 사용하면 풀 수 있다. 다 돌고 배열에서 값만 하나씩 출력해주면 되는 문제 2. Code #include using namespace std; const int INF = 10000000; // 시작 노드에서 해당 노드까지의 경..
Programmers
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 1. Logic - 다익스트라는 한 정점에서 모든 정점으로 가는 최단경로를 구하는 알고리즘이다. 이 문제는 한 정점에서 모든 정점으로 가는 최단거리 + 다시 집에가는 최단거리 두개를 구해서 더해야 한다 2. Code #include using namespace std; const int INF = 987654321; //최소 비용 배열 int d[1001]; vect..
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 1. Logic > 기본 DFS / BFS문제 Depth First Search(DFS) - 재귀를 사용하며 자기 자신을 호출하여 깊게 들어가며 노드를 확인하며 검색한다. - DFS를 구현할 때 주의해야할 점은 탐색한 경우 방문처리를 하여 다시 들어가지 않도록 하여 무한루프에 빠지는 것을 필히 방지하여야 한다. 기저조건을 잘 파악하고 방문처리를 해야한다. Br..
https://www.acmicpc.net/problem/2785 2785번: 체인 희원이는 그의 다락방에서 N개의 체인을 찾았다. 각각의 체인은 몇 개의 고리로 연결되어 있는데, 각각의 고리는 최대 두 개의 인접한 고리를 가질 수 있다. 각각의 고리는 열고 닫을 수 있다. 그 www.acmicpc.net 1. Logic - 부분 문제로 나눠서 생각을 해봤을 때 1. 원래 있는 체인을 사용해서 연결하는 경우 2. 서로 끝부분끼리 연결하는 경우 이렇게 두가지로 나누어진다고 생각했다. 원래 있는 체인을 사용하는 경우 연결하는 부분의 갯수가 체인의 길이를 넘게 되면 항상 비효율적으로 사용하기 때문에 사용하는 기존 체일을 제외한 갯수와 사용하는 체인의 갯수가 똑같아야만 한다. 서로 끝부분끼리 연결하는 경우 갯수..
https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 1. Logic - 문제를 보자마자 %, / 연산자를 활용하여 어떻게 만들면 되겠다는 생각을 했지만 항상 마지막 자리수를 따지기 때문에 문제와 맞지 않은 사고였다. - 1의 자리부터가 아닌 앞의 자리부터 잘라야된다는 생각을 했고 주어진 n에서 자릿수를 10씩 늘려가면서 빼면 각 자릿수를 가진 숫자들이 나오게 된다. 2. Code #include using namespace std; int main() { int n; int sum = 0; cin >> n; for(int i = 1; i
https://school.programmers.co.kr/learn/courses/30/lessons/12980# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 짝수일 때에는 2로 나눠주고 홀수일 때에는 -1을 해주고 2로 나눠준다. 2. Code #include using namespace std; int solution(int n) { int ans = 0; while(n) { if(n % 2 == 1) ans++; n /= 2; } return ans; } 3. Feedback 처음 문제를 보고 아래의 코드와 같이 코딩을 했지만 i..
https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 1. Logic - 주어지는 문자열의 갯수가 최대 50이니 시간복잡도를 계산해 봤을때 각 자리수에서 1씩 증가하며 뒤에 붙히고 팰린드롬을 확인하는 최악의 경우의 수를 생각해도 50 * 50 * 50 정도일 것이라고 생각해서 2초안에 충분히 돌 수 있다고 판단함. > 전부 확인해 보기 - str[0]부터 1씩 증가해가며 str의 뒤에 붙히고 팰린드롬인지 확인하기 2. Code #include using ..
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 1. Dynamic programming(동적 계획법) - 하나의 큰 문제를 작은 문제로 나누어 푸는 방법 - 재귀로 풀게되면 계산했던 경우의 수도 한번 더 하기 때문에 메모이제이션(Memoization)을 통해 계산한 값을 배열에 저장하고 다음 호출때 이전에 계산했던 값을 만나게 되면 계산하지 않고 값을 불러와서 사용함. - 시간복잡도를 현저히 줄일 수 있음. 2. Logic 1. 조건에 맞춰 3가지 분기를 만든다. 2. 완성된 수가 주어지기 때문에 주어진 수에서 1로 만들어가며 실행한다 3. 기저조건은 수가..
