본문 바로가기

자료구조

 (64)
2225번 합분해 https://www.acmicpc.net/problem/2225 풀이 코드import sysimport mathN, K = map(int, sys.stdin.readline().split())CONST_DIV = 1000000000print(math.comb(K + N - 1, N) % CONST_DIV)
30804번 과일 탕후루 https://www.acmicpc.net/problem/30804    1번 풀이import sysn = int(input())fruits = list(map(int, sys.stdin.readline().split()))res = 0def findRes(p1, p2): maxRes = cnt = 0 countFruits = [0] * n for i in range(n): if fruits[i] == p1 or fruits[i] == p2: countFruits[i] = 1 for i in range(n): if countFruits[i] > 0: cnt += 1 else : cnt = 0 maxRes = max..
9019번 DSLR https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net bfs 문제이다. 모든 경우의 수를 완전탐색 해주면 된다. 1. D -> 2n mod 10000 2. S -> (n - 1) (n % 1000) * 10 + n / 1000; 4. R -> (n % 10) * 1000 + n / 10; #include #define all(v) v.begin(), v.end() #define INF 2e..
1715번 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐 + 그리디 문제이다. 원리는 다음과 같다. n = 4일때 1 2 3 4가 있다고 하자. 그럼 두 숫자를 이용해서 최소로 만들려면 가장 적은수를 사용해야 한다(그리디 기법) 따라서 (1 + 2)을 사용해서 하나로 만들면 3, 3, 4가 남고 한번 더 가장 적은수를 사용한다. 따라서 (3 + 3)을 사용해 6, 4가 남으므로 답은 (1 + 2) + (3 + 3) + (6 +..
14786번 Ax+Bsin(x)=C ② https://www.acmicpc.net/problem/14786 14786번: Ax+Bsin(x)=C ② 첫째 줄에 정수 A, B, C가 주어진다. (0 < B ≤ A ≤ 100,000, 0 < C ≤ 100,000) www.acmicpc.net 수학 + 이분탐색 문제이다. 다음과 같이 수식을 정리해주었다. 이후 매개변수 탐색을 이용하여 정답을 찾으면 된다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typedef tuple tu; typedef vector vc; int mai..
17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net bfs문제이다. 음식이 있는 곳을 다 돌면서 가장 최소의 cnt값만 출력하면 된다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typede..
18405번 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net bfs문제이다. 문제의 조건중에 번호가 낮은 바이러스가 먼저 퍼지므로 우선순위 큐를 사용해 가장 먼저 증식하도록 했다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typed..
16978번 수열과 쿼리 22 https://www.acmicpc.net/problem/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 오프라인 쿼리, 세그먼트 트리를 활용하는 문제이다. 오프라인 쿼리를 사용해주는 이유는 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. 이러한 조건이 있기 때문이다. 만약 k = 0이라면 1번 쿼리가 한 번도 적용 안 될 때 출력해야 하는데 온라인 쿼리를 사용한 경우 1번 쿼리..
17469번 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리 N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의 www.acmicpc.net 오프라인 쿼리 + set + UF을 사용하는 문제이다. 여기서 오프라인 쿼리란 문제의 입력을 모두 받고 답을 출력하는걸 의미한다. set을 사용하는 이유는 중복되서 들어오는 값을 제거해주기 위함이다. 문제를 잘보면 (n-1)개는 무조건 (1)을 입력 받기 때문에 모두 끊어진다. 따라서 다 끊어진 상태에서 시작해서 (1)을 입력받으면 다시 합치면서 답을 출력하면 된다. 다 끊어진 상태..
13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 오프라인 쿼리, UF를 활용하면 된다. 여기서 오프라인 쿼리란 문제의 입력을 모두 받고 답을 출력하는걸 의미한다. 문제를 잘보면 (n-1)개는 무조건 (1)을 입력 받기 때문에 모두 끊어진다. 따라서 다 끊어진 상태에서 시작해서 (1)을 입력받으면 다시 합치면서 답을 출력하면 된다. 다 끊어진 상태에서 시작하는 이유는 UF에 최적화를 시키기 위함이다. #include #de..
14868번 문명 https://www.acmicpc.net/problem/14868 14868번: 문명 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 세계의 크기를 나타내는 정수 N(2 ≤ N ≤ 2,000)과 문명 발상지의 수 K(2 ≤ K ≤ 100,000)가 주어진다. 다음 K줄에는 한 줄에 하나씩 문명 발상지 www.acmicpc.net bfs + UF문제이다. 백조의 호수와 비슷한 문제다. 1. 문명이 생기는 곳 모두 문명의 값으로 바꿔주었고 queue에 넣어줬다. 2. 담긴 queue를 하나씩 돌면서 값이 있고 자신의 값이랑 다른 문명과 Union을 하였다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #defin..
10165번 버스 노선 https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 백준 2170번 선 긋기와 매우매우매우 유사한 문제이다. 단 추가된 것은 원형으로 바뀌었다. 1. 노선을 원형으로 만들지 말고 수직선으로 만든다. 2. a > b일 때 n 이상을 더 추가한다. 예) n = 9이고 a = 5, b = 0일 때 5, 6, 7, 8, 9, 0이 아니라 5, 6, 7, 8, 9, 10으로 한다. 3(가장 중요). 그럼 n = 9..
전위, 중위, 후위 구현 void preorder(struct Node *head){//전위 구현 if(head != nullptr){ cout value Llink); preorder(head -> Rlink); } } void Inorder(struct Node *head){//중위 구현 if(head != nullptr){ Inorder(head -> Llink); cout value Rlink); } } void Postorder(struct Node *head){//후위 구현 if(head != nullptr){ Postorder(head -> Llink); Postorder(head -> Rlink); cout value
트리 구현 void Insert(struct Node *head,int value){ struct Node *Newnode = (struct Node *) malloc(sizeof(Node));//새로운 노드 설정 Newnode -> Llink = nullptr, Newnode -> Rlink = nullptr;//다음 간선은 값이 없으므로 null Newnode -> value = value;// 새로운 노드에 값 설정 if(head -> Llink == nullptr && head -> Rlink == nullptr){//만약 루트가 0이면 루트 값 설정 head -> Llink = Newnode, head -> Rlink = Newnode; return; } else{ head = head -> Llink;/..
기본 설정 이진 트리를 사용하기 위한 링크 설정 struct Node{ int value; struct Node *Llink; struct Node *Rlink; }; 처음엔 값이 없으므로 null로 정의 한다. struct Node *head = (struct Node *) malloc(sizeof(Node)); head -> Llink = nullptr, head -> Rlink = nullptr;
5639번 이진 검색 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 기본적인 후위순회 문제이다. 나같은 경우는 링크드 리스트로 구현했다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typedef tuple tu; typedef v..
4485번 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 최단경로, bfs문제이다. 다음 경로 비용 > 현재 비용 + 다음 도둑루피의 값 형식으로 풀면 된다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typede..
1261번 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net bfs + 최단경로 문제이다. 벽을 부수면 비용이 1씩 추가되고 안 부수면 비용이 없다. 따라서 다음과 같이 해주면 된다. if(다음 경로가 == 1) 다음경로의 비용 > 현재 경로의 비용 + 1 else if(다음경로가 == 0) 다음경로의 비용 > 현재 경로의 비용 #include #define all(v) v.begin(), v.end() #define INF 2e9 #..
3197번 백조의 호수 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 처음엔 간단한 BFS 문제인 줄 알고 제출했다가 시간초과가 났다. 코드를 최적화하기 위해 아래와 같이 풀었다. 1. 얼음을 녹이는 Melt 함수 -> 최적화 : 완전 탐색하지 않고 '.'이 있는 좌표만 받아와 BFS 돌리기 2. 백조가 만날 수 있는지 확인하는 Bfs함수 -> 최적화 : 매번 백조가 있는 위치부터 BFS 하지 않고 이번에 녹은 얼음부터 BFS 진행 #i..
1043번 거짓말 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net UF문제이다. 나는 파티에 거짓말 아는 친구가 있으면 -1로 부모값을 바꿔 계산해주었다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typedef tuple tu; typedef vec..
1395번 스위치 https://www.acmicpc.net/problem/1395 1395번: 스위치 첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O www.acmicpc.net lazy propataion문제이다. 구간을 갱신할 때 tree[node] = (end - start + 1) - tree[node]를 하면 뒤집는 거와 똑같은 역할을 한다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using names..
3078번 좋은 친구 https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 큐와 슬라이딩 윈도우 기법을 사용하였다. 1. 자기 글자수에 맞게 큐에 넣어준다. 2. 순위가 높은순으로 큐에 들어간다. 3. (제일 나중에 들어온 순위 - 큐 가장 앞에 있는 순위)가 k를 초과하면 가장 앞에 있는 순위를 빼준다. -> 슬라이딩 윈도우 기법 주의해야 할 점은 만약 n = k = 300000이면 쌍이 (299999 * 300000 / 2) 개가 만들어지므로 in..
16496번 큰 수 만들기 https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 그리디, 정렬 문제이다. 약간의 꼼수를 써서 string a, string b가 있다고 할때 a와 b를 붙인게 b와 a를 붙인 거보다 크면 true 아니면 false 반환했다. 예를 들어 a = "100"이고 b = "32"일 때 a + b = "10032"이고, b + a = "32100"이므로 이 값들을 비교하였다. #include #define all(v) ..
12844번 XOR https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net lazy propagation문제이다. XOR특성상 a ^ a = 0 이고 a ^ 0 = 0 이다. 따라서 a를 짝수번 XOR 하면 0이므로 XOR을 안해도 되고 a를 홀수번 XOR하면 XOR을 해야한다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #def..
1939번 중량제한 https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net UF와 크루스칼 알고리즘을 비슷하게 이용하여 풀었다. 주의해야할 점은 연결을 다 해놓고 답을 구하면 안되고 연결 후 Find하기를 반복해야한다. #include #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef p..
14245번 XOR https://www.acmicpc.net/problem/14245 14245번: XOR 첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄 www.acmicpc.net 세그먼트 트리 응용문제이다. Lazy propagation을 이용하면 풀 수 있다. #include #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typedef vector vc; l v[500001],tree[500001 ..
17144번 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현, 시뮬레이션 문제이다. 나는 아래와 같은 경우로 나눠서 풀었다. 1. 미세먼지를 확산 시키는 DiffUse 함수 2. 공기청정기를 가동시키는 Clear함수 한 가지 주의해야 할 점은 확산이 한 번에 일어나기 때문에 새로운 배열을 만들어 확산 시켜야 한다. #include #define INF 2e9 #define F first #define S second using namespace st..
16234번 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 구현 문제이다. 인구수가 L이상 R이하라면 인구 이동이 일어남으로 bfs이용해 인접한 땅이 조건이 맞는지 완전 탐색하였다. #include #define INF 2e9 #define F first #define S second using namespace std; typedef long long l; typedef pair p; typedef vector vc; int dx[] = ..
13701번 중복 제거 https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net 비트마스크를 이용한 문제이다. 메모리 초과가 안 나기 위해서 unsigned char를 이용해 메모리를 줄였으며 8개의 비트에 각 정보를 담은(전체 크기 / 8) 만큼의 메로리로 더 줄였다. #include #define l long long #define INF 2e9 #define p pair #define vc ve..
에라토스테네스의 체(비트마스크) #include #define l long long #define INF 2e9 #define p pair #define vc vector #define F first #define S second using namespace std; //unsigned char는 1바이트로 총 8비트의 공간이 있다. bool isPrime(int k,vc &arr){ return arr[k >> 3] & (1 > 3] &= ~(1 > n; vc arr((1000+7) / 8 +1,255); Set(1,arr); for(int i=2;i*i

티스토리툴바