크롱의 Dev Log

문제 링크: www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 풀이 방법 [min, max] 구간의 최대 원소 개수는 1000001이므로 bool arr[1000001]을 선언하고 여기에 min~max구간의 수가 제곱ㄴㄴ수인지 아닌지 저장해줬다. arr[0]: min이 제곱ㄴㄴ수인지, arr[1]: min + 1이 제곱ㄴㄴ수인지 ... 일단 모두 제곱ㄴㄴ수라고 가정하고 시작한다. (memset을 통해 모두 true로 초기화한다.) 그다음 2부터..

문제 링크: programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr 카펫의 가로 세로 길이를 구하는 문제이다. 가로 길이를 x, 세로 길이를 y라고 하자. 테두리 1줄이 갈색이고, 나머지 안쪽은 노란색이라고 했다. 네 변에 접한 타일(갈색 타일)의 개수는 양변의 길이를 두번씩 더하고 겹치는 모서리를 한번 빼준 값인 2x+2y-4이다. 안쪽의 타일(노란 타일)의 개수는 (x-2)*(y-2)이다. 갈색 타일과 노란색 타일을 더한 ..

선수 과목 체계 등 선행 관계가 있는 자료구조를 정렬할 때 필요한 알고리즘이 바로 위상정렬(topological sort)이다. 방향이 있는 그래프(단, 사이클이 없어야 함) 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 순서대로 나열하는 알고리즘이다. 유향 그래프(방향이 있는 그래프)에서 에지 가 있다면 정점u가 정점v를 선행한다.  위상 정렬 방법 ① 진입 차수(내차수)가 0인 임의의 정점 (선행자가 없는 정점) 출력 ② 출력한 정점에 부착된 모든 에지들을 제거하여 진입 차수 재계산 ③ 모든 정점이 제거될 때까지 ①~② 반복 ④ 진입 차수가 0인 것이 없으면, 그래프가 사이클을 포함한 것으로서 해가 존재하지 않음.  위상 정렬 알고리즘 (C언어) 아래와 같은 입력 형식의 사이클이 없는 방향그..

문제 링크: www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net #include #include #include #include #include #define MAX 100 #define INF 10000 using namespace std; int n, islandNum, answer; int map[MAX][MAX]; // 입력 받아 지도 값 저장(0:바다/1:육지) >> 이후 섬 번호 붙여줌 bool visit[MAX][MAX]; // BFS탐색 시, 방문 여부..

문제 링크: www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 방법 int W[16][16]; //도시 i에서 j로 가기 위한 비용(갈 수 없는 경우는 0) int dp[16][1

문제 링크: www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net #include #include #include using namespace std; string s; int visited[50]; int ans; //바깥쪽에서 안쪽으로 계산해 나감 int calc(int start, int end) { int result = 0; for (int i = start; i < end; i++) { if (s[i] == '(') { int k = s[i - 1..

문제 링크: www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 2~1000000까지 1로 만드는 최소 연산 횟수를 먼저 계산한다. 작은 수에 대해서 먼저 계산하고 그 값을 저장해 재활용함으로써 불필요한 연산을 줄일 수 있다. #include #include using namespace std; #define MAX 1000001 int arr[MAX]; //1로 만드는 연산 횟수 저장 void count() { for (int i = 2; i

문제 링크: www.acmicpc.net/problem/1398 1398번: 동전 문제 김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다. 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 식으로 나타내면 0보다 크거나 같은 모든 K에 www.acmicpc.net 1, 10, 25, 100, 1000, 2500, 10000, 100000, ... 화폐단위가 100씩 곱한 값으로 끊어진다는 것을 캐치하면 쉽게 풀리는 문제이다. 현재 지불해야하는 금액 중 100으로 나눈 나머지는 어차피 100 이하의 금액인 동전(1, 10, 25)로만 지불할 수 밖에 없다. 따라서 1~99 금액에 대한 필요한 동전 개수를 계산해 dp..