YG - 96년생 , 강아지 있음, 개발자 희망

순열 순서가 존재하고, N개 중 K개를 선택하는 경우 순열이라고 합니다. visited로 0부터 N까지 방문했는지 확인하고 매번 0부터 N까지 반복문을 동작하여 반환합니다. Permutation const visited = Array.from({ length: N }, () => false); const combi = (num, arr) => { if (num === 0) { console.log(arr); return; } for (let i = 0; i < N; i++) { if (visited[i]) continue; visited[i] = true; combi(num - 1, [...arr, i]); visited[i] = false; } }; /** * N은 전체 개수, K는 뽑고자 하는 개수 ..

https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 풀이 방법 지문의 조건처럼 왼쪽으로 이동할 수 있으면 이동 후 청소를 하며 방향을 전환해야 한다. 그래서 각 방향마다 dx,dy 배열을 어디서 탐색할지 바꾸어 주어야 하는데 dir 을 이용하여 dir + i로 북 , 서 , 남 ,동을 순서대로 탐색하도록 하였고 만약 청소를 할 수 있다면 청소를 한 후 break 문을 통해서 반복을 끝내주고 청소를 하지 못했다면 후진을 하여 뒤에 벽이 나올 때 까..

구글에 14500 테트로미노 문제를 검색했을 때 DFS, 백트래킹 풀이만 나오고 저와 비슷한 풀이는 발견하지 못하여서 배열을 돌려서 푼 문제 풀이를 올립니다. 저는 우선 일부로 DFS , 백트래킹으로 풀지 말아야겠다가 아닌 생각을 하지 못해서 어떻게 풀어야 할까 하다가 처음에는 모든 종류들을 만들어서 문제를 풀려고 하였으나 문제를 풀다가 제가 실수해서 틀릴 것 같았기 때문에 그다음으로 생각난 방법으로 회전을 생각하지 않고 대칭, 일반적인 테트로미노들만 체크를 하였고 그리고 배열을 90도씩 돌려서 체크를 하는 방법으로 문제를 풀게 되었습니다. #include using namespace std; int n, m; int arr[505][505]; int tmp[505][505]; int func1(int ..

스타트와 링크 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 구글에 14889 스타트와 링크를 검색했을 때 DFS, 백트래킹 풀이만 나오고 저와 비슷한 풀이는 발견하지 못하여서 prev_permutation을 활용한 풀이를 올립니다. bool tmp 라는 배열을 이용해서 n/2 만큼 tmp[i] = 1을 해주어 절반을 1로 만들어 주었고 prev_permutation을 사용해 각각 스타트팀 , 링크 팀의 순서를 다르게 만들어 주었습니다. 점수를 계산한 방법은 tm..

문제 이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩 니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 풀이 function solution(m, arr) { let answer = 0; let dy = Array.from({ length: m + 1 }, () => 0); for (let i = 0; i = pt; ..

냅색 알고리즘이란? 배낭 문제는 조합 최적화의 유명한 문제이다. 간단하게 말하면, 한 여행가가 가지고 가는 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때, 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 문제 다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다. 풀이 function solution(m, coin) { let answer = 0; let dy = Array.from({ length: m + 1 }, () => 1000); dy[0] = 0; for (let i = 1; i < coin.length; i++) { for..

문제 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다. 철 수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다. 철수가 개울을 건너는 방법은 몇 가지일까요? 풀이 function solution(n) { let answer = 0; let dy = Array.from({ length: n + 2 }); dy[1] = 1; dy[2] = 2; for (let i = 3; i

동적 계획법(dynamic programming, DP)이란? 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다. 문제를 보며 예시를 들어 보겠습니다. 문제 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2로 5가지이다. 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가? 먼저 1번 계단을 오르는 방법의 수는 1가지입니다. 그리고 2번째 계단을 오르는 방법의 수는 2가지이고요 그렇다면 3번째는 어떨까요? 3번째에 다다르는 방법은 1번째에서 오던가 혹은 2번째 계단에서 오던가 2가지입니다. 그런..