백준
-
BOJ 16986 인싸들의 가위바위보 자바(java) 풀이 랭크 : 골드3 백준 16986 인싸들의 가위바위보 문제 정리 모두가 동시에 경기를 진행하는 대신 일대일 경기를 여러 번 진행해 누가 우승했는지 판단한다. 참가자 3명이서 동시에 경기를 진행할 때, 우승자를 정하기 위한 구체적인 방식은 다음과 같다 2.1 게임 시작전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의 한다. 2.2 두 사람이 무승부가 날 경우 진행 순서상 뒤의 사람이 이긴 것으로 간주한다. 2.3 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다. 2.4 특정 사람이 미리 합의된 승수를 달성할 때 까지 2.3을 반복한다. 2.5 합의된 승수를 최초로 달성한 사람이 우승한다. 상대방 두명이 낼..
[순열, 완전탐색] 백준 16986 인싸들의 가위바위보 자바(java) 풀이BOJ 16986 인싸들의 가위바위보 자바(java) 풀이 랭크 : 골드3 백준 16986 인싸들의 가위바위보 문제 정리 모두가 동시에 경기를 진행하는 대신 일대일 경기를 여러 번 진행해 누가 우승했는지 판단한다. 참가자 3명이서 동시에 경기를 진행할 때, 우승자를 정하기 위한 구체적인 방식은 다음과 같다 2.1 게임 시작전 우승을 위해 필요한 승수와 경기 진행 순서를 미리 합의 한다. 2.2 두 사람이 무승부가 날 경우 진행 순서상 뒤의 사람이 이긴 것으로 간주한다. 2.3 이전 경기의 승자와 이전 경기에 참여하지 않은 사람이 경기를 진행해 승자를 결정한다. 2.4 특정 사람이 미리 합의된 승수를 달성할 때 까지 2.3을 반복한다. 2.5 합의된 승수를 최초로 달성한 사람이 우승한다. 상대방 두명이 낼..
2020.04.08 -
BOJ 1941번 소문난 칠공주 자바(java) 풀이 랭크 : 골드3 백준 1941번 소문난 칠공주 문제 정리 학급은 5x5의 정사각형 형태로 자리가 배치되어있다. 학급이 두 파로 나뉘게 되었다. 이다솜파는 소문난 칠공주 체제를 결성하기로 하였다. 3.1 7명의 여학생들로 구성된다 3.2 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 3.3 반드시 '이다솜파'의 학생들로만 구성될 필요는 없다. 3.4 그러나 '이다솜파'의 학생은 적어도 4명 이상 반드시 포함되어 있어야 한다. 자리 배치도가 주어졌을 때, 소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하여라. 문제 풀이 모든 경우를 따져주어야 합니다. 자세한 사항은 주석을 통해 달아두었습니다! 로직은 아래..
[조합, BFS] 백준 1941번 소문난 칠공주 자바(java) 풀이BOJ 1941번 소문난 칠공주 자바(java) 풀이 랭크 : 골드3 백준 1941번 소문난 칠공주 문제 정리 학급은 5x5의 정사각형 형태로 자리가 배치되어있다. 학급이 두 파로 나뉘게 되었다. 이다솜파는 소문난 칠공주 체제를 결성하기로 하였다. 3.1 7명의 여학생들로 구성된다 3.2 7명의 자리는 서로 가로나 세로로 반드시 인접해 있어야 한다. 3.3 반드시 '이다솜파'의 학생들로만 구성될 필요는 없다. 3.4 그러나 '이다솜파'의 학생은 적어도 4명 이상 반드시 포함되어 있어야 한다. 자리 배치도가 주어졌을 때, 소문난 칠공주를 결성할 수 있는 모든 경우의 수를 구하여라. 문제 풀이 모든 경우를 따져주어야 합니다. 자세한 사항은 주석을 통해 달아두었습니다! 로직은 아래..
2020.04.07 -
BOJ 12851번 숨바꼭질2 자바(java) 풀이 랭크 : 골드5 백준 12851번 숨바꼭질2 문제 정리 수빈이는 현재 점 N에 있다. 동생은 점 K에 있다. 수빈이는 1초 후에 N-1, N+1, Nx2의 위치로 이동할 수 있다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후 인가?? 가장 빠른 방법의 수도 찾아서 출력해라. 문제 풀이 bfs를 이용하면 풀 수 있는 문제입니다. 원래 bfs를 구현하게 되면 보통 최적화를 위해서 queue에 넣고 바로 방문처리를 합니다. 하지만 그것은 최적화 즉, 넣었다 뺐다 반복하지 않도록 하는 것입니다. 이 문제는 그렇게 해서는 풀 수 없습니다. 가능한 모든 개수를 세야하기 때문입니다. 반례 예를들어 1 4의 경우 (1+1)x2 (1x2)x2 위와 같이 두..
[BFS] 백준 12851번 숨바꼭질2 자바(java) 풀이BOJ 12851번 숨바꼭질2 자바(java) 풀이 랭크 : 골드5 백준 12851번 숨바꼭질2 문제 정리 수빈이는 현재 점 N에 있다. 동생은 점 K에 있다. 수빈이는 1초 후에 N-1, N+1, Nx2의 위치로 이동할 수 있다. 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇초 후 인가?? 가장 빠른 방법의 수도 찾아서 출력해라. 문제 풀이 bfs를 이용하면 풀 수 있는 문제입니다. 원래 bfs를 구현하게 되면 보통 최적화를 위해서 queue에 넣고 바로 방문처리를 합니다. 하지만 그것은 최적화 즉, 넣었다 뺐다 반복하지 않도록 하는 것입니다. 이 문제는 그렇게 해서는 풀 수 없습니다. 가능한 모든 개수를 세야하기 때문입니다. 반례 예를들어 1 4의 경우 (1+1)x2 (1x2)x2 위와 같이 두..
2020.04.04 -
BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이 난이도: 골드3 BOJ 16985번 Maaaaaaaaaze 문제정리 3차원 미로 탈출 대회 개최 5x5 크기의 판이 5개 주어진다. 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다. 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다. 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다. 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다. 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다. 문제 풀이 이 문제는 ..
[BFS, 순열] 16985번 Maaaaaaaaaze 자바(java) 풀이BOJ 16985번 Maaaaaaaaaze 문제 자바(java) 풀이 난이도: 골드3 BOJ 16985번 Maaaaaaaaaze 문제정리 3차원 미로 탈출 대회 개최 5x5 크기의 판이 5개 주어진다. 하얀색 칸은 참가자가 들어갈 수 있는 칸, 검은 칸은 못들어가는 칸이다. 참가자는 주어진 판들을 시계 or 반시계 방향으로 자유롭게 회전할 수 있다. 뒤집을 수는 없다. 회전을 완료한 후 참가자는 판 5개를 쌓는다. 쌓는 순서는 참가자 마음대로 한다. 입구는 참가자가 임의로 선택한 꼭지점. 출구는 입구와 면을 공유하지 않는 꼭짓점 참가자 중에서 본인이 설계한 미로를 가장 적은 이동 횟수로 탈출한 사람이 승리한다. 입구에서 출구로 도달할 수 있는 방법이 없는 경우 탈출이 불가능 하다. 문제 풀이 이 문제는 ..
2020.04.01 -
BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
[DFS] 백준 16987번 계란으로 계란치기 자바(java) 풀이BOJ 16987번 계란으로 계란치기 문제 자바(java) 풀이 랭크 : 실버3 백준 16987번 계란으로 계란치기 문제 정리 계란으로 계란을 치는 경우 다음과 같은 점들을 고려한다. 1.1 계란에는 내구도와 무게가 정해져 있다. 1.2 계란으로 서로를 치면 계란의 내구도는 상대 계란의 무게 만큼 깎이게 된다. 1.3 내구도가 0이 되는 순간 계란이 깨진다. 계란을 왼쪽 부터 차례로 들어 한 번씩만 다른 계란을 쳐서 최대한 많은 계란을 깨려고 한다. 계란을 치는 과정은 다음과 같다. 3.1 가장 왼쪽 계란을 든다. 3.2 손에 든 계란으로 깨지지 않은 계란중 하나를 친다. 만약 손에 든 계란이 깨졌거나 깨지지 않은 계란이 없다면 아무일도 하지 않는다. 3.3 최근에 든 계란의 바로 오른쪽 계란을 들고 반..
2020.04.01 -
BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
[백트래킹] 백준 2580번 스도쿠 자바(java) 풀이BOJ 2580번 스도쿠 자바(java) 풀이 백트래킹의 대표적인 문제중 하나라고 할 수 있습니다. 백트래킹 문제에 익숙하지 않다면 N-Queen 문제와 이 문제를 꼭 풀어보시기 바랍니다. 난이도: 골드4 BOJ 2580번 스도쿠 문제 정리 9x9 판으로 이루어진 판에 1~9 까지의 숫자들이 써있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1~9까지의 숫자가 한 번씩만 나타난다. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1~9 까지의 숫자가 한 번씩만 나타난다. 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오. 스도쿠 판을 채우는 방법이 여럿인 경우 그 중 하나만을 출력한다. 문제 풀이 n-queen 문제와 유사한 방식으로 백트래킹을 이용하여 문제..
2020.03.31