Dot Dot Line Dot

title: Programmers - 카드 짝 맞추기 date: 2022-11-01 tags: Algorithm DFS BFS https://school.programmers.co.kr/learn/courses/30/lessons/72415 문제 요약 4x4 격자에 쌍을 이루는 카드가 배치되며, 초기 위치가 주어진다. 카드 선택과 한 칸 이동, 한 방향으로 카드 혹은 격자 끝에 도달하는 행동은 조작 횟수 1회로 판단한다. 카드 쌍이 선택이 되면 해당 쌍이 삭제가 된다. 모든 카드 쌍을 지우기 위한 최소 조작 횟수를 return한다. 문제 풀이 솔직히 어렵지는 않고, 많이 귀찮은 문제였다. 격자의 크기는 4x4, 카드는 최대 12개가 주어진다. 2개가 하나의 쌍이기에 최대 6! * 2^6으로 약 46K의 ..

title: Programmers - 단어 변환 date: 2022-08-11 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/43163 문제 요약 전부 소문자로 이루어지며 길이가 모두 같은 단어가 주어진다. 초기 단어, 목표 단어, 그리고 단어를 모은 vector가 주어지며, 변환시 한 번에 한 개의 알파벳만 변환 가능하다. vector 내부의 단어로만 변환 가능하다. 초기 단어에서 목표 단어로 변환하는 최소 횟수, 변환이 불가능하다면 0을 return한다. 문제 풀이 단어의 최대 길이는 10이다. string을 이용한 처리가 마음에 들지 않아 비트 연산처럼 정수 변수에 담을까 고민하였다. 하지만 최대 1조가 넘..

title: Programmers - 외벽 점검 date: 2022-08-10 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/60062 문제 요약 원형의 외벽과 수리 지점이 주어지며, 각 친구들이 이동 가능한 거리가 주어진다. 최소한의 인원들만 이용하여 수리를 할 수 있다면 최소 인원을, 불가능하다면 -1을 return한다. 문제 풀이 최대 길이는 200, 수리 지점은 15, 수리 인원은 8이다. 범위가 작기에 시간 초과의 걱정 없이 해결 가능한 알고리즘을 작성하면 되는 줄 알았다. 처음에는 원형 벽을 그대로 이용하였다. 각 수리 지점을 순회하는 프로그램은 확인 불가능한 테스트에서 실패가 반복되었으며, 이로 인하..

title: Programmers - 모두 0으로 만들기 date: 2022-08-05 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/76503 문제 요약 트리가 주어지며 노드가 N개, 노드를 연결하는 간선이 N-1개, 각 노드에는 가중치가 주어진다. 연결된 노드일 경우, 한 쪽은 1을 감소시키고 한 쪽은 1을 증가시킬 수 있다. 모든 노드의 가중치를 0으로 만들 수 없다면 -1을, 가능하다면 해당 작업을 최소 몇 번 진행해야 하는지 return한다. 문제 풀이 노드는 300K, 가중치의 절대값은 1M까지 주어진다. 생각보다 노드의 양이 많아 겁을 먹었으나, 간선의 개수는 노드의 개수보다 1개가 작고 트리 구조인..

title: Programmers - 불량 사용자 date: 2022-07-30 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/64064 문제 요약 유저들의 아이디와 제재된 유저의 아이디가 주어진다. 제재된 유저의 아이디 중 일부는 ''로 표기하였으며, ''을 제외한 아이디가 동일하면 제재 대상으로 볼 수 있다. 하나의 제재된 유저의 아이디는 기존 유저들의 아이디 중 여러개와 매칭이 될 수 있다. 제재가 가능한 경우의 수를 return한다. 문제 풀이 삽질을 너무도 많이 반복한 문제이다. DFS 방식을 이용하여 모든 제재된 아이디가 유저에게 할당될 경우, 경우의 수를 하나씩 늘렸다. ..

