Algorithm (66) 썸네일형 리스트형 [ 프로그래머스] 조이스틱 ( 자바 ) programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱을 이용할 때, 일방적으로 왼쪽으로 가거나 오른쪽으로 가는 것이 끝이 아니다. 왼쪽으로 오른쪽으로 언제든지 최소이동을 위해 갈 수도 있음을 알아야 한다. 하지만 일방적으로 모두 왼쪽오른쪽으로 계속 완전탐색을 하는 것도 좋은 방법은 아니다. 엄청난 중복으로 인해서 시간초과가 나는 것이 당연하기 때문이다. 따라서 적절하게 case를 나누어주어야 한다. .. [백준/2805] 나무 자르기 ( 자바 ) www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이진트리를 이용한 최댓값을 구하는 문제이다. 정해진 범위 내에서 최대한의 높이를 잘라서 원하는 길이 M을 얻어야 한다. 1. 익숙한 유형이었는데 실수했던 부분은, min 값을 나무길이의 최소값으로 잡았다. M의 길이는 1부터 20억까지라고 되어 있다. 즉, min값은 나무길이 중 최솟값보다 더 작은 1도 될 수 있다. 정해진 공식에 따라서 문제를 푸는 습관이 었.. [백준/1918] 후위표기식 ( java ) www.acmicpc.net/problem/1918 어떤 표기식보다 후위표기식을 그나마 가장 안다고 생각했는데 알고보니 제대로 안 것이 아니였다. ;; 연산자 우선순위에 따라서 결과값이 바뀌는 것인데, 제대로 고려하지 못했다. 따라서 연산자 우선순위를 고려하여서 수정하였다. 먼저 괄호가 있는 경우와 없는 경우로 나누어야 한다. 괄호가 있는 경우는 쉽다. 괄호가 끝나면 연사자를 stack으로 출력하면 된다. 왜냐하면 괄호는 하나의 연산단위로 계속 묶어주기 때문이다. 하지만 괄호가 없는 경우를 고려해야 한다. 이때 연산자 우선순위를 따져준다. 핵심은, 연산자를 계속 stack에 저장하면서 이전 stack값과 비교하는데, 현재의 자신보다 이전 연산자 우선순위가 같거나 높으면 출력한다. 예를 들어 stack의 .. Union-Find(유니온-파인드) 유니온-파인드는 disjoint sets라는 서로소 집합을 구하는 문제입니다. 서로소 집합이 용어는 어렵지만 공통 원소가 없는 집합들을 뜻합니다. 다음 그림을 보면 8개의 원소가 있고 서로소 집합은 3개입니다. 다음과 같은 유형에서 사용하면 됩니다. (물론 DFS/BFS로도 풀이가 가능합니다!) * 연결 정보가 주어졌을 때 2개의 원소는 서로 같은 집합에 속해 있는가? * 연결 정보가 주어졌을 때 독립적인 섬의 갯수는 몇개인가? Union-Find 관련 문제는 해당 원소들의 부모 정보들을 저장, 비교, 업데이트를 통해서 해결합니다. 따라서 각각 원소들의 부모 정보에 대해서 특별히 신경써주시면 됩니다. Union(결합시키다) : 해당 원소들의 parent를 비교하고 하나로 합칩니다. Find(찾다) : 해.. 1783 : 병든 나이트 ( 백준 / java ) www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net *해결 과정 이 문제는 이동 칸수가 특이합니다. 결론적으로 오른쪽으로만 이동하는 구조입니다. 이 구조를 이용해서 문제를 풀어야합니다. 배열은 최대 각 길이가 20억이 될 수 있기 떄문에 배열을 만들면 터지게 됩니다. 그래서 얼마나 많이 오른쪽으로 잘 이동할 수 있는지 확인합니다. N,M과의 관계를 천천히 살펴봅니다. n=1 : 이동 불가이므로 1을 반환 n=2 : 2,3만 이동 가능하므로 최대 4번 이동 가능 m 연습문제 : 최고의 집합 ( 프로그래머스 / java ) *해결 과정 처음에는 이 문제를 중복 조합으로 접근하였습니다. 혹시 문제가 해결되지 않은 상태에서 이 글을 보신다면 간단하게 접근하여 다시 생각히시기 바랍니다. 아래 간단한 테스트 케이스도 첨부합니다. 힌트는 최대한 공평하게 수를 분배하는 것입니다!! 저도 갈피를 잡지 못해 다른 글을 참고하였고 다시 풀어서 맞았습니다. 참고로 효율성도 요구하는 문제이기 때문에 O(N)시간에 처리가 가능해야 합니다. *테스트케이스 n = 3 / s = 8 / 답 [2,3,3] n = 3 / s = 7 / 답 [2,2,3] n = 4 / s = 14 / 답 [3,3,4,4] 나머지가 있는 경우, 없는 경우 등등 많은 경우들을 나누어서 풀어보았습니다. 그렇게 조건을 걸어서 풀었더니, 제대로 풀리지 않았고 재귀를 생각하였습니다.. 깊이/너비 우선 탐색(DFS/BFS) : 네트워크 ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr *해결 과정 해당 문제는 결론적으로 최적화된 풀이법은 union이라고 합니다. 하지만 저는 문제 유형처럼 DFS나 BFS를 활용하는 방법을 생각했습니다. 그렇게 BFS를 이용하기로 했습니다. 내가 임의로 시작한 0번 노드와 연결되어있는 노드들을 BFS로 쭉 검사하면 됩니다. BFS 함수 한번으로 해결하는 것이 아니라 일단 검사 자체는 주어진 n개를 모두 하는게 핵심입니다.. 깊이/너비 우선탐색(DFS / BFS) : 단어변환 ( 프로그래머스 / java ) programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr * 해결과정 프로그래머스 레벨별 풀이는 모두 유형을 제공하고 있습니다. 이미 힌트를 얻는다는 점에서 해결책을 떠올리는 과정은 성장할 수 없으나 연습하기는 좋습니다. 이 문제는 DFS, BFS 모두로 해결이 가능한 문제입니다. 그 중에 저는 DFS로 풀었습니다. DFS로 풀 때 항상 주의해야 할 것이 있습니다. 종료조건, 반복내용 + .. 이전 1 2 3 4 5 6 ··· 9 다음
