목록Algorithm/백준 BOJ (44)
다희의 코딩 성장일기
[백준] 2493. 탑 (자바 JAVA)
[ 문제 ] [백준] 2493. 탑 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net # 접근 방법 및 풀이 단순히 for문 두개로 탐색 돌렸는데 역시나 시간초과 ㅎㅎ.. 왜 N범위를 제대로 안 읽고 푸는지.. 다시한번 느꼈다. 두번째는 스택으로 풀었다. 왼쪽에서 오른쪽으로 탐색할지, 오른쪽에서 왼쪽으로 탐색할지 고민해서 시간이 조금 걸렸다. ans[]배열을 N 크기만큼 생성해 각각의 idx에 해당하는 답을 담기..
[백준] 2583. 영역 구하기 (자바 JAVA)
[ 문제 ] [백준] 2583. 영역 구하기 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 접근 방법 및 풀이 보통 0,0와 M,N은 맨 왼쪽 위부터 맨 오른쪽 아래로 생각하기 쉬운데 여기선 다르다. 0,0이 맨 왼쪽 아래고 M,N이 맨 오른쪽 위다. 그리고 숫자로 들어오는 값이 x, y를 좌표선상으로 생각해서 받아야한다. x는 가로축 y는 세로축이기 때문에 x는 열좌표 y는 행좌표이다...
[백준] 1726. 로봇 (자바 JAVA)
[ 문제 ] [백준] 1726. 로봇 (자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net # 접근 방법 및 풀이 출발지점에서 도착지점까지 최단거리로 움직이는 것이기 때문에 BFS로 풀었다. 초기 궤도는 map[][]으로 입력받고, 출발지점과 끝지점 입력을 받는다. 이때 입력에서 주어진 방향이 동쪽이 1, 서쪽이 2, 남쪽이 3, 북쪽이 4로 주어지는데, 이게 불편해서 내가 편한대로 방향을 다음과 같이 바꿔주었다. 따라서 입력으..
[백준] 4889. 안정적인 문자열(자바 JAVA)
[ 문제 ] [백준] 4889. 안정적인 문자열(자바 JAVA) 문제 링크 : https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 입력은 여러 개의 데이터 세트로 이루어져 있다. 각 데이터 세트는 한 줄로 이루어져 있다. 줄에는 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 문자열의 길이가 2000을 넘는 경우 www.acmicpc.net # 접근 방법 및 풀이 스택을 이용해서 풀었다. 문제에서 연산은 2가지. "여는 괄호 -> 닫는괄호" or "닫는괄호 -> 여는괄호" '{' 여는 괄호라면 스택에 넣어주고, 닫는 괄호라면 스택에 들어있는 여는괄호를 뽑는다. 근데 이때 여는 괄호가 들어있지 않다면, 닫는 괄호를 여는 괄호로 만들어서 스택에 넣어준다. ..
[백준] 17141. 연구소2 (자바 JAVA)
[ 문제 ] [백준] 17141. 연구소2 문제 링크 : https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net # 접근 방법 및 풀이 구현 + bfs로 풀었다. 1. 0인 빈칸 갯수 세기 -> bfs 돌려서 빈칸에 퍼질때마다 카운트를 -1 할거다. 2. 바이러스를 놓을 수 있는 곳이 최대 10개 이므로, 조합으로 바이러스 놓을 곳 M개 뽑기 3. BFS로 바이러스 퍼트리기 큐에 선택한 바이러스 좌표를 다 넣고 bfs 돌려서 큐에서 마지막으로 나온 바이러스가 ..
[백준] 14719. 빗물 (자바 JAVA)
[ 문제 ] BOJ 14719. 빗물 문제 링크 : https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net # 접근 방법 및 풀이 그냥 구현! 이문제 보니 스택으로 많이 풀었던데, 난 그냥 문제대로 구현했다. 이 문제를 보고 스택을 바로 안 떠올렸는데 이런거 보면 자료구조 형태의 문제 유형에 부족하다는 것을 느꼈다. 무튼 나는 첫번째 만나는 블록, 그리고 빈칸에 대한 flag를 두어서 구현했다. 입력에서 모든 블록은 map에서 1로 ..