분류 전체보기
[백준] 1012 유기농 배추 - Java
[백준] 1012 유기농 배추 - Java
2022.05.27배추가 심어진 밭을 이차원 배열로 표현하고, 그 배열을 그래프로 표현해 풀 수 있는 문제이다. dfs와 bfs 모두 사용할 수 있다. 이번에는 재귀를 통한 dfs를 사용해 풀어보자. import java.util.*; import java.io.*; public class Main { static int N; static int M; static int K; static int[][] map; static boolean[][] visit; static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}}; static int cnt; public static void main(String[] args) throws IOException { BufferedReader br = n..
[백준] 3055 탈출 - Java
[백준] 3055 탈출 - Java
2022.05.27물이 전이되는 조건 때문에 처리해줘야 하는 요소가 많다. 일단 최단시간을 구하는게 목적이니, bfs를 돌리면서 최단 시간을 갱신하면 풀 수 있을 것 같다. 고슴도치는 물이 전이된 곳에 갈 수 없으니 물에 대한 bfs를 먼저 돌려 언제 물이 해당 위치에 전이되는지 기록하자. 그 후는 항상 하던대로 고슴도치에 대한 bfs를 수행하면 된다. import java.util.*; import java.io.*; public class Main { static int N; static int M; static char[][] map; static int[][] dist_water; static int[][] dist_hedgehog; static boolean[][] visit; static int[][] dir ..
[백준] 1697 숨바꼭질 - Java
[백준] 1697 숨바꼭질 - Java
2022.05.27최소 시간을 구하라고 했으니.. bfs를 사용해 dist를 갱신하고 최소 시간을 출력하면 될 것 같다. 기존 문제는 격자 혹은 그래프를 대놓고 줘서 그래프를 어떻게 구성해야 할 지 쉽게 떠올릴 수 있었는데, 이번 문제에서는 그래프에 대한 단서가 별로 없다. 먼저 그래프를 디자인해보자. 정점은 술래가 위치한 상태 / 간선은 +1. -1. *2 세 가지로 구성할 수 있겠다. 위의 조건에 맞춰 그래프를 구성하고 bfs를 돌려 답을 구하자. import java.util.*; import java.io.*; public class Main { static int N; static int K; static int[] dist; static boolean[] visit; public static void main(..
[백준] 7562 나이트의 이동 - Java
[백준] 7562 나이트의 이동 - Java
2022.05.27bfs로 격자를 순회하면서 거리를 갱신해 풀 수 있는 문제다. 관련 문제를 많이 풀어서 그래프 유형에 익숙해지자. import java.util.*; import java.io.*; public class Main { static int I; static int ans; static int[][] map; static boolean[][] visit; static int[][] dist; static int[][] dir = {{2,-1}, {2,1}, {1,-2}, {1,2}, {-2,-1}, {-2,1}, {-1,-2}, {-1,2}}; public static void main(String[] args) throws IOException { BufferedReader br = new Buffered..
[C] typedef / Union
[C] typedef / Union
2022.05.26typedef typedef int INT; 위와 같이 작성하면 INT라는 이름의 타입을 새로 생성한다. 자바에서 클래스의 이름을 타입처럼 사용하듯, 여기서도 비슷한 맥락으로 생각하면 된다. 지난번에 배운 구조체를 정의할 때는 struct struct_name variable_name 이렇게 길게 선언해야 했는데, typedef로 미리 구조체를 어떻게 사용할 지 명시해 두면 좀 더 간결하게 사용할 수 있다. 위와 같이 활용한다. 원래 이름은 아예 생략해서 사용할 수도 있다. Union C말고 다른 언어에서는 거의 사용하지 않는 타입이다. 위의 그림을 살펴보자. Union 타입으로 정의하면, 멤버변수들이 같은 위치에서 시작하게 된다. 즉, mem1에 10을 넣고 mem2에 20을 넣으면 mem1에 10을 ..
[C] 구조체
[C] 구조체
2022.05.26자바에 클래스가 있다면, C에는 구조체가 있다. (struct) 물론 모든 부분이 같지는 않고, C의 구조체의 마지막에는 세미콜론을 붙여야 하고, C의 구조체의 멤버로는 메서드가 포함될 수 없는 등 다른 부분이 있다. 구조체의 메모리 모양, 선언, 접근 방법은 자바에서 배운 내용과 비슷하다. 이 부분에서 잠깐 "배열의 이름은 포인터다"를 떠올릴 수 있는데, 구조체의 이름도 구조체의 첫 번째 멤버의 주소라고 생각할 수 있다. (구조체에서 메모리는 연속적으로 구성되어있다.) 구조체를 선언하면서 동시에 그 구조체 타입의 변수도 선언할 수 있음을 기억해 두자. 따로 따로 선언하는 것과 같은 효과를 낸다. 선언과 초기화를 동시에 진행할 수도 있다. 위의 두 가지를 한 번에 사용할 수도 있다. #include #i..
[백준] 14502 연구소 - Java
[백준] 14502 연구소 - Java
2022.05.261. 벽을 설치할 수 있는 위치 탐색 2. 벽을 설치하는 모든 경우를 고려해야 한다. dfs로 벽을 설치하고 설치가 완료됐으면 bfs로 바이러스의 수를 기록한다. import java.util.*; import java.util.concurrent.LinkedBlockingDeque; import java.io.*; public class Main { static int N; static int M; static int wall; static int ans; static int[][] map; static boolean[][] visit; static int[][] able_wall; static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; public sta..
[C] 동적 메모리
[C] 동적 메모리
2022.05.23메모리를 동적으로 할당받을 때 malloc외에도 realloc, xalloc, calloc 등 alloc의 가족들이 있다. 하나 하나 살펴보자. calloc calloc은 인자 전달 방식과 메모리를 0으로 초기화하는 부분 말고는 malloc과 동일하다. int *p = (int*)calloc(24, sizeof(int)); int *p = (int*)malloc(sizeof(int)* 24); 두 문장은 같은 역할을 한다. realloc int *p = (int*)malloc(3 * sizeof(int)); int *np = (int*)realloc(p, 5*sizeof(int)); realloc은 원래 사용하던 공간을 최대한 재활용하는 방향으로 메모리를 확보한다. 이전 포인터 p근처 공간이 넉넉하면 주..
[C] Stack / Heap
[C] Stack / Heap
2022.05.23스택 메모리에는 지역변수, 인자, 리턴 값 등이 있다고 배웠다. 스택 메모리에서는 변수의 선언 위치에 따라 생성/제거 시기가 정해지지만, 힙 메모리에서는 개발자 마음대로 쓰고 버릴 수 있다. 마치 전역변수처럼, 한 번 선언해두면 여러 함수에서 함께 사용할 수 있지만, 전역변수와는 달리 다 썼다 싶으면 제거할 수도 있다. 스택 / 힙 메모리 구조는 C뿐만 아니라 거의 모든 프로그래밍 언어에서 공통되는 요소이다. 자바를 예로 들면, A a = new A(); 코드를 실행하면, new 연산자가 힙 메모리에 공간을 확보한 후 동적 변수를 만든다. 그러고 나서, 동적 변수에 OID(Object Identifier)를 붙여주고 new연산자는 A의 생성자를 실행한 후 OID를 리턴한다. 오른쪽 그림에서 그래프 형태는..
[백준] 13904 과제 - Java
[백준] 13904 과제 - Java
2022.05.23그리디와 우선순위 큐 자료구조를 사용해 풀 수 있다. 우선순위 큐는 그냥 쓰면 되는데.. 그리디는 어떻게 사용해야 할까? 일단 객체 하나 만들고 점수 내림차순으로 정렬하자. 그 후 계산을 시작한다. 하루에 과제 하나를 끝낼 수 있으니, 기간이 많이 남은 과제는 최대한 나중에 하면 된다. 점수에 대해 정렬이 된 상태라서, 이렇게 작성하면 고득점을 얻을 수 있다. import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int..
[백준] 16987 계란으로 계란치기 - Java
[백준] 16987 계란으로 계란치기 - Java
2022.05.23백트래킹으로 모든 경우를 계산해 풀 수 있는 문제이다. (브루트포스 느낌) 재귀는 반복문으로 구현할 수 있고 반복문은 재귀로 구현할 수 있듯, 이 문제도 반복문을 사용해 풀 수 있을 것 같긴 하다. 재귀적 구조에 익숙해져야겠다. 아직은 너무 어색하다. import java.util.*; import java.io.*; public class Main { static int N = 0; static int cnt = 0; static Egg[] egg; static int max = 0; public static void main(String args[]) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
[백준] 1759 암호 만들기 - Java
[백준] 1759 암호 만들기 - Java
2022.05.23백트래킹으로 풀 수 있는 문제이다. 조건은, 모음이 1개 이상 / 자음이 2개 이상이다. 암호의 문자는 하나씩밖에 사용할 수 없으니 백트래킹 함수는 인자를 두 개 받도록 설정해 처리해주자. 값의 후보가 되는 요소들은 리스트로 담아서 풀 수 있는데, 이번에는 배열을 사용해서 풀어보자. arr의 값이 cand의 인덱스로 접근해서 답을 출력한다. import java.util.*; import java.io.*; public class Main { static int L, C = 0; static int[] arr; static char[] cand; public static void main(String args[]) throws IOException { BufferedReader br = new Buffe..