다희의 코딩 성장일기

[ 문제 ] [백준] 7490. 0 만들기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net # 접근 방법 및 풀이 dfs 문제다. 문제 자체는 어렵지 않았는데 첫번째 풀이로 풀고 나서 다른사람 코드 찾아보니 dfs재귀로만 풀어서 다시 풀어봤다. 첫번째 풀이는 "+, -, 공백" 3가지를 하나씩 선택해가면서 N까지 String 식을 만들었다. 이때 식에 공백이 들어간 부분은 replaceAll로 공백을 ""로 변경했다. 1 2+3일 경우, 공백을 ""로 만들면 12+..

[ 문제 ] [백준] 15566. 개구리1 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/15566 15566번: 개구리 1 연못 안에 개구리들이 있을 수 있는 연꽃 N개와, 연꽃 사이를 연결하는 다리 역할의 통나무 M개가 있다. 같은 연꽃 쌍을 연결하는 통나무의 개수는 1개 이하이다. 여기에 N마리의 개구리가 각각 www.acmicpc.net # 접근 방법 및 풀이 완탐 + 백트래킹으로 풀었다. 개구리는 최대 N개고 각 개구리마다 선호하는 연꽃번호는 1~2개씩 있다. 각 개구리마다 선호하는 연꽃으로 선택해서 연꽃마다 개구리 배치를 다 해준다. 이때 개구리를 연꽃에 배치하는 모든 경우의 수는 개구리마다 선택지가 각 최대 2개씩이므로 2^N이다. N이 최대 15이..

[ 문제 ] [백준] 12100. 2048 (Easy) (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net # 접근 방법 및 풀이 완탐 + 백트래킹 문제다. dfs로 상하좌우 4방향에 대해서 5회까지 다 이동시켜보고 그때 최대값을 구하면 된다. 여기서 백트래킹은 방향을 정하고, 그 방향으로 이동시키기 전에 먼저 원본 map상태를 백업해두어야한다. 어떤 방향으로 블럭을 이동 시킨후에 다음회..

[ 문제 ] [백준] 1463. 1로 만들기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net # 접근 방법 및 풀이 DP 기초 문제다. DP테이블을 만들어 값을 어떻게 저장하고 저장한 값을 어떻게 활용할지 생각해본다. 접근방식이 바로 생각 안날때는 N이 가장 작은값일때부터 구해보면 된다. N = 1 2 3 4 5 6 7 8 9 10 0 1 1 N이 1일때는 연산할 필요가 없으므로 0번, 2일때는 2로 나누어지는 연산을 통해 1이되므로 1번, 3도 마찬가지로 1번이다. 4부터 값을 천천히 살펴보면 주어진 연산 세가지로 떠올려보면..

[ 문제 ] [백준] 1522. 문자열 교환 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net # 접근 방법 및 풀이 아이디어를 떠올리기가 어려운 문제다. a를 모두 연속적으로 만들기 위해서 먼저 주어진 문자열에서 a의 길이를 센다. a가 연속적이라면 교환을 통해서 해당 a의 길이만큼 연속적으로 배치가 된다. 예를들어, "ababab"라면 a가 3개가 있으므로 a는 길이 3이된다. 따라서 a를 모두 연속적으로 만들기 ..

[ 문제 ] [백준] 23290. 마법사 상어와 복제 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net # 접근 방법 및 풀이 일단 내가 다른 사람들 풀이와 다른점은 물고기 리스트를 3차원 배열로 표현하지 않고 HashMap으로 관리했다. static HashMap fish; 를 선언해서 key값에 Point 클래스로 물고기의 위치 Point.x, Point.y로 만들고, 해당 위..