BOJ
-
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 -
BOJ 17135번 캐슬 디펜스 문제 자바(java) 풀이 랭크 : 골드4 삼성 SW 역량 테스트 A형 기출문제 백준 17135번 캐슬 디펜스 문제정리 게임 맵은 NxM 크기이다. 1x1 크기의 칸으로 이루어져 있다. 각 칸에 포함된 적의 수는 최대 하나이다. 격자판 N+1번 행의 모든 칸에는 성이 있다. 궁수 3명을 배치하려고 함 4.1 궁수는 성이 있는 칸에 배치 가능. 하나의 칸에는 최대 1명의 궁수만 있을 수 있음 4.2 턴 마다 궁수는 적 하나 공격 가능. 모든 궁수는 동시에 공격 4.3 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적. 그러한 적이 여럿이면 가장 왼쪽에 있는 적 공격 4.4 공격받은 적은 게임에서 제외 궁수의 공격이 끝나면 적이 이동한다. 적은 아래로 한칸 이동..
[BOJ] 삼성 sw 역량 테스트 A형 기출 :: 백준 17135번 캐슬 디펜스 (조합, 시뮬레이션)BOJ 17135번 캐슬 디펜스 문제 자바(java) 풀이 랭크 : 골드4 삼성 SW 역량 테스트 A형 기출문제 백준 17135번 캐슬 디펜스 문제정리 게임 맵은 NxM 크기이다. 1x1 크기의 칸으로 이루어져 있다. 각 칸에 포함된 적의 수는 최대 하나이다. 격자판 N+1번 행의 모든 칸에는 성이 있다. 궁수 3명을 배치하려고 함 4.1 궁수는 성이 있는 칸에 배치 가능. 하나의 칸에는 최대 1명의 궁수만 있을 수 있음 4.2 턴 마다 궁수는 적 하나 공격 가능. 모든 궁수는 동시에 공격 4.3 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적. 그러한 적이 여럿이면 가장 왼쪽에 있는 적 공격 4.4 공격받은 적은 게임에서 제외 궁수의 공격이 끝나면 적이 이동한다. 적은 아래로 한칸 이동..
2020.03.10 -
BOJ 3190번 뱀(snake) 문제 자바(java) 풀이 랭크 : 실버 1 백준 온라인 저지(BOJ) 3190번 뱀(snake) 문제 자바 풀이 백준3190번 뱀 코드 저는 푸는데 1시간 좀 넘게 걸렸어요 아래의 깃허브를 참고해주세요!! 백준3190번 뱀 문제이해 시작시 뱀은 맨위 맨 좌측에 위치. 처음에 오른쪽으로 향하며 초기 뱀의 길이는 1이다. 몸길이를 늘려 머리를 먼저 다음 칸에 가져다 댄다. if 사과 exists: 사과 없어지고 꼬리는 움직이지 않음 ( 몸 길이 늘어남 ) if !사과 exsists: 몸 길이를 줄여 꼬리가 위치한 칸을 비워줌 ( 몸 길이 그대로 ) 게임이 끝나는 시간 계산하기 ( 벽 또는 자기자신의 몸과 부딪히면 게임 끝) 벽은 상하좌우 끝에 있다. 문제 풀이 뱀 초기 위..
[백준 알고리즘(BOJ)] 3190번 뱀 자바(java) 풀이BOJ 3190번 뱀(snake) 문제 자바(java) 풀이 랭크 : 실버 1 백준 온라인 저지(BOJ) 3190번 뱀(snake) 문제 자바 풀이 백준3190번 뱀 코드 저는 푸는데 1시간 좀 넘게 걸렸어요 아래의 깃허브를 참고해주세요!! 백준3190번 뱀 문제이해 시작시 뱀은 맨위 맨 좌측에 위치. 처음에 오른쪽으로 향하며 초기 뱀의 길이는 1이다. 몸길이를 늘려 머리를 먼저 다음 칸에 가져다 댄다. if 사과 exists: 사과 없어지고 꼬리는 움직이지 않음 ( 몸 길이 늘어남 ) if !사과 exsists: 몸 길이를 줄여 꼬리가 위치한 칸을 비워줌 ( 몸 길이 그대로 ) 게임이 끝나는 시간 계산하기 ( 벽 또는 자기자신의 몸과 부딪히면 게임 끝) 벽은 상하좌우 끝에 있다. 문제 풀이 뱀 초기 위..
2020.02.09