Ikjo's Technology blog

문제 설명 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 접근 방법 해당 문제는 백트래킹을 이용하여 해결할 수 있었습니다. 우선 주어진 스도쿠 데이터에서 빈 칸(0)의 개수를 카운팅해서 백트래킹 시 최대 depth(깊이)로 설정했습니다. 이후 9 * 9 스도쿠 판 좌표 (1, 1) 지점부터 마지막 (9, 9) 지점까지 순차적으로 백트래킹하면서 빈 칸을 채워나갔습니다. 해당 빈 칸을 채울 때는 우선 해당 빈칸에 나올 수 있는 숫자 목록을 구해내도록 했습니다. 이때 해당 빈 칸에 나올 수 있는 숫자들은 해당 빈..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 문제에서 나오는 그림이 주는 압박감 대비 상대적으로 해결하기 쉬웠던 문제였습니다. 문제에 접근했었던 방법은 단순했습니다. 일단 주어지는 직선 정보들을 통해 "교점"과 "그래프 전체 크기(가로 x 세로)"를 구한 후 그래프 상에 교점을 표기하여 이를 문자열 배열로 반환하는 것이었습니다. 교점을 구하는 것은 문제에서 주어지는 다음 참고사항으로 쉽게 구할 수 있었습니다. 이를 바탕으로 교점을 구하는 로직을 작성했습니다. private long[] getPoint(int[] line1, int[..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 길이가 10억인 도로가 있을 때, 도로 상 위치 1부터 위치 10억까지 각각의 위치에 1번 블록 ~ 1천만 블록을 문제에서 주어진 규칙대로 배치해야한다. 이때 도로 상 각각의 위치에 올 수 있는 숫자 블록에는 일종의 규칙이 있다. 위치를 나타내는 해당 수(1 ~ 10억)가 "소수"일 경우에는 반드시 1이라는 점이다. 소수는 1과 1이 아닌 자기 자신으로만 나눠지는 수로서 1 외에는 n * 2, n * 3, n * 4, ... 등의 값의 형태를 띄는 숫자 블록이 나올 수가 없다. 이를 위해..

문제 설명 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근 방법 다이나믹 프로그래밍(메모이제이션 기법)을 통해 문제를 해결할 수 있었습니다. 어떻게 값을 메모이제이션 할 수 있을까 고민하던 중 그림으로 그려보다가 아이디어를 떠올릴 수 있었습니다. 위 그림을 통해 다음과 같은 사실을 알 수 있습니다. 세 개의 칸 중 왼쪽 칸의 값은 바로 위 칸의 값과 그 오른쪽 칸의 값에만 의존적입니다. 세 개의 칸 중 가운데 칸의 값은 위에 있는 세 개의 칸 값에 의존적입니다. 마지막으로, 세 개의 칸 중 오른쪽 칸의 값은 바로 위 ..

문제 설명 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 방법 우선 인자로 주어진 화살 n발에 대해서 백트래킹을 통해 라이언이 0점 ~ 10점에 대해 쏠 수 있는 모든 경우의 수를 탐색하도록 했습니다. private void bow(int[] lionInfo, int index, int depth) { if (depth == n) { return; } for (int i = 0; i = lionInfo[i]) { apache += score; } else { lion += score; } } return apache - lion; } 위에서 구한 점..