이 문제를 이해하는데 쫌 시간이 오래 걸렸다. 간단하게 설명하면 각 칸마다 높이가 있고, 물이 0부터 차 올랐을 때 가장 큰 안전영역 개수를 구하면 된다. 물이 4만큼 차 올랐을 때 안전영역은 아래와 같이 구해진다. 만약에 물이 안차오르면 안전영역은 1이다. 그래서 각 칸의 높이가 전부 1이면 답은 1이다. 물의 최대 높이는 지역의 최대 높이이다. 그래서 물의 높이는 0부터 지역의 가장 큰 수만큼 돌려주면 된다. 물의 높이 0도 신경 써야 하는 이유는 메모에 "아무 지역도 물에 잠기지 않을 수도 있다." 는 조건이 있기 때문이다. [전체 풀이 코드] package baekjoon.classfication.dfs; import java.io.BufferedReader; import java.io.Input..
이 문제는 골드5 문제로 일반 사람과 적록 색약 따로 BFS를 돌려서 풀어야 한다. 맨 처음 문제를 해결할 때는 BFS 돌릴 때 분기를 줘서 해결해보려고 했지만 너무 조건문이 복잡해져서 적록 색약 map을 따로 만들고 G를 R로 변경하는 방식으로 바꿨다. 가독성을 위해 조건문은 최대한 2차 까지만 하려고 노력했다. 최대한 깔끔하게 코드를 작성하는 것이 관건인 문제인 것 같다 [풀이 코드] import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; //https://www.acmicpc.net/p..
이 토마토 문제는 골드5 문제로 실버 단계에서 풀던 bfs 공식 으로 풀리지가 않았다. 기존 bfs의 공식이라 함은 for문을 돌아서 1을 찾은 다음 바로 큐에 담고 방문체크를 한 다음에 bfs를 돌리는 것인데 똑같이 이렇게 푸니 절대로 풀리지 않는 문제가 있었다. 기존 풀이 코드 for (int i = 0; i < mapZ; i++) { for (int j = 0; j < mapY; j++) { for (int k = 0; k < mapX; k++) { if (map[i][j][k] == 1 && !isVisited[i][j][k]) { isVisited[i][j][k] = true; bfs(i, j, k); } } } } 직면한 문제와 해결 방법 만약 입력이 아래 처럼 주어졌을 때 밑에 1을 찾아 바..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이 문제는 (1,1) 위치에서 (N,M) 위치로 가는데 최소 칸수를 구하는 문제이다. 최단 경로 문제는 BFS 를 사용하면 된다고 생각하면 된다. BFS는 갈 수 있는 인접한 경로를 모두 방문하기 때문에 최초 방문된 시점이 출발 노드점에서 갈 수 있는 가장 빠른 경로이기 때문이다. 그래서 이문제도 BFS로 풀면 된다. 최단경로 문제는 BFS로 푼다는 걸 공식처럼 생각하면 된다. 시간 복잡도는 인접 행렬을 사용할거기 때문에 N, ..
BFS(Breadth First Search, BFS)는 주로 최단거리나 최단 시간등 목표 상태에 도달할 수 있는 가장 빠른 경로를 탐색하는데 활용된다. 왜냐하면 BFS는 인접한 노드들에 대해서 모두 방문을 하기 때문에 방문한 시점이 가장 최단 경로의 시점이기 때문이다. BFS 문제 풀이 순서 1. input 단계에서 방문 체크 isVisited 배열과 , 방문 경로 map의 배열, 방문체크 dy, dx 배열을 만든다 2. for문을 돌아서 map에서 방문 위치를 찾아낸다. 3. 찾은 위치를 Queue에 넣고, 방문 체크를 한다. 4. Queue에서 뽑은 map위치에서 방문 경로를 뒤진다. 5. 방문 경로에서 조건에 맞으면 Queue에 넣는다. Queue가 다 비워질때 까지 계속 방문 경로를 뒤지고 조건..
[공부이유] 코딩테스트는 좋은 회사를 가기 위해서는 필수적으로 공부를 해야 한다. 코딩테스트를 안보는 회사도 있지만 그 회사가 코딩테스트를 보는 회사보다 좋은 경우는 별로 없을것이고 자기가 가고 싶은 회사가 코딩테스트를 보면 면접도 볼 수 없다. 회사에서 코딩테스트는 많은 입사자를 거르기 위한 거름망 용도로 생각하면 된다. [코딩테스트 공부 사이트, 책과 사이트 장단점] 코딩테스트 공부 할 수 있는 사이트는 많지만 대표적으로 3군데가 있다. 1. 백준(https://www.acmicpc.net/) 2. 프로그래머스(https://programmers.co.kr/) 3. 릿코드(https://leetcode.com/) 코드를 크게 입력, 구현부, 출력 으로 나눴을때 백준은 다 코딩 해야 되지만, 프로그래머..
https://programmers.co.kr/learn/courses/30/lessons/12929 위 문제가 DP문제인것은 눈치채기가 쉬운데 도저히 규칙히 찾아지지가 않았다. 찾아보니 대표적인 카탈란수 문제였다. 문제 풀이 카탈란수를 간략하게 설명하면 짝이 주어질때의 경우의 수를 나열한 수열이다. 위 괄호는 “(” 가 나올때 뒤에 무조건 “)” 가 나와야 하고 아래 산문제도 짝이 “/” 이 나오면 “\” 나와야하는 짝이 있어야하므로 대표적인 카탈란 수 문제이다. 그래서 대표적인 점화식이 존재한다. 원래 DP문제는 점화식을 찾아야하는 문제인데 카탈란 수 문제인걸 알면은 점화식을 바로 알수가 있다. 점화식은 아래와 같다. 이 점화식을 이용하여 문제를 풀면 된다. 코드 public int solution(..
자바로 알고리즘 문제를 풀 때 Scanner 클래스를 사용하면 편리하나 속도가 느리다는 단점이 있다. 그래서 Scanner 대신에 버퍼를 사용하는 BufferedReader 클래스를 사용하여 알고리즘 문제를 풀면 시간복잡도 효율성에서 유리하다. BufferedReader, StringTokenizer 클래스 사용예제 public class StringRepeat { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); /..
substring() 함수와 indexOf() 함수는 필수로 알아야 하는 함수이다. 함수의 개념을 알고 문제를 풀면서 활용해보자 [indexOf()함수와 substring() 함수개념] substring(beginIndex, endIndex) : beginIndex부터 endIndex 앞에 까지 문자열을 return 하고 substring(index) : index 부터 문자열을 return 한다. ex) "12341234".substring(0, 8) => 12341234 "12341234".substring(0) => 12341234 indexOf(String str) : 문자의 위치를 return하며, 없으면 -1을 return 한다. indexOf(String str, int fromIdx) : ..
ToCharArray() 함수는 String을 Char[]을 return 한다. 그래서 향상된 for문으로 한자리수씩 꺼낼 수 있다. 주로 String 값의 형식을 알아내는데 사용되고, 아래 문제에서는 ( )의 개수를 알아내는데 사용 되었다. [문제] 유효한 () 만 return, 만약에 "("가 뒤에 ")"가 없거나 " )" 가 먼저 나오는 경우는 제거 해야함. package public class ToCharArrayExaple { public static void main(String[] args) { //String s = "(a(b(c)d)"; // String s = "(((a(b(c(e(f)d))"; // String s = "in(f(lea)r)n)"; // String s = "a)b(c..
알고리즘 전략 1. 문제를 정확히 이해한다.(먼저 문제를 보고 시각화하여 어떻게 풀건지 말로 설명할 수 있어야 한다.) 2. 생각하고 프로그램화 한다. 즉 한국말로 생각하면서 이미지화 하고 Java로 코딩해야 한다. 3. 담을 그릇을 만든다 (Data Structure) 4. for(), while문을 만들고 그 안에 알고리즘을 담는다. 문제 : 숫자인 String 문자열 2개를 더한값 출력 Input: "123", "888" Output: "1011" package codingtest_java; // charAt(), subString(), StringBuilder클래스, append(), reverse().toString() // String인 숫자값을 숫자로 변환 int num = str.charA..
재귀함수 정의 컴퓨터가 수행하는 작업들은 대개 작은 조각들로 나누어 볼 수 있다. 그런데 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다. 완전히 같은 코드를 반복해 실행하는 for 같은 반복문이 좋은 예다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function)이다. 재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 조합과 순열 문제 간단한 반복문을 재귀함수로 변환하기 1. 조합 조합은 예를 들어 5개의 숫자를 4자리수 에 대한 숫자를 만들려고 할때 모든 경우를 구하는 것이다. 아래 문제를 보고 for문..