18870번: 좌표 압축

18870번:  좌표 압축사용 언어: C++ 풀이 실제로 값들을 비교해서 푸는게 아니라, 값들을 받아서 정렬 후 (중복값도 빼주면서), 정렬하지 않은 배열의 원소가 정렬된 배열의 몇 번째 인덱스인지 알아내면 그 값이 그 원소가 다른 몇 개의 원소보다 큰지 개수다.#include using namespace std;int main(){ ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; int A[N]; for(int i=0; i> A[i]; } vector C; for(int i=0; i

1978번: 소수 찾기 (BOJ C++)

1978번: 소수 찾기 사용 언어: C++ 풀이 아래의 코드는 O(n)이지만, O(루트n)에 코드를 짤 수 있다. 해당 숫자의 루트 n까지만 확인하면 된다는 사실을 사용하는 것이다. for(int i=2; i*i> num; bool flag; while(num--) { int isPrime; flag = true; cin >> isPrime; if(isPrime == 1) continue; for(int i=2; i

1259번: 팰린드롬수 (BOJ C++)

1259번: 팰린드롬수 사용 언어: C++ 풀이 #include #include using namespace std; int main(void) { ios::sync_with_stdio(0); cin.tie(0); stack stack; while(1) { string a; cin >> a; if(a == "0") break; if(a.length() == 1) { cout

2096번: 내려가기 (BOJ C++)

2096번: 내려가기사용 언어: C++ 문제 N줄에 0 이상 9 이하의 숫자가 세 개씩 적혀 있다. 내려가기 게임을 하고 있는데, 이 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다. 그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 제약 조건이 있다. 바로 아래의 수로 넘어가거나, 아니면 바로 아래의 수와 붙어 있는 수로만 이동할 수 있다는 것이다. 이 제약 조건을 그림으로 나타내어 보면 다음과 같다.별표는 현재 위치이고, 그 아랫 줄의 파란 동그라미는 원룡이가 다음 줄로 내려갈 수 있는 위치이며, 빨간 가위표는 원룡이가 내려갈 수 없는 위치가 된다. 숫자표가 주어져 있을 때, 얻을 수 있는 최대..

1504번: 특정한 최단 경로 (BOJ C/C++)

1504번: 특정한 최단 경로 사용 언어: C++ 풀이 //1번 정점에서 시작, n번 정점으로 이동. //시작 정점이 주어지고 최단경로이므로 다익스트라 알고리즘을 활용하면 된다. //주어진 두 정점을 반드시 거쳐야한다. 만약 a, b 정점을 거쳐야한다면 // 1 -> a -> b -> n or 1 -> b -> a -> n 두 가지 경우만 구하면 된다. // 그러면 a와 b 각각에서 다익스트라를 돌리면 모든 값을 구할 수 있다. -> 다익스트라 두 번만 돌리면 된다. #include #include #include #include #define INF 1e9 using namespace std; int n, e; //n: 정점 개수, e: 간선 개수 int v1, v2; //거쳐야하는 정점 v1, v2 ..

1753번: 최단경로 (BOJ C/C++)

1753번: 최단경로 사용 언어: C++ 풀이 //우선 순위 큐를 이용한 다익스트라 알고리즘으로 최단경로 구하기 #include #include #include using namespace std; #define INF 1e9 int v, e, start; //V: 정점의 개수, E: 간선의 개수, start: 시작 정점의 위치 vector arr[20001]; //각 노드가 연결된 노드 정보 저장 //1번째 노드가 3번째 노드에 연결되어있다를 표현하려면 arr[1] int dist[20001]; //최단 거리 정보 저장 void dijkstra(int start) { priority_queue pq; // pq.push({0,start}); dist[start] = 0; while(!pq.empty()..

1149번: RGB거리 (BOJ JAVA)

1149번: RGB거리 사용 언어: JAVA 문제 RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다. 집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자. 1번 집의 색은 2번 집의 색과 같지 않아야 한다. N번 집의 색은 N-1번 집의 색과 같지 않아야 한다. i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다. 입력 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 ..

1043번: 거짓말 (BOJ JAVA)

1043번: 거짓말 사용 언어: JAVA 풀이 파티에서 진실을 아는 사람을 좀비라 생각하고, 좀비와 같은 파티에 간 사람은 감염된다고 생각했다. 이 문제에 다시 와서 parent 함수, find-union으로 더 간단한 풀이를 만들어야겠다. //진실을 아는 사람(좀비)과 같은 파티에 있던 사람은 감염된다. import java.util.Scanner; public class Main{ static int[][] party; static int[] arr; static int[] arr2; public static void check_infect(int N, int M){ //N: how many people, M: party for(int i=0; i