웹개발 성장기

13706번: 제곱근 첫째 줄에 양의 정수 N이 주어진다. 정수 N의 제곱근은 항상 정수이며, N의 길이는 800자리를 넘지 않는다. www.acmicpc.net 이분탐색 문제. 그런데 이제 범위가 큰... N의 길이는 800자리를 넘지 않는다 문제에 명시된 N의 범위가 어마무시하기 때문에 무조건 String으로 처리해줘야 하지만 다행스럽게도 Java에는 범위가 infinite한 BigInteger라는 class가 존재한다. (공식문서 참조) BigInteger (Java SE 11 & JDK 11 ) Immutable arbitrary-precision integers. All operations behave as if BigIntegers were represented in two's-compleme..

2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 태그는 다익스트라이지만 우선순위큐로도 풀 수 있다. (사실 우선순위큐로 풀었는데 질문글 보니 다익스트라 코드도 있어서 다익스트라로도 풀어봄...ㅎㅎ) 우선순위큐 풀이 좌표 정보 + 검은 방을 흰 방으로 바꾼 횟수를 class로 선언한 후 검은 방을 흰 방으로 바꾼 횟수가 작은 순으로 큐에서 뽑으면 된다. visited 배열로 방문 유무를 확인하며 다음 좌표가 검은방이면 cnt + 1, 흰 방이면 cnt값을 큐에 넣는다. 적은 횟수부터 탐색하기 때문에 끝방 좌표에..

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net DP문제이고 두 가지 방식으로 풀 수 있다. Top-Down 풀이 DFS 재귀를 이용한다. 목적지인 arr[N - 1][N - 1]에 도달했을 경우 1을 return한다. 처음 방문하는 위치일 경우에만 DFS를 수행한다. 정답일 경우 1이 계속 return하면서 올 것이므로 cnt[x][y] += solve(nx, ny); 을 해준다. 그렇지 않으면 기존 값 (cnt[x][y])을 return한다. 방문체크는 처음에 cnt배열을 -1로 초기화한 후 방..

10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 최신순으로 끼워넣으려니 복잡해서 단순하게 생각했다. Queue members[201] 배열을 선언하고 나이만 뽑아서 member[age]에 쏙쏙 넣은 후 마지막에 큐를 돌리면서 출력하면 끝 실버 문제들은 단순하게 푸는게 최고인 것 같다. 코드 import java.io.*; import java.util.*; public class Main { static int N; static Queue[] members; public static void main(Strin..

풀이 7682번: 틱택토 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입 www.acmicpc.net X빙고, O빙고 둘 다 존재할 경우 invalid인걸 놓쳐서 헤메고 있었음 논리적으로 되는 경우, 안되는 경우를 다 따져야 하는 문제!! 알고리즘같지 않은(?) 문제였다. 맨처음에 입력받은 String에서 O의 개수, X의 개수를 센다. 가로, 세로, 대각선 경우를 보면서 빙고일 때 O 빙고의 수, X 빙고의 수도 센다. X 빙고의 수 > 0일 때 O 빙고의 수 > 0이면 이미 X 빙고가 나왔을 때 게임이 종료되었어야 하는데 아닌 경우이므로 ..

1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 반례가 엄청 많이 존재하니 혹시라도 틀렸다면 질문게시판의 반례모음집 게시글을 참조하며 고쳐나가면 좋다. 어떻게 풀지 생각하다 BFS N부터 시작해서 100까지 가는 방법을 찾았다. 문제 분류는 브루트포스로 되어있는데 말 그대로 브루트포스로 0부터 1000000까지 모든 경우를 계산하는 방법도 있다. N에서 출발하는데 현재 숫자가 누를 수 있는 번호이면 (isPossibleToPress(int n)으로 각 자릿수에 누를 수 없는 수가 있는지 ..

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 BFS로 네 가지 경우 (DSLR)를 전부 탐색한다. int, String을 저장하는 custom class DSLR을 구현했다. 큐에는 (현재 숫자, 지금까지 부른 명령어)를 저장한다. 탐색하다가 현재 숫자가 B가 되면 지금까지의 명령어를 출력한다. visited[]로 숫자 중복 여부를 확인한다. D, S, L, R을 method로 만들어서 사용했다. 코드 import java.io.*; import java.util.*; public cla..

19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 풀이 시간초과가 났던 문제. 검색하여 찾아보니 연료를 무한으로 충전할 수 있어서 그렇다고 한다. 문제에는 적혀있지 않은 예외사항이 두 가지 있다. 택시 기사가 승객의 위치까지 도달할 수 없는 경우 (거리 = INF) 승객을 도착지까지 태울 수 없는 경우 (거리 = INF) 되는지 안되는지 판단할 때 단순히 거리와 연료량 여부로 판단하면 안되고 이 부분도 고려해야 문제가 통과한다. 구현문제라 문제에 충실하면 생각보다 어렵지 않..