아라찌

문제 https://programmers.co.kr/learn/courses/30/lessons/12953 자연수 array 입력받으면 array 수들의 최소 공배수 return 접근 방법 유클리드 알고리즘을 사용하면 두 수의 최소공배수를 빠르게 구할 수 있다. > 유클리드 알고리즘 두 수 a, b가 있으면 최소 공배수는 a*b / 최대 공약수 인데, 최대 공약수 구하는 방법은 r = a&b 에서 나눈 나머지를 r이라고 하면 if r == 0 {b는 최대 공약수} else { ​ b = a ​ a = r ​ // 로 해서 다시 반복 } 하다 보면 최대 공약수가 구해진다. 위 과정은 소인수 분해를 하는 과정을 사용한 것이다. 최대 공약수를 구했으면 이 값을 이용해 최소 공배수를 구할 수 있다. 최소공배수 ..

문제 자연수 n을 입력받음 n*n 체스판에서 퀸이 서로 공격할 수 없게끔 배치할 수 있는 경우의 수 리턴 접근 방법 dfs에서 모두 돌리지 않고 특정 조건만 돌려주는 백트레킹 접근 퀸은 가로 세로 대각선 공격을 함으로 라인별로 하나씩 배치해주면 가로 체크할 필요가 없으니 라인별로 dfs 돌아주되, 세로, 대각선을 체크하면서 불필요한 부분들 continue로 최적화 대각선의 경우 한 라인씩 전진할 때마다 좌우 shift 코드

문제 https://www.acmicpc.net/problem/9663 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 접근 방법 백트레킹 문제. dfs로 접근하되, 필요없어 보이는 노드는 무시하며 탐색(프루닝) 처음엔 2차원 배열로 둘 수 있는 공간 true 둘 수 없으면 false 로 두고 채크하는식으로 풀었는데 시간초과.. 불필요한 부분들 줄여가면서 라인 한줄만 체크하면 된다는걸 알게되서 대각선 체크를 굳이 다 하지 말고 depth 한칸당 좌우 shift를 해줌으로써 해결 코드 풀이 1 (시간초과 ㅠ) 풀이 2(통과)

문제 https://www.acmicpc.net/problem/1780 n*n 크기의 수를 입력받음 (n받고, n 만큼 한라인씩 입력받음) 각 칸에는 -1, 0 , 1 중 하나의 값을 입력받음 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이런 식으로 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성 접근 방법 음.. 1번 2번 로직대로 메소드를 짜고 while 돌리면 되지 않을까? 종이가 같거나 라인크기가 3일때 계산 후 나오고.. 범위가 크기 때문에 dfs으로 해야할 것 같기도..

문제 a = 2차원 배열(행렬처럼) b = 2차원 배열(행렬처럼) 행렬 a*b 를 2차원배열 행렬처럼 해서 array 리턴 제한 조건 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다. 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다. 곱할 수 있는 배열만 주어집니다. 입출력 예 arr1 arr2 return [[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]] [[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]] 풀이 순서대로 곱해서 리턴...