알고리즘/문제풀이 - 백준

백준 2447 별 찍기 - 10

문제 : https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 � www.acmicpc.net 서론 스스로 해결하지 못한 문제. 출력결과를 배열에 넣는다는 생각을 못했고, 바로 출력하려고 시도하다 못풀었다. 그런데 바로 출력해서 푸신 분들도 있다. 존경스럽다. 아래 코드는 배열에 넣는 방식으로 풀었다. 풀이 n이 3일때의 출력결과는 다음과 같다. 3*3 행렬에서 정중앙(1행 1열)만 공백처리 한다. * * * * * * * * n이 9일때의 출력결과는..

2019. 7. 5. 19:47
알고리즘/문제풀이 - 백준

백준 2562 최댓값

문제 : https://www.acmicpc.net/problem/2562 서론 c++의 max_element를 활용해본 문제 아이디어 9개의 수를 벡터에 넣고 최대값은 배열이나 벡터의 최대값을 리턴해주는 max_element를 이용한다. max_element는 최대값의 주소를 리턴하므로 포인터 연산자를 붙인다. 최대값의 번지수는 max_element로 얻어진 최대값의 벡터주소에서 벡터의 시작주소를 빼고 +1 하면 얻을 수 있다. 구현 /c++ #include #include #include using namespace std; vectorv; int main() { int n; n = 9; for (int i = 0; i > tmp; v.push_back(..

2019. 7. 5. 15:16
알고리즘/문제풀이 - 백준

백준 1003 피보나치 함수

문제 : https://www.acmicpc.net/problem/1003 서론 DP문제이며 메모이제이션을 이용하여 풀이했다. 아이디어 n 0 1 2 3 4 5 6 7 8 피보나치 0 1 1 2 3 5 8 13 21 0의 개수 1 0 1 1 2 3 5 8 13 1의 개수 0 1 1 2 3 5 8 13 21 위 표를 보면 규칙성이 있는데, 피보나치 수열과 1의 개수 수열은 같다. n이 0일때를 제외하고, 피보나치 수열의 n은 0의 개수 수열의 n+1과 같다. 따라서 0의 개수는 n번째 피보나치수를, 1의 개수는 n-1번째 피보나치 수를 출력하면 된다. 메모이제이션 함수에서 fib(n) = fib(n-1) + fib(n-2)를 계산할때 이미 fib(n-1)과 fib(n-2)를 이전에 계산한적이 있어서 배열에..

2019. 6. 28. 21:35
알고리즘/문제풀이 - 백준

백준 9663 N-Queen

문제 : https://www.acmicpc.net/problem/9663 서론 백트래킹을 이해하기 위해 풀어본 문제 퀸이 위치할 수 있는 조건을 만드는것, 퀸이 놓일때 이전에 놓인 퀸들을 모두 고려해야하는것, 재귀를 시작할 위치를 지정하는것을 생각하는데 꽤나 오래걸렸다. 걸린시간대비 결과물이 짧은 코드이지만 간결하게 나온것 같아서 만족한다. 아이디어 & 풀이과정 DFS 조건을 만족하려면 각 행에는 하나의 퀸만 둘 수 있다. DFS를 이용하여 1행부터 n행까지 각 행마다 하나씩 퀸을 두면서 가능한 모든 경우의 수를 탐색한다. set A 1행 1열에 퀸을 하나 놓고 행을 증가시켜 모든 열을 탐색한다. 2행 1열에 퀸을 놓아보지만 조건을 만족하지 않으므로 리턴한다. 2행 2열도 안되므로 리턴 2행 3열은 가..

2019. 6. 28. 18:17
알고리즘/문제풀이 - 백준

백준 1920 수 찾기

문제 : https://www.acmicpc.net/problem/1920 서론 이진탐색 문제 구현 //c++ #pragma warning (disable : 4996) #include #include #include using namespace std; int a[100001]; int n, m; int bs(int target) { int start = 0; int end = n - 1; while (start > n; for (int i = 0; i > m; for (int i = 0; i < m; i++) { int target; scanf("%d", &target); printf("%d\n", bs..

2019. 6. 27. 21:15
알고리즘/문제풀이 - 백준

백준 1504 특정한 최단 경로

문제 : https://www.acmicpc.net/problem/1504 서론 우선순위 큐를 이용한 다익스트라 알고리즘으로 풀이했다. 아이디어 다익스트라 알고리즘은 1 -> 2 -> 3-> 4가 최단경로일때 1에서 4까지의 최단경로는 1~2까지의 최단경로를 포함하고 2~3까지의 최단경로를 포함한다. 즉 목적지까지의 최단경로는 중간지점들의 최단경로 합이다. 두개의 정점이 n1, n2일때 시작정점부터 두개의 정점을 거쳐서 종료정점까지 가는 방법은 1. 시작정점 -> n1 -> n2 -> 종료정점 2. 시작정점 -> n2 -> n1 -> 종료정점 두개의 방법이 있다. 1번 방법은 시작정점 -> n1의 최단경로, n1 -> n2의 최단경로, n2 -> 종료정점의 최단경로의 합을 구하면 되고 2번 방법도 마찬가..

2019. 6. 27. 20:01