개발 블로그

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 이 문제는 최대힙(priority_queue), 최소힙(priority_queue)를 이용하여 풀 수 있습니다. 힙이 무엇인지 설명드리겠습니다. 힙의 특성에 대해 설명드리겠습니다. 최대힙은 부모 노드는 자식 노드에 들어있는 값보다 커야하고, 최소힙은 부모 노드는 자식 노드에 들어있는 값보다 작아야 합니다. 힙은 완전 이진 트리(Complete Binary Tree)이기 때문에, N..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 DFS, Union Find 등 다양한 알고리즘을 통해 해결할 수 있는 문제입니다. 저는 Union Find로 풀었는데, 이 자료구조를 통해 어떻게 해결했는지 설명드리겠습니다. Union Find란 ? 상호 배타적 집합(Disjoint-set)들의 부분 집합들로 나눠진 원소들에 대한 자료구조 2가지 연산으로 이루어져 있다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산(루트를 찾는..

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 이 문제는 N명이 한 줄로 서있을 때 서로 마주칠 수 있는 쌍의 수를 구하는 문제입니다. 비교적 어려운 문제는 아니지만, 키가 같은 경우 때문에 고려사항이 많은 문제입니다. 테스트 케이스로 설명 드리겠습니다. case 1 : 7 2 4 1 2 2 5 1 다음과 같이 키가 2 4 1 2 2 5 1 일 경우에는 서로 마주할 수 있는 쌍은 (1 2), (2,3), (2,4), (..

https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net DFS + Bruteforce 문제입니다. 중복 값을 제거해주는 Set를 선언해줍니다. 그리고 길이가 6이 될 때 까지 값을 하나씩 추가해줘야하는데, 예시를 들어 값이 112에서 1을 추가한다면 112(기존 값) * 10 + 1(새로운 값)이 되어야 합니다. 그래서 함수 세 번째 파라미터에서 함수 num * 10 + a[nx][ny]를 호출해주었습니다. ..

https://www.acmicpc.net/problem/17089 17089번: 세 친구 첫째 줄에 사람의 수 N(3 ≤ N ≤ 4,000), 친구 관계의 수 M(0 ≤ M ≤ 4,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계를 의미하는 두 정수 A, B가 주어진다. 친구 관계는 A와 B, 그리고 B와 A가 친 www.acmicpc.net 이 문제는 A, B, C의 각각의 친구의 수의 최솟값을 구하는 문제입니다. 우선적으로 A, B가 친구 관계인지 check해주고, A, B가 친구인 경우에 C가 친구인 경우를 구한다면, 시간 복잡도를 O(N^3)에서 O(N^2 + MN)으로 최소화할 수 있게 됩니다. #include using namespace std; int a[4001][4001]; i..

https://www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 주어지는 입력값은 아이스크림의 종류와 조합해서 안 되는 아이스크림의 종류 개수입니다. 예시를 들어 조합해서는 안 되는 아이스크림이 1번, 3번이면 check[3][1], check[1][3]을 true로 바꿔줘야 합니다. 왜냐하면 1번, 3번이나 3번, 1번이나 같은 의미이기 때문입니다. 만약 검사를 하고 check변수가 false이면 개수를 하나씩 늘려주면 ..

https://www.acmicpc.net/problem/16943 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 이 문제는 c++에 내장되어 있는 next_permutation을 사용하면 간단하게 풀 수 있는 문제입니다. A, B를 입력받고, A의 순서를 뒤바꿔서 C보다 작은 최대 수를 구하는 문제입니다. 우선적으로 A를 문자열로 입력받습니다. 그리고 next_permutation을 이용하여 순열을 하나씩 구하고 stoi함수를 통해 숫자로 파싱 시켜주고 B와 비교해서 작으면 값을 지속..

https://www.acmicpc.net/problem/16924 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net 이 문제는 해당 격자판에서 다음과 같은 십자가를 몇 개 만들 수 있는지 물어보는 문제입니다. 해당 인덱스에서 상하좌우 비교해서 *가 된다면 해당 부분과 크기를 push 해주면 되는 간단한 문제지면 예외의 경우가 존재합니다. 예외 케이스 * *** * * 다음과 같은 부분은 제일 아래쪽 *이 크기가 1인 십자가에 속하지 않기에, -1을 출력 해줘야 합니다. 이러한 경우를 방지하기 위해 ch..

https://www.acmicpc.net/problem/16936 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 이 문제는 곱2, 나3이 섞인 수열이 존재하면, 순서에 맞는 수열을 찾는 문제입니다. 여기에서 핵심은 각 수를 소인수분해 했을 때, 3의 인수가 가장 많은 수가 제일 앞에 와야 합니다. 왜냐하면, 인수가 3이 많게 되면, 그다음 수도 자연스럽게 3으로 나누어 떨어지기 때문입니다. 그리고 3의 인수가 동일하다면 오름차순 정렬해주면 됩니다. (3의 인수가 동일한 경우에는 곱하기 2를..

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 비교적 간단한 브루트포스 문제였습니다. 우선적으로 I,V,X,L을 사용하여 만들 수 있는 로마 숫자의 개수를 반환해야 합니다. 그런데 for문을 4번 돌리게 된다면, 시간 복잡도가 O(n^4)이 되기 때문에 다른 방안을 생각해야 합니다. I+V+X+L = n(사용할 로마 숫자 개수)이 되어야 합니다. 그러면 가장 큰 수를 나타내는 L의 개수는 n-X-V-I가 됩니다. 나머지 부분은 가장 작은 수 I부터 n까지 탐색하고, V는 n-I까지, X는 n-I-V까지 탐색해서 만들 수 있는 로마 숫자의 ..