title: Programmers - 여행경로 date: 2022-07-28 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/43164 문제 요약 항공권을 모두 이용하여 여행경로를 짠다. "ICN" 공항에서 출발하는 여행경로를 짜며, 여러 경로가 존재하면 알파벳 순서가 앞서는 경로를 return한다. 문제 풀이 공항의 이름이 string 3글자이다. string 비교 연산이 이루어지겠으나, overhead로 인하여 속도 측면에서 좋지 않다. 이 3글자를 숫자로 바꾼다. "AAA" 부터 "ZZZ"까지 순서대로 배치할 때의 순서와 동일하다. 숫자로 표시된 티켓을 정렬한다. 여기서 정렬을 하였으므로, 이후 경로는 앞의 ..

title: Programmers - 경주로 건설 - 포기 date: 2022-07-24 tags: Algorithm DP DFS BFS https://school.programmers.co.kr/learn/courses/30/lessons/67259# 문제 요약 2차원 정사각형의 도면이 주어진다. 직선 도로는 100원, 90도로 꺾이는 도로는 500원이 추가로 든다. 길이 N일 때, (0,0)에서 (N-1,N-1) 까지 가는 도로를 설치할 때 최소 비용을 return한다. 문제 풀이 이틀간 이 문제만 계속 시도하였다. 계속하여 정확성 56점에서 실패하며, 테스트 케이스 및 여러 AC 프로그램을 살펴보았으나 도대체 뭐가 문제인지 알아낼 수 없었다. 포기하고 나중에 다시 풀 계획이다. DFS 시도 - BF..

title: Programmers - 조이스틱 date: 2022-07-10 tags: Algorithm DFS https://school.programmers.co.kr/learn/courses/30/lessons/42860 문제 요약 문자열이 주어진다. A로만 이루어진 초기 문자열에서 조이스틱을 조종하여 주어진 문자열을 만들어야 한다. 조이스틱의 최소 조종 횟수를 return한다. 문제 풀이 우선 'A'를 주어진 문자로 바꿀 때, 정방향으로 바꾸는 것과 역방향으로 바꾸는 것 중 횟수가 더 적은 방법으로 count 한다. 가장 중요한 부분은 바꿀 문자를 선택하기 위하여 좌우로 움직이는 것이다. 좌, 우로 움직일 수 있으며, 'A' 문자가 주어지면 바꿀 필요가 없기에 방문하지..

title: Programmers - 양궁대회 date: 2022-07-06 tags: Algorithm DFS BruteForce https://school.programmers.co.kr/learn/courses/30/lessons/92342 문제 요약 어피치가 어드밴티지를 가지는 양궁 대회이다. 어피치가 먼저 화살을 쐈고, 라이언은 어피치의 화살을 보고 가장 높은 점수차이가 나도록 쏴야 한다. 어떻게 쏘더라도 라이언이 우승할 수 없다면 -1을, 가능하다면 화살을 vector에 넣어 return한다. 문제 풀이 문제를 잘 읽자 문제를 잘못 읽어서 한시간 가까이 삽질하였다. 우선 과녁은 11개이며, 라이언은 어피치가 쏜 화살보다 많이 과녁에 맞춰야 점수를 얻을 수 있다. 라이언의 입장에서 점수를 얻거나..

title: Programmers - 피로도 date: 2022-06-25 tags: Algorithm DFS https://programmers.co.kr/learn/courses/30/lessons/87946 문제 요약 현재 피로도, 그리고 던전에 들어가기 위한 최소 피로도와 소모 피로도가 주어진다. 유저가 탐험할 수 있는 최대 던전 수를 구하여 return한다. 문제 풀이 던전의 개수는 8개밖에 존재하지 않으며, 순서에 영향을 받으므로 DFS가 적합하다고 판단하였다. DFS 함수의 최대 호출 횟수는 8! + 1(처음 진입시 1회) = 약 40k이다. 조건이 까다롭지 않으므로 .data 함수 없이 vector에 직접 접근하여도 문제가 없을 것 같다. 프로그램 #include #include using..