백준
-
BOJ 10828번 스택 자바(java) 풀이 랭크 : 실버4 메모리: 17728KB 시간: 252ms 백준 10828번 스택 문제 정리 스택을 구현하고 다음 명령들을 처리해라. push X: 정수 X를 스택에 넣는다. pop: 스택에서 가장 위에 있는 정수를 빼고, 출력 한다. 스택이 비었다면 -1 출력 size: 스택의 크기를 출력한다. empty: 스택이 비었다면 1 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 비어있다면 -1 출력 push 명령을 제외하고 모두 값을 출력해야 합니다. 문제 풀이 이 문제는 큐문제와 유사합니다. 이도 풀어보시는걸 추천드립니다!! java에 구현되어 있는 Stack을 이용하여 문제를 풉니다. Stack의 메소드 몇 개만 알면 풀 수 있..
[BOJ] 백준 10828 스택 자바(java) 풀이 (자바 스택 메소드)BOJ 10828번 스택 자바(java) 풀이 랭크 : 실버4 메모리: 17728KB 시간: 252ms 백준 10828번 스택 문제 정리 스택을 구현하고 다음 명령들을 처리해라. push X: 정수 X를 스택에 넣는다. pop: 스택에서 가장 위에 있는 정수를 빼고, 출력 한다. 스택이 비었다면 -1 출력 size: 스택의 크기를 출력한다. empty: 스택이 비었다면 1 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 비어있다면 -1 출력 push 명령을 제외하고 모두 값을 출력해야 합니다. 문제 풀이 이 문제는 큐문제와 유사합니다. 이도 풀어보시는걸 추천드립니다!! java에 구현되어 있는 Stack을 이용하여 문제를 풉니다. Stack의 메소드 몇 개만 알면 풀 수 있..
2020.03.15 -
BOJ 1018번 체스판 다시 칠하기 문제 자바(java) 풀이 랭크 : 골드3 백준 1018번 체스판 다시 칠하기 문제 정리 MxN 크기의 보드가 있다. 흰색과 검은색의 정사각형으로 이루어져 있다. 8x8 체스판을 만드려고 한다. 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 한다. -> 체스판을 색칠하는 경우는 2가지 MxN 크기의 보드에서 8x8 크기의 체스판으로 잘라서 색을 다시 칠하려 한다. 다시 칠해야 하는 정사각형의 최소 개수를 구하여라 문제 접근 완전 탐색만 할 줄 안다면 풀 수 있는 문제입니다. 간단하게 생각해야 합니다. 4중 for문으로 답을 구해낼 수 있습니다. 8x8로 자를 수 있는 가능한 경우 모두 잘라본다 자를 때 마다 체스판과 다른 문자 갯수를 찾아서 저장하고 최소 값과..
[BOJ] 백준 1018번 체스판 다시 칠하기 자바(java) 풀이 (완전탐색)BOJ 1018번 체스판 다시 칠하기 문제 자바(java) 풀이 랭크 : 골드3 백준 1018번 체스판 다시 칠하기 문제 정리 MxN 크기의 보드가 있다. 흰색과 검은색의 정사각형으로 이루어져 있다. 8x8 체스판을 만드려고 한다. 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져야 한다. -> 체스판을 색칠하는 경우는 2가지 MxN 크기의 보드에서 8x8 크기의 체스판으로 잘라서 색을 다시 칠하려 한다. 다시 칠해야 하는 정사각형의 최소 개수를 구하여라 문제 접근 완전 탐색만 할 줄 안다면 풀 수 있는 문제입니다. 간단하게 생각해야 합니다. 4중 for문으로 답을 구해낼 수 있습니다. 8x8로 자를 수 있는 가능한 경우 모두 잘라본다 자를 때 마다 체스판과 다른 문자 갯수를 찾아서 저장하고 최소 값과..
2020.03.15 -
BOJ 1517번 버블소트 문제 자바(java) 풀이 랭크 : 골드3 백준 1517번 버블소트 문제 정리 N개의 수로 이루어진 수열이 있다. 이 수열에 대해 버블 소트를 수행할때 swap이 몇 번 일어나는지 계산하여라. N은 최대 500,000 각각의 수는 최대 10억 문제 접근 N이 최대 500,000이므로 단순한 버블 정렬대로 하면서 계산하면 N2으로 시간초과가 날 것입니다. 최소 nlogn 정도의 알고리즘을 구현해야 합니다. O(n)이라 생각한 알고리즘 1.1 list에 모든 값을 다 넣고 최대값을 구해 최대값의 위치를 구합니다. 1.2 그 값의 위치를 찾고 list의 맨 뒤 인덱스에서 값으 위치를 빼줍니다.(예를 들어 최대값의 위치 1, 맨 뒤 인덱스 5 -> 5-1=4) 이 값이 뒤로 보내기 위..
[BOJ] 백준 1517번 버블 소트 자바 ( 병합 정렬(merge sort) 이용하기 )BOJ 1517번 버블소트 문제 자바(java) 풀이 랭크 : 골드3 백준 1517번 버블소트 문제 정리 N개의 수로 이루어진 수열이 있다. 이 수열에 대해 버블 소트를 수행할때 swap이 몇 번 일어나는지 계산하여라. N은 최대 500,000 각각의 수는 최대 10억 문제 접근 N이 최대 500,000이므로 단순한 버블 정렬대로 하면서 계산하면 N2으로 시간초과가 날 것입니다. 최소 nlogn 정도의 알고리즘을 구현해야 합니다. O(n)이라 생각한 알고리즘 1.1 list에 모든 값을 다 넣고 최대값을 구해 최대값의 위치를 구합니다. 1.2 그 값의 위치를 찾고 list의 맨 뒤 인덱스에서 값으 위치를 빼줍니다.(예를 들어 최대값의 위치 1, 맨 뒤 인덱스 5 -> 5-1=4) 이 값이 뒤로 보내기 위..
2020.03.14 -
BOJ 1085번 직사각형에서 탈출 자바(java) 풀이 랭크 : 브론즈2 백준 1085번 직사각형에서 탈출 문제정리 지금 현재 위치는 (x,y) 이고 직사각형의 왼쪽 아래 위치는 (0,0)이다. 오른쪽 위 꼭지점은 (w,h)에 있다. 직사각형 경계선까지 가는 거리의 최소값을 구하는 프로그램을 작성해라. 문제풀이 경계선이란 직사각형의 선 위를 이야기합니다. 예시를 보면 가로 10 세로 3의 크기인 직사각형이 있습니다. 한수는 (6,2)에 있으므로 위쪽 (6,3)으로 가면 직사각형 위에 있게됩니다. 즉 1만 이동하면 선 위에 있을 수 있습니다. 그림을 한 번만 그려보면 쉽게 알 수 있습니다. 높이(위, 아래 직사각형 선)와 너비선(양 옆 직사각형 선)을 따로 따져줍니다. 높이 2.1 현 위치의 y좌표가 높..
[BOJ] 백준 1085번 직사각형에서의 탈출 자바(java)BOJ 1085번 직사각형에서 탈출 자바(java) 풀이 랭크 : 브론즈2 백준 1085번 직사각형에서 탈출 문제정리 지금 현재 위치는 (x,y) 이고 직사각형의 왼쪽 아래 위치는 (0,0)이다. 오른쪽 위 꼭지점은 (w,h)에 있다. 직사각형 경계선까지 가는 거리의 최소값을 구하는 프로그램을 작성해라. 문제풀이 경계선이란 직사각형의 선 위를 이야기합니다. 예시를 보면 가로 10 세로 3의 크기인 직사각형이 있습니다. 한수는 (6,2)에 있으므로 위쪽 (6,3)으로 가면 직사각형 위에 있게됩니다. 즉 1만 이동하면 선 위에 있을 수 있습니다. 그림을 한 번만 그려보면 쉽게 알 수 있습니다. 높이(위, 아래 직사각형 선)와 너비선(양 옆 직사각형 선)을 따로 따져줍니다. 높이 2.1 현 위치의 y좌표가 높..
2020.03.13 -
BOJ 2583번 영역 구하기 문제 자바(java) 풀이 난이도: 실버1 풀이시간: 30분 백준 2583번 영역 구하기 문제정리 MxN 크기의 모눈종이가 주어진다. 모눈 종이 위에 K개의 직사각형을 그린다. k개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 몇개의 영역으로 분리되는지, 각 영역의 넓이는 어떤지 구하여라 문제풀이 분리된 영역과 넓이를 구하는 것이므로 모든 좌표에서 bfs 탐색을 하면 됩니다. 이 문제는 영역을 구분짓는 문제인 보물섬, 치즈, 빙산과 유사합니다. 문제에서 주어지는 직사각형의 좌표들과 배열의 인덱스가 다르기 때문에 주어진 x,y좌표를 반대로 바꿔줍니다. ( 바꾸면 답이 잘 나오는지 직접 그려보느라 시간 좀더 걸림 ) 직사각형이 있는 곳은 map..
[BOJ] 백준 2583번 영역 구하기 자바(java) 풀이 (dfs, bfs)BOJ 2583번 영역 구하기 문제 자바(java) 풀이 난이도: 실버1 풀이시간: 30분 백준 2583번 영역 구하기 문제정리 MxN 크기의 모눈종이가 주어진다. 모눈 종이 위에 K개의 직사각형을 그린다. k개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 몇개의 영역으로 분리되는지, 각 영역의 넓이는 어떤지 구하여라 문제풀이 분리된 영역과 넓이를 구하는 것이므로 모든 좌표에서 bfs 탐색을 하면 됩니다. 이 문제는 영역을 구분짓는 문제인 보물섬, 치즈, 빙산과 유사합니다. 문제에서 주어지는 직사각형의 좌표들과 배열의 인덱스가 다르기 때문에 주어진 x,y좌표를 반대로 바꿔줍니다. ( 바꾸면 답이 잘 나오는지 직접 그려보느라 시간 좀더 걸림 ) 직사각형이 있는 곳은 map..
2020.03.12 -
BOJ 7576번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7576번 토마토 문제정리 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토가 익게된다. 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 를 의미한다. 대각선 토마토에는 영향을 줄 수 없다. 모든 토마토가 익는데 필요한 최소 일 수를 구해라 토마토가 없는 칸이 있을 수 있다. 처음부터 토마토 모두가 익어있다면 0, 모두 익을 수 없다면 -1 출력 토마토 상태 1 : 익은 토마토 0 : 익지 않은 토마토 1 : 토마토 없음 문제 풀이 최소 시간을 구해야 하므로 모든 방향으로 퍼져가며 토마토를 익게 해나가며 구해야한다. 즉 bfs를 이용하여 탐색합니다. 익은 토마토가 여러개인 경우도 있기 때문에 익은 토마토를 모두 list에 담고 b..
[BOJ] 백준 7576번 토마토 자바(java) 풀이 (bfs)BOJ 7576번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7576번 토마토 문제정리 보관 후 하루가 지나면 익은 토마토에 인접한 익지 않은 토마토가 익게된다. 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 를 의미한다. 대각선 토마토에는 영향을 줄 수 없다. 모든 토마토가 익는데 필요한 최소 일 수를 구해라 토마토가 없는 칸이 있을 수 있다. 처음부터 토마토 모두가 익어있다면 0, 모두 익을 수 없다면 -1 출력 토마토 상태 1 : 익은 토마토 0 : 익지 않은 토마토 1 : 토마토 없음 문제 풀이 최소 시간을 구해야 하므로 모든 방향으로 퍼져가며 토마토를 익게 해나가며 구해야한다. 즉 bfs를 이용하여 탐색합니다. 익은 토마토가 여러개인 경우도 있기 때문에 익은 토마토를 모두 list에 담고 b..
2020.03.11