연의 기록 🪁

https://www.acmicpc.net/problem/16724문제설명UDLR(상하좌우)로 각 칸에 있는 사람들이 어떤 방향에 있는지 주어진다. 사람들이 화살표를 따라 쭉 이동했을 때 모든 사람이 안전구역으로 들어갈 수 있도록 하려면 몇 개의 안전 구역을 만들어야 하는지를 묻는 문제이다. 아이디어이 문제는 그래프의 사이클의 개수를 찾는 문제이다. 사이클 1개당 1개의 안전구역을 만들어 주면 된다. 그래서 dfs를 통해 그래프를 순회하며 부모(사이클의 시작점)를 기록해주고, 마지막에 부모가 총 종류가 있는지를 리턴해줬다.아래의 경우 부모가 2종류가 나왔으니 2를 리턴해주면 된다. 코드정답 코드는 아래와 같다. dfs를 이용해 순회하며 다음 블럭이 현재와 부모가 다르다면 Union함수를 통해 부모를 합쳐..

https://school.programmers.co.kr/learn/courses/30/lessons/258711 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 분석아래와 같이 도넛모양, 막대모양, 8자모양 그래프가 있다.여기서 문제의 핵심은 “이 그래프들과 무관한 정점을 하나 생성한 뒤, 각 도넛 모양 그래프, 막대 모양 그래프, 8자 모양 그래프의 임의의 정점 하나로 향하는 간선들을 연결”했다는 부분이다.즉 아래와 같이 정점을 찾으면 거기에 연결된 것은 도넛, 막대, 8자그래프 중 하나여야 한다는 소리이다.그렇기에 정점에 아래와 같이 도넛그래프 2개를 합친 것 같은 모양이 붙어있거나 하는 일..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 아이디어 나는 문제를 3가지 파트로 나눠서 풀었다. 1. 입력을 받는 부분 2. 팀을 짜는 부분 3. 짜여진 팀을 이용해서 점수를 계산하고 큐에 기록 입력을 받고, 짜여진 팀을 이용해 점수를 계산하는 것을 어렵지 않다. 이 문제의 핵심적인 부분은 팀을 짜는 부분이다. 그 부분은 아래와 같이 구현하였다. 이 문제의 경우에는 사람이 스타트팀 혹은 링크팀이기 때문에 스타트팀에 절반을 배정하면 나머지는 자동으로 링크팀이 된다..

배낭문제(Knapsack Problem) 다이나믹 프로그래밍의 대표적인 예시문제이다. 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 아래와 같은 형식으로 주어진다. https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제를 요약하자면 아래와 ..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 아이디어 문제를 풀고 다른 블로그 글들도 봤는데 규칙이 여러가지라 여러 방식의 점화식으로 풀 수 있다. 난이도가 쉬운 편의 문제이다. P(N)을 쭉 나열하면 아래와 같다. N P(N) 1 1 2 1 3 1 4 2 5 2 6 3 7 4 8 5 9 7 10 9 11 12 12 13 나의 경우 1~5까지는 규칙이 적용되지 않는다고 보고 P(N)=P(N-1)+P(N-5)라고 점화식을 세워서 풀었는데 P(N)=..

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 아이디어 마지막이 1로 끝나도록 일단 나열을 해봤는데 아래와 같았다. 숫자 식 횟수 1 1 1 2 1+1 2 3 1+1+1 3 4 1+2+1 3 5 1+2+1+1 4 6 1+2+2+1 4 7 1+2+2+1+1 5 8 1+2+2+2+1 5 9 1+2+3+2+1 5 10 1+2+3+2+1+1 6 11 1+2+3+2+2+1 6 12 1+2+3+3+2+1 6 ..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 아이디어 1~99는 한수가 1,2,3,4 .... 99개이니 (한 자리, 두 자리 수는 모두 한수이니까) 입력받은 수가 100이상일 경우 100부터 해당 수 까지 한수인지 체크하면 된다. 한 자리씩 잘라 배열에 넣고 뒷자리 수에서 앞자리 수를 빼며 한수인지 체크했다. 코드 #include #include #include using namespace std; int main() { ios::sync_w..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 이 문제는 두가지를 생각해야 한다. 첫번째 수는 무조건 더해주는 수이다. -가 한번이라도 나오면 그 뒤에 나오는 숫자는 모두 빼줘야 한다. 예를들면 위의 55-50+40이라는 식은 값을 최소로 만들기 위해서는 55-(50+40)이렇게 괄호를 칠 것이다. 즉 결론적으로 55-50-40=-35가 된다. 위 규칙 2개를 유념하며 코드를 짜면 아래와 같다. #include #include using..

