Ikjo's Technology blog

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 처음 접근했었던 방법은 2차원 배열을 생성한 후 해당 2차원 배열로부터 left ~ right 길이의 1차원 배열을 잘라내어 이를 반환하는 것이었습니다. 하지만 인자로 주어지는 n의 최대값은 10의 7승으로 n * n 2차원 배열을 만드는 순간 Outofmemoryerror 에러가 발생하게 됩니다. 즉, 주어진 n에 대해서 2차원 배열을 만드는 게 아니라 left와 right 범위에 해당되는 배열만을 추려낼 필요가 있었습니다. 이때, 문제에서 2차원 배열의 값을 채우는 방법에는 일종의 규..

문제 설명 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 접근 방법 결론적으로 해당 문제는 너비 우선 탐색을 이용하여 해결할 수 있었으나, 처음에는 백트래킹으로 접근 했었습니다. 백트래킹으로 접근, 결과는 시간 초과 입력될 수 있는 명령어에 대한 모든 경우의 수를 고려하고자 했고, 가장 짧은 명령어를 찾기 위해 명령어 조합의 수를 첫째 자리부터 대략 100번째 자리까지(임의로 둔 것) 일일이 백트래킹을 해주도록 했습니다. 탐색 중 타겟 숫자와 동일해지는 순간 해당 명령어를 출력 시키도록 했지만,..

이분 탐색이란? 우선 탐색이란 자료구조, 그래프 등에서 특정한 데이터를 찾는 것을 말한다. 대표적인 탐색 방법으로 '순차 탐색'이 있는데, 이는 어떤 자료구조에서 특정 데이터를 찾기 위해 첫 번째 원소부터 마지막 원소까지 차례대로 확인하는 방법으로 가장 정직한 탐색 방법이다. 하지만 이러한 순차 탐색의 시간 복잡도는 O(N)으로 데이터가 무수히 많은 경우에는 적합하지 않다. 이러한 경우에는 어떤 탐색 방법이 유용할까? 대표적으로 '이분 탐색'이 있다. 이분 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하기 때문에 시간 복잡도가 O(logN)으로 순차 탐색 보다 훨씬 유리한 방법이다. 다만 이분 탐색의 경우 '데이터가 정렬되어 있는 경우'에만 사용할 수 있다는 특징이 있다. 이분 탐색 구현해보기 여러 ..

문제 설명 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 접근 방법 문제의 입력값으로 최초 n개의 각각의 노드별로 부모 노드가 주어지는데, 이를 해쉬 맵 자료구조에 저장합니다. 이때 루트 노드는 부모 노드가 없으므로 루트 노드만 따로 별도의 변수(rootNodeIndex)에 저장해주도록 합니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); St..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 해당 문제는 특정 테이블 형태의 데이터가 주어졌을 때 유일성과 최소성을 만족하는 후보키의 개수를 요구하고 있습니다. 접근 방법으로는 우선 백트래킹을 통해 모든 키에 대한 경우의 수를 구하도록 했습니다. 이때 키의 칼럼 수는 최소 1개에서 최대 릴레이션 상 전체 칼럼 수의 개수(n)와 같습니다. 1개부터 n개까지 순차적으로 백트래킹을 하면서 경우의 수가 만들어지면 해당 키에 대해 유일성과 최소성을 검증(verify 메서드 호출)하도록 했습니다. // ... boolean[] visited;..