알고리즘 문제풀이
-
BOJ 1012번 유기농 배추 문제 자바(java) 풀이 난이도: 실버2 풀이시간: 20분 백준 1012번 유기농 배추 설치 문제 정리 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 배추가 상하좌우로 붙어있으면 인접해있다고 본다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 서로 퍼지므로 총 몇 마리의 지렁이가 필요한지 알 수 있다. 다음과 같이 입력이 주어진다 TC 개수 가로 세로 배추개수 맵 각 TC에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다. 문제 접근 이 문제는 bfs를 이용하여 영역의 개수를 구하는 것과 같은 문제입니다. bfs를 통해 1로 이어져 있는 영역은(배추가 이..
[bfs] 백준 1012번 유기농 배추 자바 풀이BOJ 1012번 유기농 배추 문제 자바(java) 풀이 난이도: 실버2 풀이시간: 20분 백준 1012번 유기농 배추 설치 문제 정리 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 배추가 상하좌우로 붙어있으면 인접해있다고 본다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 서로 퍼지므로 총 몇 마리의 지렁이가 필요한지 알 수 있다. 다음과 같이 입력이 주어진다 TC 개수 가로 세로 배추개수 맵 각 TC에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다. 문제 접근 이 문제는 bfs를 이용하여 영역의 개수를 구하는 것과 같은 문제입니다. bfs를 통해 1로 이어져 있는 영역은(배추가 이..
2020.06.14 -
BOJ 1637번 날카로운 눈 자바(java) 풀이 랭크 : 골드1 백준 1637번 날카로운 눈 문제 정리 정수가 여러 개 모여 있는 정수더미가 있다. 그 안에는 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 짝수개 존재한다. 이 중에서 홀수개가 존재하는 정수를 찾아야한다. N은 1이상 20,000이하 그리고 N개의 줄에 걸쳐 세개의 숫자(A, C, B)가 주어진다. A, A+B, A+2B, A+3B...의 정수들이 정수더미 안에 있다. A+kB는 C보다 작거나 같다. 1
[이분탐색] 백준 1637번 날카로운 눈 자바 풀이BOJ 1637번 날카로운 눈 자바(java) 풀이 랭크 : 골드1 백준 1637번 날카로운 눈 문제 정리 정수가 여러 개 모여 있는 정수더미가 있다. 그 안에는 어떤 특정한 정수 하나만 홀수개 존재하고 나머지 정수는 짝수개 존재한다. 이 중에서 홀수개가 존재하는 정수를 찾아야한다. N은 1이상 20,000이하 그리고 N개의 줄에 걸쳐 세개의 숫자(A, C, B)가 주어진다. A, A+B, A+2B, A+3B...의 정수들이 정수더미 안에 있다. A+kB는 C보다 작거나 같다. 1
2020.06.13 -
BOJ 1107 리모콘 자바(java) 풀이 랭크 : 골드5 백준 1107 리모컨 문제 정리 리모컨의 일부 숫자 버튼이 고장났다. 리모컨에는 0~9까지의 숫자 버튼과ㅏ +, - 버튼이 있다 '+' 버튼은 +1된 채널, '-' 버튼은 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이고, 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해 최소 몇번 버튼을 눌러야 하는지 구하시오 이동하려는 채널 최대 500,000 수빈이가 지금 보고 있는 채널은 100번 문제 접근 이 문제는 다음과 같은 사항을 고려하여야 합니다 고장난 버튼 수가 없는 경우 -> 입력 받지 않음 원하는 번호가 100번인 경우 -> 0 출력하고..
[완전탐색, 백트래킹] 백준 1107번 리모컨 자바 풀이BOJ 1107 리모콘 자바(java) 풀이 랭크 : 골드5 백준 1107 리모컨 문제 정리 리모컨의 일부 숫자 버튼이 고장났다. 리모컨에는 0~9까지의 숫자 버튼과ㅏ +, - 버튼이 있다 '+' 버튼은 +1된 채널, '-' 버튼은 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이고, 고장난 버튼이 주어질 때, 채널 N으로 이동하기 위해 최소 몇번 버튼을 눌러야 하는지 구하시오 이동하려는 채널 최대 500,000 수빈이가 지금 보고 있는 채널은 100번 문제 접근 이 문제는 다음과 같은 사항을 고려하여야 합니다 고장난 버튼 수가 없는 경우 -> 입력 받지 않음 원하는 번호가 100번인 경우 -> 0 출력하고..
2020.06.10 -
프로그래머스 가장 큰 정사각형 찾기 자바(java) 풀이 Level 2 연습문제 가장 큰 정사각형 찾기 문제 정리 1과 0으로 채워진 표가 있다. 표 1칸은 1x1의 정사각형으로 이루어져 있다. 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하여라 naive한 문제 풀이 처음에는 정말 naive하게 5중 for문을 이용해서 풀어보았습니다. 정확성은 모두 맞추었지만 역시나 효율성 테스트는 통과하지 못했습니다. 최대 크기의 board에서 우측하단 하나만 0인 경우 이런 경우 터질 것 같습니다. naive한 코드는 아래와 같습니다. public static int solution(int [][]board) { int x_len = board.length; int y_len = board[0].le..
[DP] 프로그래머스 level2 가장 큰 정사각형 찾기 자바 풀이프로그래머스 가장 큰 정사각형 찾기 자바(java) 풀이 Level 2 연습문제 가장 큰 정사각형 찾기 문제 정리 1과 0으로 채워진 표가 있다. 표 1칸은 1x1의 정사각형으로 이루어져 있다. 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하여라 naive한 문제 풀이 처음에는 정말 naive하게 5중 for문을 이용해서 풀어보았습니다. 정확성은 모두 맞추었지만 역시나 효율성 테스트는 통과하지 못했습니다. 최대 크기의 board에서 우측하단 하나만 0인 경우 이런 경우 터질 것 같습니다. naive한 코드는 아래와 같습니다. public static int solution(int [][]board) { int x_len = board.length; int y_len = board[0].le..
2020.06.02 -
BOJ 7622번 이중 우선순위 큐 문제 자바(java) 풀이 랭크 : 골드5 백준 7622번 이중 우선순위 큐 문제 정리 큐에 저장된 값 자체가 큐의 우선순위를 나타낸다. 큐에 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최대, 최소값을 출력하는 프로그램을 작성하세요 I n : n을 Q에 삽입 D 1 : Q에서 최댓값 삭제 D -1 : Q에서 최솟값 삭제 최대, 최소 둘 이상인 경우, 하나만 삭제됨을 유념 Q가 비어있는데 적용할 연산이 'D'라면 이 연산은 무시한다. 동일한 정수가 삽입될 수 있다. 큐가 비어있다면 EMPTY를 출력하라. 그렇지 않으면 {최댓값, 최솟값} 출력 문제접근, TreeMap 처음엔 문제이름 그대로 우선순위 큐 두개를 이용해서 풀었지만 시간초과가 나서 다른 ..
[TreeMap, 우선순위 큐] 백준 7622번 이중 우선순위 큐 자바 풀이BOJ 7622번 이중 우선순위 큐 문제 자바(java) 풀이 랭크 : 골드5 백준 7622번 이중 우선순위 큐 문제 정리 큐에 저장된 값 자체가 큐의 우선순위를 나타낸다. 큐에 연산을 처리하고 최종적으로 큐에 저장된 데이터 중 최대, 최소값을 출력하는 프로그램을 작성하세요 I n : n을 Q에 삽입 D 1 : Q에서 최댓값 삭제 D -1 : Q에서 최솟값 삭제 최대, 최소 둘 이상인 경우, 하나만 삭제됨을 유념 Q가 비어있는데 적용할 연산이 'D'라면 이 연산은 무시한다. 동일한 정수가 삽입될 수 있다. 큐가 비어있다면 EMPTY를 출력하라. 그렇지 않으면 {최댓값, 최솟값} 출력 문제접근, TreeMap 처음엔 문제이름 그대로 우선순위 큐 두개를 이용해서 풀었지만 시간초과가 나서 다른 ..
2020.05.29 -
프로그래머스 이중우선순위 큐 자바 풀이 Level 3 해시(Hash) 이중우선순위큐 문제 정리 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조 이다. 1.1 I 숫자 : 큐에 주어진 숫자를 삽입한다 1.2 D 1 : 큐에서 최댓값을 삭제한다. 1.3 D -1 : 큐에서 최솟값을 삭제한다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최대값, 최솟값]을 반환하여라. 최대/최소를 삭제하는 연산에서 최대/최소값이 둘 이상인 경우, 하나만 삭제한다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다. 문제 접근 우선순위 큐는 deque 처럼 뒤에서 뺄 수 없습니다. 그래서 오름차순, 내림차순 우선순위 큐를 따로 두어 최대, 최소를 구해야겠다고 생각했습니다. 오..
[우선순위 큐] 프로그래머스 level3 이중우선순위큐 자바 풀이프로그래머스 이중우선순위 큐 자바 풀이 Level 3 해시(Hash) 이중우선순위큐 문제 정리 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조 이다. 1.1 I 숫자 : 큐에 주어진 숫자를 삽입한다 1.2 D 1 : 큐에서 최댓값을 삭제한다. 1.3 D -1 : 큐에서 최솟값을 삭제한다. 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최대값, 최솟값]을 반환하여라. 최대/최소를 삭제하는 연산에서 최대/최소값이 둘 이상인 경우, 하나만 삭제한다. 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다. 문제 접근 우선순위 큐는 deque 처럼 뒤에서 뺄 수 없습니다. 그래서 오름차순, 내림차순 우선순위 큐를 따로 두어 최대, 최소를 구해야겠다고 생각했습니다. 오..
2020.05.28