https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에는 값을 직접 구한 뒤 0의 개수를 뒤에서부터 세려고 했는데 500!의 값은 굉장히 크다. 아래 사이트에서 구해본 결과 https://ko.numberempire.com/factorialcalculator.php 팩토리얼 계산기 팩토리얼 계산기 ko.numberempire.com 팩토리얼의 값이 너무 크다. 그래서 구글링을 한 결과 소인수 분해를 한 뒤 5의 수를 세면 된다. 예제 출력을 보면 10을 입력받으면 2를 출력해야 하는데 10의 경우 10 9 8 7 6 5 4 3 2..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 접근은 잘 했는데 경우의 수를 각각 비교해서 최솟값으로 답을 내야한다는 점을 간과해서 한참 헤맨 문제이다. 내가 생각한 접근 방법은 아래와 같다. 각 수를 1로 만드는 경우를 나열해 보았다. 입력 1 2 3 4 5 ... 8 9 10 연산 횟수 0 1 1 2 3 ... 3 2 3 점화식은 아래와 같이 세웠었다. n=1이면 0 3으로 나눠질 때 : f(x)=1+f(x/3) 2로 나눠질 때 : f(x)=1+f(x/2) 두 수로 나눠지지 않을 때 : f(x)=f(x-1)+1 이런식으로 세웠었다. 적용해보면 f(5)=..

https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 이 문제에서 배운것은 문자열-숫자 변환, 이진탐색이다. 이진탐색은 이론은 알고 있었는데 사용할 생각을 자꾸 못하는 것 같다. 문자열과 숫자 우선 입력받은 값이 숫자인지 숫자가 아닌지 판정을 해야 했는데 그러기 위해 함수를 하나 만들었다. isdigit()함수를 이용했다. //isdigit( [char형 문자] ) -> 해당 문자가 숫자인지 아닌지 리턴해준다. bool ..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수 구하기 2보다 작으면 무조건 소수가 아니므로 false를 리턴, 그게 아닐 경우 2부터 해당 수의 제곱근으로 나눠보며 한번이라도 나누어 떨어지면 소수가 아니라고 판정하는 방식을 이용하였다. 코드는 아래와 같다. sqrt를 사용하기 위해서 #include 를 해주어야 한다. bool isPrime(int p) { if (p < 2) { return false; } double sq = sqrt(p); for (int i = 2; i N; while (N--) {..

https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 유클리드 호제법 유클리드 호제법의 과정은 아래와 같다. 큰 숫자를 작은 숫자로 mod연산을 한다. 작은 숫자를 1번에서 구한 나머지 mod연산을 한다. 위 과정을 mod연산의 결과가 0이 나올때 까지 계속 반복한다. 이때 나누는 수로 사용된 수가 두 수의 최대공약수가 된다. 위 과정을 이용해서 1428과 833의 최대공약수를 구해보도록 하자. mod연산의 결과가 0이 될때 나누는 수는 119였으니 1428과 833의 최대공약수는 119이다. 이를 코드로 구현하면 ..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #include using namespace std; int T, M, N, K; int map[60][60]; int moveX[4] = { 0,1,0,-1 }; int moveY[4] = { 1,0,-1,0 }; void reset() { for (int i = 0; i < 60; i++) { for (int j = 0; j < 60; j++) { map[i][j] = 0; } } } void dfs(in..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net dfs/bfs구현 #include #include #include #include using namespace std; vector edge[1001]; int check1[1001]; int check2[1001]; void dfs(int start) { check1[start] = 1; cout M >> S; while (M != 0) { int a, b;..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 처음에는 아무 생각 없이 정렬해서 풀다가 틀려서 봤더니 메모리 제한이 8MB였다. 구글링을 해보니 수를 모두 입력받아서 저장하면 메모리를 초과하게 되니 입력받은 숫자의 개수를 세는 식으로 접근해야 한다고 한다. 즉 [5, 2, 3, 1, 4, 2, 3]을 입력받았을 때 각 숫자를 입력받아 저장하는 것이 아니라 0으로 초기화 된 배열의 n번째 인덱스를 추가해주는 식으로 풀어 주어야 한다. 정답 코드는 아래와 같다. ..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 아이디어 아홉 난쟁이의 키를 모두 벡터에 넣은 뒤 합(sum)을 구한다. 그리고 sum과 100의 차를 구해 n1이라 하자. 그런 뒤 이중 포문을 이용해 벡터의 값 중 2개를 골라 더한 값이 n1일때 이중포문을 탈출한다. 그리고 벡터에서 해당 원소들을 지워준 뒤 정렬하여 출력한다. 조금 더 자세히 설명하자면 아래의 그림과 같다. i=0~7, j=i+1~8을 반복하는 이중 포문을 만들어 위와 같이 하나씩 더..