PS/boj5 [BOJ] 백준 1932번 : 정수 삼각형 백준 1932번 : 정수 삼각형 문제 : https://www.acmicpc.net/problem/1932 코드 경로를 따라가며 정수 삼각형의 해당 수를 선택했을 때 선택된 수의 합을 저장하는 dp 2차원 리스트를 생성한다. dp는 정수 삼각형의 크기와 같다. 삼각형의 맨 위층은 정수 하나이므로 dp에 그대로 입력값을 저장한다. 삼각형의 두번째 층 부터 맨 아래 까지는 하나의 층에서 왼쪽부터 오른쪽으로 이동하며 dp값을 갱신한다. 하나의 층 내에서 가장 왼쪽 값(j = 0)은 대각선 위층의 오른쪽 값으로 부터만 선택 될 수 있다. dp에 위층의 대각선 왼쪽값은 존재하지 않음. 여기에 현재 선택된 수를 더해 dp에 저장한다. 마찬가지로 하나의 층 내에서 가장 오른쪽 값(j = i - 1)은 대각선 위층의 .. 2022. 1. 11. [BOJ] 백준 24049번 : 정원 (Easy) 정원(Easy) 문제 : https://www.acmicpc.net/problem/24049 문제 세로길이 n, 가로길이 m이 첫번째 줄에 입력으로 주어진다. 정원의 가장 왼쪽 n개의 꽃 색깔이 두번째 줄에 입력으로 주어진다. 정원의 가장 위쪽 m개의 꽃 색깔이 세번째 줄에 입력으로 주어진다. 왼쪽과 위쪽 칸에 심어져 있는 꽃의 색을 보고, 두 꽃의 색이 같으면 노란색 꽃, 다르면 빨간색 꽃을 심는다. 노란색 꽃은 0, 빨간색 꽃은 1로 표현한다. 결과로 n행 m열 칸의 꽃의 색 출력한다. 코드 입력으로 주어지는 행, 열의 정보를 포함한 그래프를 그리기 위해 가로 m + 1 크기, 세로 n + 1 인 배열을 만든다. 1, 1 칸부터 차례로 돌며 왼쪽과 위쪽 꽃의 색을 비교해 현재 칸에 꽃의 색을 정한다... 2022. 1. 4. [BOJ] 백준 24039번 : 2021은 무엇이 특별할까? Good Bye, BOJ 2021! A번 - 2021은 무엇이 특별할까? 문제 : https://www.acmicpc.net/problem/24039 문제 연속한 두 소수의 곱으로 이루어져 있으면 특별한 수라 부른다고 약속한다. 주어진 수 N보다 큰 특별한 수 중 가장 작은 수를 구한다. 코드 약수는 대칭으로 존재하기 때문에 특정수의 제곱근값보다 작은 수의 범위에서 약수가 존재하지 않으면 제곱근값보다 큰 범위의 수에서도 약수가 존재하지 않는다. 이 점을 활용하여 소수 판별 함수 is_prime_num() 의 경우 소수 여부를 판단할 숫자가 num일 때 num의 제곱근 만큼만 반복문을 돌게 하여 연산횟수를 줄인다. 2부터 차례로 증가시키며 소수인 수를 구해 소수이면 리스트에 저장한다. 소수를 2개 찾았을 .. 2022. 1. 4. [BOJ] 백준 15649번 : N과 M (1) 백준 15649번 : N과 M (1) 문제 : https://www.acmicpc.net/problem/15649 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 코드 백트래킹 문제 백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘. backtracking(k) 는 arr(k) 를 .. 2021. 12. 17. [BOJ] 백준 1260번 : DFS와 BFS DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V 입력. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력. 탐색 시작 정점 V부터 방문된 점을 순.. 2021. 11. 29. 이전 1 다음