알고리즘 문제풀이
-
BOJ 9095번 1,2,3 더하기 c++ 및 java 풀이 난이도: 실버3 백준 9095 1,2,3 더하기 문제 정리 어떤 수 N이 주어질때 1,2,3의 합으로 N을 나타낼 수 있는 방법의 개수를 구하여라. 1+2+1 과 2+1+1은 다른 방법이다 N은 양수이며 11보다 작다. 문제 접근 재귀를 이용해서 풀면 되겠다고 생각하였습니다. 1,2,3으로 모두 빼면서 0이 될때까지 재귀를 이용해 빼보는 것입니다. 예를들어 4-1 = 3 3-1 = 2 2-1 = 1 1-1 = 0 (1,1,1,1) 4-2 = 2 2-1 = 1 1-1 = 0 (2,1,1) 와 같이 됩니다 문제 풀이 테스트 케이스 수를 입력받습니다. N을 입력받고 N에서 1뺀 수, 2를 뺀 수, 3을 뺀 수를 재귀함수에 넣어서 0으로 만듭니다. 0..
[재귀, DP] 백준 9095 1,2,3 더하기 c++, java 풀이BOJ 9095번 1,2,3 더하기 c++ 및 java 풀이 난이도: 실버3 백준 9095 1,2,3 더하기 문제 정리 어떤 수 N이 주어질때 1,2,3의 합으로 N을 나타낼 수 있는 방법의 개수를 구하여라. 1+2+1 과 2+1+1은 다른 방법이다 N은 양수이며 11보다 작다. 문제 접근 재귀를 이용해서 풀면 되겠다고 생각하였습니다. 1,2,3으로 모두 빼면서 0이 될때까지 재귀를 이용해 빼보는 것입니다. 예를들어 4-1 = 3 3-1 = 2 2-1 = 1 1-1 = 0 (1,1,1,1) 4-2 = 2 2-1 = 1 1-1 = 0 (2,1,1) 와 같이 됩니다 문제 풀이 테스트 케이스 수를 입력받습니다. N을 입력받고 N에서 1뺀 수, 2를 뺀 수, 3을 뺀 수를 재귀함수에 넣어서 0으로 만듭니다. 0..
2020.06.26 -
BOJ 18870번 좌표 압축 c++ 풀이 난이도: 실버2 백준 18870번 좌표 압축 문제 정리 수직선 위의 값이 주어질때 이를 좌표압축해여 표현하여라 주어지는 수의 개수는 1
[좌표압축] 백준 18870번 좌표압축 c++, java 풀이BOJ 18870번 좌표 압축 c++ 풀이 난이도: 실버2 백준 18870번 좌표 압축 문제 정리 수직선 위의 값이 주어질때 이를 좌표압축해여 표현하여라 주어지는 수의 개수는 1
2020.06.25 -
BOJ 2630번 색종이 만들기 문제 자바(java) 풀이 난이도: 실버3 백준 2630번 색종이 만들기 문제 정리 여러개의 정사각형칸들로 이루어진 종이가 있으며 파란색 또는 하얀색으로 칠해져있다. 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 종이를 만드려고 한다. 종이가 모두 같은 색으로 칠해져있지 않으면 가로와 세로로 중간 부분을 잘라나간다. 이를 모두 똑같은 색깔의 종이만 남거나 하나 밖에 남지 않을때까지 반복한다. 종이의 크기는 NxN이며 (2,4,8,16,32,64,128) 크기중 하나이다. 하얀색:0, 파란색: 1 최종적으로 하얀색 색종이의 개수와 파란색 색종이의 개수를 출력한다. 문제 접근 어떤 조건을 두고 조건이 만족하지 않으면 계속 반복되는 구..
[재귀] 백준 2630번 색종이 만들기 자바 풀이BOJ 2630번 색종이 만들기 문제 자바(java) 풀이 난이도: 실버3 백준 2630번 색종이 만들기 문제 정리 여러개의 정사각형칸들로 이루어진 종이가 있으며 파란색 또는 하얀색으로 칠해져있다. 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 종이를 만드려고 한다. 종이가 모두 같은 색으로 칠해져있지 않으면 가로와 세로로 중간 부분을 잘라나간다. 이를 모두 똑같은 색깔의 종이만 남거나 하나 밖에 남지 않을때까지 반복한다. 종이의 크기는 NxN이며 (2,4,8,16,32,64,128) 크기중 하나이다. 하얀색:0, 파란색: 1 최종적으로 하얀색 색종이의 개수와 파란색 색종이의 개수를 출력한다. 문제 접근 어떤 조건을 두고 조건이 만족하지 않으면 계속 반복되는 구..
2020.06.24 -
BOJ 1463번 1로 만들기 자바(java) 풀이 난이도: 실버3 백준 1463번 1로 만들기 문제 정리 정수 X가 3으로 나누어 떨어지면, 3으로 나눈다 정수 X가 2로 나누어 떨어지면, 2로 나눈다 1을 뺀다 위의 3가지 연산을 이용해 주어진 정수 N을 1로 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라 1
[dfs, dp] 백준 1463번 1로 만들기 자바 풀이BOJ 1463번 1로 만들기 자바(java) 풀이 난이도: 실버3 백준 1463번 1로 만들기 문제 정리 정수 X가 3으로 나누어 떨어지면, 3으로 나눈다 정수 X가 2로 나누어 떨어지면, 2로 나눈다 1을 뺀다 위의 3가지 연산을 이용해 주어진 정수 N을 1로 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라 1
2020.06.18 -
BOJ 달이 차오른다, 가자 문제 자바(java) 풀이 난이도: 골드1 백준 1194번 달이 차오른다, 가자 문제 정리 미로를 탈출하려 한다. 미로는 다음과 같이 구성되어 있다. 빈 곳: 언제나 이동 가능(.) 벽: 절대 이동 불가(#) 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 잡는다(a - f) 문: 대응하는 열쇠가 있을 때만 이동 가능(A - F) 민식이 위치: 빈 곳, 현재 서 있는 곳 (숫자 0) 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳. 탈출로(숫자 1) 민식이는 수평, 수직으로 이동가능하다. 탈출하는데 걸리는 이동 횟수의 최솟값을 구하시오 열쇠와 문은 여러 개일 수도 있다. 문에 대응하는 열쇠가 없을수도 있다. 0은 1개, 1은 적어도 한 개 있다. 열쇠는 여러..
[bfs, bitmasking] 백준 1194번 달이 차오른다, 가자 자바 풀이BOJ 달이 차오른다, 가자 문제 자바(java) 풀이 난이도: 골드1 백준 1194번 달이 차오른다, 가자 문제 정리 미로를 탈출하려 한다. 미로는 다음과 같이 구성되어 있다. 빈 곳: 언제나 이동 가능(.) 벽: 절대 이동 불가(#) 열쇠: 언제나 이동할 수 있다. 이 곳에 처음 들어가면 열쇠를 잡는다(a - f) 문: 대응하는 열쇠가 있을 때만 이동 가능(A - F) 민식이 위치: 빈 곳, 현재 서 있는 곳 (숫자 0) 출구: 달이 차오르기 때문에, 민식이가 가야하는 곳. 탈출로(숫자 1) 민식이는 수평, 수직으로 이동가능하다. 탈출하는데 걸리는 이동 횟수의 최솟값을 구하시오 열쇠와 문은 여러 개일 수도 있다. 문에 대응하는 열쇠가 없을수도 있다. 0은 1개, 1은 적어도 한 개 있다. 열쇠는 여러..
2020.06.17 -
BOJ 7569번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7569번번 토마토 문제 정리 창고에 보관한 토마토중에 잘 익은 것과 익지 않은 것이 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 이다. (대각선 X) 창고의 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하려 한다. 모든 칸에 토마토가 들어있지 않을 수 있다. 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않음 저장될 때 부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지 못한다면 -1 출력 문제 접근 3차원 형태의 배열을 가지고 bfs 탐색을 통해 토마토를 익혀가면 된다. 3차..
[BFS] 백준 7569번 토마토 자바 풀이BOJ 7569번 토마토 문제 자바(java) 풀이 난이도: 실버1 백준 7569번번 토마토 문제 정리 창고에 보관한 토마토중에 잘 익은 것과 익지 않은 것이 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익게 된다. 인접한 곳은 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 이다. (대각선 X) 창고의 토마토들이 며칠이 지나면 다 익게 되는지 최소 일수를 구하려 한다. 모든 칸에 토마토가 들어있지 않을 수 있다. 1: 익은 토마토, 0: 익지 않은 토마토, -1: 토마토가 들어있지 않음 저장될 때 부터 모든 토마토가 익어있는 상태이면 0을 출력 토마토가 모두 익지 못한다면 -1 출력 문제 접근 3차원 형태의 배열을 가지고 bfs 탐색을 통해 토마토를 익혀가면 된다. 3차..
2020.06.15