두부의 코딩일기

https://www.acmicpc.net/problem/1475 1475번: 방 번호 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 오랜만에 쉬운 문제 등장. 0-9번까지 숫자를 넣어주기 위한 cnt 배열을 생성해주고, 방 번호 N을 charAt으로 잘라서 배열에 입력해준다. charAt으로 잘라서 int형 배열에 입력하게 되면 아스키코드 값으로 변환되서 들어오기 때문에 숫자 1로 변경해주기 위해서 아스키코드 값이 48인 '0'을 빼주면서 배열에 입력해준다. int num = N.charAt(i) - '0'; 배열에 입력해줄 때 해당 숫자의 인덱스를 +1 시켜주면 된다. 또한 6과 9를 뒤집어서 사용할 수 있기 때문에 ..

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 이분 탐색을 이용해서 풀어야하는 문제이다. 잘 모르겠다면 아래의 포스팅을 먼저 보고 오는 걸 추천한다. https://sookr5416.tistory.com/146 자바 이분 탐색 Arrays.binarySearch() 메서드 정의 및 사용 방법 알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서..

안녕하세요. 두부입니다. 오늘은 문자열을 분리하는 방법 중 하나인 StringTokenizer 클래스에 대해서 알아보겠습니다. StringTokenizer 클래스 정의 StringTokenizer 클래스는 주로 BufferedReader 클래스의 메서드로 입력을 받을 때 사용합니다. 특정 문자를 기준으로 문자열을 여러 개의 토큰으로 분리하는 클래스입니다. 우선 StringTokenizer 클래스를 사용하려면 라이브러리를 임폴트 해주어야 합니다. import java.util.StringTokenizer; StringTokenizer 생성 // 띄어쓰기 기준으로 문자열 분리 StringTokenizer st = new StringTokenizer(문자열); // 구분자 기준으로 문자열 분리 StringTo..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 풀이 이번 문제는 예제가 7개나 있는 고마운 문제이다. 매번 알고리즘 문제를 풀면서 반례를 찾는게 여간 쉬운 일이 아닌데 정말 고맙다. 8x8 이상의 크기를 입력하고 상하좌우 한 칸씩 색깔이 다른 8x8 크기의 체스판을 만드는데 색칠이 잘 못된 최소 개수를 구하는 문제이다. 만약 10x10 크기의 배열이 입력됐다고 하면 자를 수 있는 경우의 수는 얼마나 될까? 10x10 크기가 주어지면 경..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 이번 문제는 다이나믹 프로그래밍(dp) 문제이다. 다이나믹 프로그래밍에는 Bottom-up 방식과 Top-down 방식이 있는데 이 문제에서는 둘 다 사용이 가능하다. 필자는 Bottom-up 방식이 먼저 떠올라서 반복문으로 풀었다. 우선 이 문제에는 "큰 수로 나누는 게 무조건 좋다"의 함정이 있다. 예제 2번을 보면 쉽게 이해할 수 있다. 큰 수(2)로 먼저 나누는 방법은 10 → 5 → 4 → 2 → 1로 4번의 연산을 거치지만, 1을 먼저 빼고 3으로 나누게 되면 10 → 9 → 3 → 1로 3번의..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 이전에 풀었던 유기농 배추와 동일한 문제인데 난이도가 아주 조금 올라갔다. 아파트 단지 개수뿐만 아니라 단지 내에 몇 개의 집이 있는지를 구해야 하는 문제로 유기농 배추 문제에서 몇 가지 코드만 추가해주면 쉽게 풀 수 있다. 유기농 배추 문제와 달랐던 건 배열의 모양과 입력할 때이다. 예제를 살펴보면 '0110100'로 들어오는데 한 자리씩 잘라서 int형 배열에 넣어줘야 한다. map[i][..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 대표적인 dfs와 bfs 알고리즘 문제 중 하나이다. 필자는 재귀함수를 이용한 dfs가 제일 편하고 익숙해서 이걸로 해결했다. 1. N x M 크기의 int형 배열 2개를 만들어준다. 배추밭(map)과 방문 여부(check)를 기록할 배열이다. 2. 모든 배추밭을 다 돌면서 방문하지않은 곳의 인접한 배추를 찾으면 된다. if (x < map.length-1 && map[x+1][y] == 1 && che..

엑셀 작업을 하다보면 데이터 중간에 있는 빈 셀을 찾아서 모두 삭제해야되는 경우가 있습니다. 이러한 경우 하나씩 찾아서 삭제한다는 것은 매우 비효율적인 방법인데요. 엑셀에서는 한 번에 빈 셀이 포함된 행을 다 지울 수 있는 기능이 있습니다. 지금부터 그 기능에 대해서 알아보겠습니다. 우선 예시 데이터를 보겠습니다. 아래의 데이터는 임의로 입력한 데이터이기 때문에 현실과 무관합니다. [회사대출] 열에서 빈 셀을 찾아서 모두 삭제하려면 매우 번거롭습니다. 1. [찾기 및 선택] 메뉴에서 [찾기] - [이동 옵션]을 선택한다. 2. [빈 셀]을 선택 후 확인을 누르면 선택한 영역에 모든 빈 셀만 멀티 선택된다. 3. 멀티 선택된 빈 셀에서 오른쪽 클릭을 누르고 [삭제]를 클릭한다. 4. [행 전체]를 선택 후..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 문제 설명이 매우 길어서 어렵게 느껴지지만 생각보다 쉬운 문제이다. N개의 도시와 N-1개의 도로가 있다. 그리고 도시에는 리터당 가격이 적혀있고 1리터당 1km를 갈 수 있다. 최소한의 비용으로 도시 A부터 D까지 가려면 어떻게 해야 될까? 바로 리터당 가격이 저렴한 기름을 넣는 것이다. 예제를 한 번 풀어보겠다. 첫 번째 도시에서 두 번째 도시로 가려면 5원짜리 기름을 2L..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 회의가 겹치지않도록 최대한 많은 회의를 배정하는 게 이 문제의 목표이다. 쉽게 말해서 이전 회의 종료 시간과 이후 회의 시작 시간이 겹치지 않으면 된다. 그리고 최대한 많은 회의를 하려면 종료 시간이 짧은 회의를 선택해야한다. 우선 문제를 쉽게 해결하기 위해서 종료 시간을 오름차순으로 정렬해야한다. Arrays.sort(times, new Comparator() { @Override public int compare(int[] o1, int[] o2) { // 종료 시간이 같다면 시작 시간이 빠른순으로 정렬..