본문 바로가기

알고리즘63

[C++]백준 11657번 : 타임머신 www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만포드 알고리즘 적용문제. 벨만포드 알고리즘은 최단거리 구하기에서 음이 가중치를 핸들링할 수 있는 알고리즘이다. 음의 사이클이 생기면 최단거리를 구할 수 없고, 이 음의 사이클을 감지할 수 있다. 정당성은 다음과 같다. 음수 사이클이 없는 그래프에서 최단 경로가 한 정점을 두 번 지나는 일은 없다는 점을 떠올리면, 최단 경로가 포함하는 간선 수의 상.. 2020. 11. 9.
[C++]백준 11779번 : 최소비용 구하기 www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 기본적인 다익스트라 알고리즘 적용 문제 다익스트라 알고리즘은 하나의 정점에서 다른 모든 정점으로의 최단 거리를 구하는데 사용된다. 우선순위 큐를 사용하여 거리를 가중치로 두고 구현하면 시간복잡도 O(|E|log|V|)를 가진다. #include #include #include #include using namespace std; struct comp{ bool operator().. 2020. 11. 9.
[C++]백준 12094번 : 2048(HARD) www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 1. 접근 Easy버전과 다르게 10회 반복이어서 기저를 찾아내야 한다. map을 연산한 뒤에도 이전과 같은 모습이면 해당 탐색은 취소했지만 여전히 시간초과가 났다. 2. 풀이 접근에서 발견한 기저 외에 한 가지가 더 필요했다. 최종단계까지 간 경우 결과를 바탕으로 각 단계별 최소 기댓값을 배열에 저장한다. 이 후의 탐색에서 이를 활용하여 각 단계마다 map의 최대 값을 최소 기댓값.. 2020. 11. 4.
C/C++ 팁 1. Compare함수 - priority_queue struct comp{ bool operator()(type a, type b){ return a > b; } }; priority_queue pq; pq의 비교 함수는 구조체로 구현할 수 있다. pq는 heap 형태로써 a와 b는 각각 부모 노드, 현재 노드이며 조건에 맞을 시 교환이 이루어진다.(default : max heap) (즉 예시는 현재 노드 b의 값이 부모 노드 a보다 작으면 교환이 이루어지는 형태로 min heap 구현 코드이다) - sort #include ... bool comp(type a, type b){ return a > b } ... sort(vector.begin(), vector.end(), comp); algorit.. 2020. 11. 4.
[C++]백준 1111번 : IQ Test https://www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 1. 접근 수열의 패턴을 찾기 위해 a와 b를 기준으로 반복문을 통해 결과를 판별하고자 함 2. 틀린 이유 a와 b의 범위는 제한이 없기 때문에 불가능 따라서 수열의 형태를 기준으로 3가지 결론을 판별해야함 3. 풀이 1) 답이 하나 : 수열의 크기가 2이면서 같은 수, 수열의 모든 원소가 같은 패턴을 가질 경우 2) 답을 낼 수 없음 : 수열의 크기가 3이상이면서 처음 3원소로 구한 패턴에 맞지 않은 원소가 있는 경우(즉 패턴이 없는 수열인 경우) 3) 답이 여.. 2020. 11. 3.
[C++]백준 10800번 : 컬러볼 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 1. 접근 공에 대한 구조체로 벡터 배열을 만들고 크기 순으로 정렬한 뒤 반복문을 통해 현재 공까지 색이 다르고 사이즈가 작으면 총합에 크기를 더해 정답을 구했다. for(int i=1; i> N; vector v(N); vector acc(N); for (int i = 0; i > c >> s; v[i] = { i, c - 1, s, 0 .. 2020. 11. 3.
구현 팁 1. 배열에서의 시계방향, 반시계방향 bool map[SIZE]; // 원 형태의 map을 배열로 구현 int move; // 움직일 거리 int idx = 0; // map에서의 현재 위치 idx += move; if(idx >= 0) idx %= SIZE; // 시계, 반시계 방향으로 움직였을 때 else idx += SIZE; // 반시계 방향으로 움직였을 때 2. 최단경로 1) 다익스트라 : 하나의 정점에서 다른 모든 정점으로의 최단 거리 #include #include #include #include using namespace std; struct comp{ bool operator()(pair a, pair b){ return a.second > b.second; } }; int N, M, .. 2020. 10. 31.
SQL 팁 0. SQL query SELECT col FROM table WHERE condition 1. ORDER BY col1 DESC, col2 ASC, ... WHERE절 밑 2. LIMIT a, b : col [a, a+b] WHERE절 밑 3. COUNT(col) SELECT절 안에서 사용 EX) SELECT COUNT(col) EX) SELECT COUNT(*) AS NEW_NAME 4. DISTINCT(col) OR DISTINCT col SELECT절 안에서 사용 SELECT DISTINCT(col) SELECT COUNT(DISTINCT(col)) 5. GROUP BY GROUP BY col1, col2... : 그룹화하기 전, 특정 col 명시 이때 col은 기존의 col 혹은 AS로 만든 별.. 2020. 10. 22.
JAVA 팁(1) 0. 단축키 syso 입력한 후 Ctrl + Space : System.out.println(); 자동 완성 main 입력한 후 Ctrl + Space : main 문 자동 완성 try 입력한 후 Ctrl + Space : try-catch 문 자동 완성 for 입력한 후 Ctrl + Space : for 문 자동 완성 1. 입력 : 라인 단위로 읽어와서 잘라받는게 빠르다. import java.io.BufferedReader; import java.io.InputStreamReader; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); /* 한 라인이 띄어쓰기 없이 여러 개의 입력 값일 때 */ String str = b.. 2020. 10. 13.

티스토리툴바