티스토리

번쩍번쩍

검색하기

블로그 홈

번쩍번쩍

yun000.tistory.com/m

yun000 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

[백준] 2448번. 별 찍기-11 (C++) 문제https://www.acmicpc.net/problem/2448풀이[재귀]좌표 찍어보다 보면 규칙이 보인다.동그라미 친 부분을 재귀로 돌면서별을 찍으면 된다. 히히 삼각형 이쁘다~코드#include using namespace std;int arr[8000][8000] = { 0 };void star(int n, int x, int y) { if (n == 3) { //삼각형 그리기 arr[y][x] = 1; arr[y + 1][x - 1] = 1; arr[y + 1][x + 1] = 1; arr[y + 2][x - 2] = 1; arr[y + 2][x + 2] = 1; arr[y + 2][x - 1] = 1; arr[y + 2][x + 1] = 1; arr[y + 2][.. 공감수 0 댓글수 0 2025. 2. 27.
[백준] 1916번. 최소비용 구하기 (C++) 문제https://www.acmicpc.net/problem/1916풀이[다익스트라]https://yun000.tistory.com/148 다익스트라 알고리즘 (Dijkstra)다익스트라 알고리즘하나의 정점에서 다른 정점들로의 최단경로 찾는 알고리즘탐욕법과 다이나믹 프로그래밍 사용 우선순위 큐 (priority queue)을 통해 최소 비용 노드를 파악→ 시간 복잡도 O(Nloyun000.tistory.com +) 주의!! 방향 그래프이다!!! 무방향 그래프로 생각해서 한참 헤맸다.코드#include #include #include #include using namespace std;typedef pair p;int main() { //INPUT/////////////////////////////////.. 공감수 0 댓글수 0 2025. 2. 26.
[백준] 11725번. 트리의 부모 찾기 (C++) 문제https://www.acmicpc.net/problem/11725풀이[DFS/BFS]node 1부터 시작하여 연결된 노드를 탐색하며 부모 노드를 확인한다. +) BFS가 더 효율적인 것을 볼 수 있다.코드1️⃣ DFS#include #include #include #include using namespace std;int visited[100001] = { 0 };int result[100001] = { 0 };vector> tree;void check(int node, int parent) { result[node] = parent; for (int i = 0; i > N; tree = vector>(N+1); int n1, n2; for (int i = 0; i > n1 >> n2; tree[.. 공감수 0 댓글수 0 2025. 2. 25.
[백준] 1991번. 트리 순회 (C++) 문제https://www.acmicpc.net/problem/1991풀이[재귀]preorder = node Left Rightinorder = Left node Rightpostorder = Left Right node +) 처음에 "2번 무식한 코드" 처럼 만들었는데암만봐도 더 나은 방법이 있을 것 같아서 1번으로 바꿈코드1️⃣ 깔끔한 코드#include #include #include #include using namespace std;unordered_map>tree;void preorder(char nowNode) { if (nowNode == '.')return; cout > N; char root, left, right; for (int i = 0; i > r.. 공감수 0 댓글수 0 2025. 2. 24.
[백준] 19951번. 태상이의 훈련소 생활 (C++) 문제https://www.acmicpc.net/problem/19951 풀이[누적합] sum+=prefixSum[i] 이기 때문에prefixSum의 시작점(예를들어 1번의 -3) 끝점(예를 들어 6번의 +3)에만 값들을 지정해 주면 된다. 시작점의 위치는 0부터 시작하게 했으므로 prefixSum[a - 1] += k; 끝점은 a~b에 k값을 더해야 하기 때문에 b-1이 아닌 b이다. prefixSum[b] -= k; 코드#include #include using namespace std;int main() { //INPUT int N, M, a, b, k; cin >> N >> M; vectorground(N, 0); for (int i = 0; i > ground[i]; } vectorprefi.. 공감수 0 댓글수 0 2025. 2. 20.
[백준] 1629번. 곱셈 (C++) 문제https://www.acmicpc.net/problem/1629 풀이[분할 정복] 🍏모듈러 연산 적용(A×B)%C = ((A%C)×(B%C))%C 🍏분할 정보 적용 예시A=10, B=11, C=12를 생각해 보자10^11은 10^5 x 10^5 x 10 과 같다10^5 는 10^2 x 10^2 x 10 과 같다10^2 는 10^1 x 10^1 과 같다이 방식을 이용한 것이다코드#include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(NULL); //INPUT long long A, B, C; cin >> A >> B >> C; //CALCULATE long long res.. 공감수 0 댓글수 0 2025. 1. 17.
[백준] 17626번. Four Squares (C++) 문제https://www.acmicpc.net/problem/176264개 이상의 제곱수를 더해서 n을 만들어라풀이[완전탐색, BFS]nowNumber를 0으로 만든다면 끝낸다nowCount가 4를 초과하면 더이상 계산하지 않는다코드#include #include #include #include #include using namespace std;int main(){ //INPUT int n; cin>>n; int visited [50002]={0,}; int result; queue>q; //START q.push({0,n});//count, now number visited[n]=1; while(!q.empty()) { int.. 공감수 0 댓글수 0 2025. 1. 16.
[백준] 18870번. 좌표 압축 (C++) 문제https://www.acmicpc.net/problem/18870 풀이[unique사용]vector의 unique사용하면 금방 풀리는 문제이다 정렬 후에 unique를 써야 한다.sort(vec.begin(), vec.end());vec.erase(unique(vec.begin(),vec.end()),vec.end()); map dic에 숫자별 위치를 저장했다코드#include #include #include #include using namespace std;int main(){ //INPUT int N; cin >> N; vectornum(N); vectororiginal(N); for (int i = 0; i > num[i]; } original = num; //CHECK sort(num.b.. 공감수 0 댓글수 0 2025. 1. 8.
[백준] 11286번. 절댓값 힙 (C++) 문제https://www.acmicpc.net/problem/11286 풀이[priority_queue] comp를 통해 원하는 방식으로 비교하면 된다!! {절대값, 부호}를 pq에 저장하는 방식이다. 그렇기에 절대값이 같다면 부호 기준으로 비교하고if(a.first==b.first){return a.second>b.second;}그렇지 않다면 절대값 기준으로 비교한다return a.first>b.first; 코드#include #include #include #include #include using namespace std;struct comp{ bool operator()(pair a, pair b) { if(a.first==b.first){return a.second>b.s.. 공감수 0 댓글수 0 2025. 1. 2.
[백준] 14500번. 테트로미노 (C++) 문제https://www.acmicpc.net/problem/14500풀이[DFS+노가다] 4번 이동하는 모든 경우의 수를 생각해보자위와 같은 경우 등등이 있을 것이다. 어라 그런데 뭔가 보인다!짜잔! 도형들을 회전하거나 대칭 시킨 모양과 동일하다!그렇기 때문에 dfs를 사용해서 해결하면된다 그런데 ㅗ 모양은 저 경우에 대입할 수 없다그렇기 때문에 이 경우는 노가다로 진행한다 코드#include #include #include using namespace std;int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };int answer = 0;int map[502][502];int visited[502][502];int n, m;void dfs(int x, int y, int.. 공감수 0 댓글수 0 2025. 1. 1.
[백준] 16928번. 뱀과 사다리 게임 (C++) 🌘 문제https://www.acmicpc.net/problem/16928 🌗 풀이[BFS]흔한 bfs문제이다 한칸에 사다리와 뱀이 동시에 있는 경우는 없기 때문에board하나로 뱀와 사다리를 통한 이동을 확인할 수 있다board[시작위치]=이동위치 🌖 코드#include #include #include using namespace std;int main(){ // INPUT int ladderNum, snakeNum; cin >> ladderNum >> snakeNum; vector board(101, 0); int from, to; for (int i = 0; i > from >> to; board[from] = to; } for (int .. 공감수 1 댓글수 1 2024. 12. 30.
[백준] 9019번. DSLR (C++) 문제https://www.acmicpc.net/problem/9019 풀이[bfs]bfs문제이다!visited를 설정해주는 것을 유의하자 코드#include #include #include #include using namespace std;int D(int num) { return (num * 2) % 10000; }int S(int num) { return (num == 0) ? 9999 : num - 1; }int L(int num) { return (num % 1000) * 10 + (num / 1000); }int R(int num) { return (num % 10) * 1000 + (num / 10); }int main() { int T; cin >> T; while (T--) .. 공감수 0 댓글수 0 2024. 12. 28.
[백준] 7662번. 이중 우선순위 큐 (C++) 문제https://www.acmicpc.net/problem/7662 풀이[priority queue]INSERT최대힙, 최소힙에 둘 다 숫자를 넣는다desc.push(n);asc.push(n);number에 해당 수가 몇개 있는지 저장한다number[n]++; DELETE숫자를 저장하는 곳이 2개(desc,asc)라서 확인해야 하는 과정이 있다. 확인하려는 최소값(asc.top()) 혹은 최대값(desc.top())이 존재하는 값인지 확인해야 한다.만약 number에서 확인한 값이 0이면 number[desc.top()] == 0 이미 삭제된 값이라 존재하지 않는다는 의미이다. 그렇기에 해당 값을 최소힙 혹은 최대힙에서 pop(asc.pop();, desc.pop())한다.while (!asc.emp.. 공감수 0 댓글수 0 2024. 12. 28.
[백준] 적록색약 (C++) 문제https://www.acmicpc.net/problem/10026 풀이[DFS]상하좌우로 움직였을 때int nextX=x+dir[i][0]; int nextY=y+dir[i][1]; 같은 색이 있는 경우 area[nextY][nextX]==area[y][x] visit하고visited[nextY][nextX]=1; 최대한 끝까지 탐색한 후돌아왔을 때 수를 하나씩 늘리면 된다.dfs(k,i,true); normal++; 일반인과 색맹인 사람을 구분해서 수를 카운트 했다.그리고 색맹인 경우area[nextY][nextX]=='R'&&area[y][x]=='G' || area[nextY][nextX]=='G'&&area[y][x]=='R'R,G도 같은 색으로 보게 하였다. 코드#include #inclu.. 공감수 0 댓글수 0 2024. 12. 26.
[백준] 5430번. AC (C++) 문제https://www.acmicpc.net/problem/5430 풀이[deque 사용]단순 구현 문제이다!deque의 pop_front()와 pop_back()을 사용하면 된다pop_front()는 맨 앞에 것을 pop(삭제)하는 것이고pop_back()은 맨 뒤에 것을 pop하는 것이다 코드#include #include #include #include using namespace std;void solution(){ //INPUT string f,arr; int n; cin >> f; cin >> n; cin >> arr; deque dq; bool isReverse=false; //COLLECT NUMBERS string number = ""; for (int i = 1; i > T; for.. 공감수 0 댓글수 0 2024. 12. 25.
[백준] 7576번. 토마토 (C++) 문제https://www.acmicpc.net/problem/7576 풀이흔한(?) bfs 문제이다 INPUT입력하면서 모두 이미 익었는지 확인하고(isAlreadyComplete)그렇다면 0출력 후 끝낸다익지 않은 것이 있다면 q에 하나씩 넣어준다.거기부터 탐색 할 것이기 때문이다 CHECK익은 토마토의 상하좌우를 확인할 것이다. 단 확인하려는 위치가 토마토 판 범위를 넘어가거나 if(nextY=n || nextX>=m) 익지 않은 토마토가 아닌 경우(비어있거나 익은 경우), 혹은 이미 방문한 곳인 경우if(Tomato[nextY][nextX]!=0 || Visited[nextY][nextX]==1) 넘어가고 확인하지 않을 것이다 RESULTTomato에서 익지 않은 것이 있는지 확인하고 그렇다면.. 공감수 0 댓글수 0 2024. 12. 23.
[백준] 11054번. 가장 긴 바이토닉 부분 수열 (C++) 문제https://www.acmicpc.net/problem/11054풀이[LIS알고리즘, DP]되게 어렵게 생각했는데 그냥 LIS쓰면 된다ㅋㅋINCREASING최장 증가 수열 길이를 구한다 DECREASING최장 감소 수열 길이를 구한다 ANSWERup[i]+down[i]가 가장 큰 것을 ans로 설정하면 된다.코드#include #include using namespace std;int num[1000], up[1000], down[1000];int main() { //INPUT int N; cin >> N; for (int i = 0; i > num[i]; } //INCREASING for (int i = 0; i num[j]) up[i] = max(up[i], up[j] + 1); } .. 공감수 0 댓글수 0 2024. 11. 28.
[백준] 1965번. 상자넣기 (C++) 문제https://www.acmicpc.net/problem/1965풀이[LIS,DP]코드#include #include #include using namespace std;int main(){ //INPUT int N; cin >> N; vector box(N); vectordp(N, 1); for(int i=0;i> box[i]; } //CHECK for (int i = 0; i box[k])dp[i] = max(dp[i], dp[k] + 1); } } //RESULT cout 동일한 문제https://yun000.tistory.com/164 [백준] 11055번. 가장 큰 증가하는 부분 수열 (C++)문제https://www.acmicpc.net/problem/11055풀이[DP, LIS알고리즘.. 공감수 0 댓글수 0 2024. 11. 26.
[백준] 11657번. 타임머신 (C++) 백준https://www.acmicpc.net/problem/11657풀이[벨만-포드 알고리즘]음의 간선이 있기 때문에 다익스트라가 아닌 벨만-포드 알고리즘을 사용하자플로이드 와샬도 가능은 할 것 같은데 일단 벨만-포드를 사용했다 Bellman-Ford algorithm모든 노드를 돌면서to 노드로 이동하는 것이 Dist[to]보다 저렴하면 갱신한다.이것을 (노드수-1번) 반복한다. check negative weight cycles한 번 더 이동하는데 값이 작아지면음의 가중치 사이클이 있는 것이다.코드#include #include #include using namespace std;#define INF 20000000int main(){ int N, M; cin >> N >> M; vect.. 공감수 0 댓글수 0 2024. 11. 25.
[백준] 11055번. 가장 큰 증가하는 부분 수열 (C++) 문제https://www.acmicpc.net/problem/11055풀이[DP, LIS알고리즘]저번에 푼문제랑 비슷해서 후딱풀었다 숫자들을 차례대로 확인한다지금 확인할 숫자가 n번째 숫자라고 하자0~n-1번째 숫자들 중 n번째 숫자보다 작은 숫자를 m이라고 하자"dp[m]+n번째 숫자"가 "dp[n]"보다 크면 dp를 갱신한다. dp중에 제일 큰 값이 정답! 코드#include #include #include using namespace std;int main(){ int N; cin >> N; int maxN=0; vectornumber(N); vectordp(N); for (int i = 0; i > number[i]; dp[i] = number[i]; for (int j = 0; j numbe.. 공감수 0 댓글수 0 2024. 11. 24.
[백준] 11722번. 가장 긴 감소하는 부분 수열 (C++) 문제https://www.acmicpc.net/problem/11722풀이[DP, LIS 알고리즘]숫자를 차례대로 확인한다.이번에 확인하는 숫자 n의 이전 값들 중에n보다 크고, dp값도 큰 m이 있다고 하면m의 dp값+1 로 n의 dp값을 갱신한다.m과 연결된 부분 수열이 되는 것이다.예시10 30 10 20 20 10 에서 숫자를 차례대로 보자 이번 차례가 4번째에 있는 20이라고 하자0~3번째 숫자를 보며 20보다 큰 것이 있나 확인할 것이다앗 30이 더 크다!30즉 dp[1]의 값은 1이다.20즉 dp[3]의 값은 1이다.dp[1]+1이 dp[3]보다 더 큰값이므로 dp[3]=2로 갱신된다. 이번 차례가 5번째에 있는 10이라고 하자0~4번째 숫자를 보며 10보다 큰 것이 있나 확인한다.30,20.. 공감수 0 댓글수 0 2024. 11. 23.
[백준] 2116번. 주사위 쌓기 (C++) 문제https://www.acmicpc.net/problem/2116풀이Front Back다이스가 ABCDEF이다. 여기서A가 bottom 이면 F가 top이다 / F가 bottom이면 A가 top이다B가 bottom 이면 D가 top이다 / D가 bottom이면 B가 top이다C가 bottom 이면 E가 top이다 / E가 bottom이면 C가 top이다알파벳들을 각각 숫자로 나타내면0 5 / 5 01 3 / 3 12 4 / 4 2이다.이 관계를 mapbottomTop으로 저장한 것이다. Check1번 다이스를 두는 방식에 따라 나머지 다이스들이 다 정해진다.그래서 1번 다이스의 밑면이 1~6일 때의 상황을 하나씩 살펴보면 된다 diceCheck 재귀함수이전 다이스의 top값을 알면현재 확인.. 공감수 0 댓글수 0 2024. 11. 21.
[백준] 2437번. 저울 (C++) 문제https://www.acmicpc.net/problem/2437풀이[누적합]문제의 예시 1 1 2 3 6 7 30 를 살펴보자 1 → 1 (숫자 1로만 만들 수 있는 숫자)1 → 1 2 (숫자 1, 1로 만들 수 있는 숫자)2 → 1 2 3 4 (숫자 1, 1, 2로 만들 수 있는 숫자)3 → 1 2 3 4 5 6 76 → 1 2 3 4 5 6 7 8 9 10 11 12 137 → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2030 → 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 31 32 33 34 35.....50 여기서 각각 1 2 4 7 13 20까지는 숫자가 연속된다.하지만 30은 20 보다 크므로21.. 공감수 0 댓글수 0 2024. 11. 20.
[백준] 11660번. 구간 합 구하기 5 (C++) 문제https://www.acmicpc.net/problem/11660풀이[DP,누적합]INPUT///////////////////////// 초록색 범위는 dp[i-1][k], 하늘색 범위는 dp[i][k-1]이다.이 둘을 합했으니 그 공통되는 dp[i-1][k-1]을 빼주고입력 받은 숫자(num)을 더해주면 된다.dp[i][k] = dp[i][k - 1] + dp[i - 1][k] + num -dp[i-1][k-1]; CHECK/////////////////////// 답 = dp[x2][y2]-(dp[x1-1][y2]+dp[x2][y1-1]-dp[x1-1][y1-1]) 코드#include #include using namespace std;int main(){ ios_base::sync_with_s.. 공감수 0 댓글수 0 2024. 11. 19.
[백준] 11659번. 구간 합 구하기 4 (C++) 문제https://www.acmicpc.net/problem/11659주의사항빠른 입출력을 위해 아래 코드를 추가해주지 않으면 시간초과 뜬당ios_base::sync_with_stdio(false);cout.tie(NULL);cin.tie(NULL); 풀이[DP, 누적합] INPUT////////////////////////number[i]는 number[1]부터 number[i]까지 합한 것이 된다. CHECK//////////////////////i부터j까지 합을 구하고 싶다면 number[j] ( 0부터 j까지 합한 값) 에서number[i-1] (0부터 i-1까지 합한 값)를 빼면 된다. #include #include using namespace std;int main(){ ios_base::s.. 공감수 0 댓글수 0 2024. 11. 19.
[백준] 17182번. 우주 탐사선 (C++) 문제https://www.acmicpc.net/problem/17182 풀이DFS+플로이드 와샬1. Floyd-Warshall행성A에서 행성 B로 가는 방법은 한가지가 아니다!A-C-B, A-B, A-C-D-B 등등.. 많다이 중에 어떠한 것이 최소 경로인지 파악하기 위해 플로이드 와샬을 쓴다 플로이드 와샬 전 → 후case10 30 1 0 2 11 0 29 --> 1 0 228 1 0 2 1 0case20 83 38 7 0 53 38 715 0 30 83 15 0 30 2267 99 0 44 --> 58 90 0 4414 46 81 0 14 46 52 0 +) 플로이드 와샬 알고리즘 설명https://yun000.tistory.com/155.. 공감수 1 댓글수 0 2024. 11. 17.
[백준] 11723번. 집합 (C++) 문제https://www.acmicpc.net/problem/11723 주의사항아래 코드는 C++에서 입출력 성능을 최적화하기 위한 코드로추가해주지 않으면 시간초과 난다!ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 풀이비트 마스크 써야하는 문제다그냥 냅다 배열로 풀었더니 시간초과가 났다ㅎㅎ AND&비트 둘 다 1이여야만 1OR|비트 하나라도 1이면 1XOR^비트가 서로 다르면 1, 같으면 0SHIFT>비트를 좌우로 한칸씩 이동NOT~비트 반전 ALL bit = (1 1여기서 1을 빼주면 모든 21 하위 비트가 1이 된다. EMPTY bit=0; bit가 0이되면 초기화! ADD bit |= (1 REMOVE bit &= ~(1 .. 공감수 0 댓글수 1 2024. 11. 16.
[백준] 1374번. 강의실 (C++) 문제https://www.acmicpc.net/problem/1374 풀이INPUT강의 번호는 상관이 없다.timeTable에 시작,종료시간 정보를시작 시간 기준 오름차순 정렬한다. CHECKpriority_queue endTime은 수업이 빨리 끝나는 순으로 정렬되어 있다 timeTable의 i번째 수업 시작시간이endTime내의 가장 빨리 끝나는 시간 이후에 시작된다면방을 추가할 필요가 없다. 그리고 해당 방의 수업 종료 시간은 i번째 수업 종료시간으로 갱신되야 하므로endTime.pop()을 해준다. timeTable의 i번째 수업 시작시간이endTime내 가장 빨리 끝나는 시간 이전에 시작이라면해당 방에서는 수업을 할 수 없으니 방을 추가한다. #include #include #include #i.. 공감수 0 댓글수 0 2024. 11. 15.
[SWEA] 1249번. 보급로 (C++) 문제https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=CCPP&select-1=4&pageSize=10&pageIndex=1 SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 풀이BFS로 풀면 된다 그나마 조금 다른점은(?)if (nsum>=distance[ny][nx]) continue;이 부분일것.. 공감수 0 댓글수 4 2024. 11. 15.
[백준] 2212번. 센서 (C++) 문제https://www.acmicpc.net/problem/2212 어려운 문제는 아닌데 뭔가 이해하는데 오래걸렸다.아래와 같이 생각하니 한방에 이해가 갔다 주의사항K값이 N값보다 클 경우를 생각해야한다!!! 이걸 생각 못해서 런타임 에러 났다.결과값은 long long으로 풀이 예시 2번)3 6 7 8 10 12 14 15 18 20에 센서들이 있다.센서들 사이의 거리를 확인한다. 3 1 1 2 2 2 1 3 2이것을 내림차순 정렬한다. 3 3 2 2 2 2 1 1 1K-1 즉 4개를 삭제한다 2 2 1 1 1이것을 다 합하면 result 7 이 나온다 센서들 사이의 거리가 긴부분은 나눠서 집중국을 설치해주면 되기 때문이다. #include #include #include using namespace.. 공감수 1 댓글수 0 2024. 11. 14.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.