웹개발 성장기

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..

코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 풀이 카카오 2020 블라인드 1차코테에 나왔던 문제이다. 그당시 예외처리하고 하느라 은근 오래걸렸던 것 같은데 그동안 짬바(?)가 쌓였는지 저번보단 적게, 수월하게 풀었다 특정한 규칙이 보이지 않아 모든 케이스를 다 구해야 하구나.. 생각했다. 문자열을 자를 수 있는 개수를 전부 돌려보면서 비교했다. StringBuillder로 하나씩 붙여나갔다. 자른 문자열 이전 값과 다음 값을 비교해주며 cnt가 2 이상이면 숫자까지 붙여주면 된다. substrin..

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

원래 정규표현식은 이해하기 어렵고 쓰기 복잡해서 꺼리고 있었다. 이번주 토요일에 있을 카카오 신입공채 코딩테스트를 대비하기 위해 작년 1차 문제를 풀어보다 "아 이문제 정규식 쓰면 정말 간단하게 풀릴것 같은데?!" 하는 생각이 들었다. (바로 이문제이다) 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 알파벳, 숫자, 특수문자 남기기에는 성공했다. 하지만 .의 개수가 2개 이상일 때 전부 . 하나로 바꾸기 이것도 분명 정규식으로 할 수 있을것 같은데 못찾았다... 그래서 결국 split("\\.")으로..

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