Don't give up!

2580번: 스도쿠 (acmicpc.net) 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 하나의 빈칸에 숫자를 올바르게 채워넣기 위해서는 다음의 조건들을 만족해야 합니다. 1. 같은 가로 줄에 있는 숫자들과 중복되는가? 2. 같은 세로 줄에 있는 숫자들과 중복되는가? 3. 3x3으로 정의되는 정사각형 안에 있는 숫자들과 중복되는가? 이러한 방식으로 가능한 숫자를 빈칸에 대입한 후 다른 빈칸에서도 조건을 만족하는 숫자가 존재하지 않는다면 이전 빈칸의 숫자를 바꾸어 반복하는 ..

1753번: 최단경로 (acmicpc.net) 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 주어지는 것은 방향성이 있는 그래프이고 구해야 하는 것은 모든 정점으로의 최단 경로입니다. 시작 정점에서부터 시작하여 연결된 경로의 정점에 가중치를 갱신하는 다익스트라 알고리즘을 사용하고자 하였습니다. 코드 import java.io.*; import java.util.*; class Main { static int V, E, K, INF; static L..

1697번: 숨바꼭질 (acmicpc.net) 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 현재 위치가 X일때 목표지점 K로 이동할 수 있는 방법은 X-1, X+1, X*2로 3가지이지만 만약 X가 K보다 큰 값을 가지고 있을 경우 X+1, X*2는 최단시간을 구하는 데 큰 도움이 되지 않습니다. BFS를 수행하고, 같은 위치에 반복 도달을 검사에서 제외함으로써 문제를 해결할 수 있다고 생각하였습니다. 코드 package com.boj; impo..

1106번: 호텔 (acmicpc.net) 1106번: 호텔 첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 문제에서 유의깊게 보아야 할 부분은 '적어도 C명'이었습니다. 3원을 투자하여 5명을 얻을 수 있다면 적어도 1명을 늘리기 위해 필요한 금액도 3원이며, 적어도 3명을 늘리기 위해 필요한 금액도 3원입니다. 적어도 C명 늘리기 위해 필요한 금액의 최소값은 C부터 C+100명을 늘리기 위해 필요한 금액의 최소값으로 구할 수 있습니다. (주어진 조건에서 비용으로 얻을 수 있는 고객의 수..

코딩테스트 연습 - [1차] 추석 트래픽 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 불량 사용자 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 어떻게 생각하고 문제를 풀었는가? 불량 사용자 아이디의 탐색은 길이가 같아야 합니다. *문자를 0~9, a~z의 문자 탐색이 가능하도록 정규표현식 \w로 변경하여 문자의 탐색을 수행하여 일치하는 아이디들을 찾을 수 있습니다. 주어진 조건에서 순서에 상관없이 아이디 목록이 동일하다면 동일한 케이스로 인식됩니다. 이를 해결하고자 중복을 방지하는 HashSet에 주어진 문자열 배열에서..

코딩테스트 연습 - N-Queen | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 어떻게 생각하고 문제를 풀었는가? 체스판의 크기 N이 12이하의 자연수이므로 가능한 모든 경우를 직접 확인하여 카운트하고자 하였습니다. 1번째 줄부터 k-1번째 줄까지 진행하면서 퀸을 배치하고, 모든 퀸을 배치했을 때 이를 카운트, 다른 열에 배치한 경우에 대해서도 이를 수행함으로써 문제를 해결할 수 있습니다. 코드 import java.util.*; class ..

코딩테스트 연습 - 보석 쇼핑 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 보석 쇼핑 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"] [3, 7] programmers.co.kr 어떻게 생각하고 문제를 풀었는가? 가장 짧은 구간을 구하기 위해서는 전체 보석의 종류를 알아야 하고, 어떤 위치에서 시작했을 때 구간의 길이가 몇인지 확인해야 합니다. 시작 위치는 1번째 보석부터 차례대로 이동하므로 FIFO인 자료구조 Queue에서 원소가 지워지는 과정과 비슷하게 볼 수 있으며, 순서대로 원소를 삽입하면서 Queue에 삽입된 원소의 종류가 전체 보석의 종류와 비슷한 순간을 확인하고 시작 위치를 이동시킬 수 있습니..