알고리즘 문제풀이/BOJ
-
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 7579번 앱 문제 자바(java) 풀이 난이도: 골드3 BOJ 7579번 앱 문제정리 비활성화: 필요한 메모리가 부족해질때 스마트폰의 OS가 앱들 중 몇개를 삭제하는 과정 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문에 필요한 메모리만큼 비활성화 하는 것은 좋지 않다. N개의 앱이 활성화 되어있다. 앱은 각각 m 바이트 만큼의 메모리를 사용하고 있다. 앱을 비활성화한 후 다시 싫애하고자 할 경우 추가적으로 들어가는 비용은 c 이다. 메모리 M이 추가로 필요하여 비활성화 하고자 할때 비용 c의 합이 최소가 되는 방법을 찾는다. 문제 풀이 다이나믹 프로그래밍 기법을 이용합니다. 모든 경우를 따져서 하기에는 시간이 부족하기 때문입니다. 이와 유사한 문제를 풀어봤던 것 같은데 잘 기억..
[DP] 백준 7579 앱 자바(java) 코드BOJ 7579번 앱 문제 자바(java) 풀이 난이도: 골드3 BOJ 7579번 앱 문제정리 비활성화: 필요한 메모리가 부족해질때 스마트폰의 OS가 앱들 중 몇개를 삭제하는 과정 비활성화된 앱들을 재실행할 경우 그만큼 시간이 더 필요하기 때문에 필요한 메모리만큼 비활성화 하는 것은 좋지 않다. N개의 앱이 활성화 되어있다. 앱은 각각 m 바이트 만큼의 메모리를 사용하고 있다. 앱을 비활성화한 후 다시 싫애하고자 할 경우 추가적으로 들어가는 비용은 c 이다. 메모리 M이 추가로 필요하여 비활성화 하고자 할때 비용 c의 합이 최소가 되는 방법을 찾는다. 문제 풀이 다이나믹 프로그래밍 기법을 이용합니다. 모든 경우를 따져서 하기에는 시간이 부족하기 때문입니다. 이와 유사한 문제를 풀어봤던 것 같은데 잘 기억..
2020.04.03 -
BOJ 18809번 Gaaaaaaaaaarden 문제 자바(java) 풀이 난이도: 골드1 BOJ 18809번 Gaaaaaaaaaarden 문제정리 빨간색, 초록색 배양액을 이용해 꽃을 피운다. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져나간다. 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 경우 땅에서 꽃이 핀다. 꽃이 핀 땅에서는 배양액이 사려저 더 이상 배양액이 퍼지지 않는다. 모든 배양액은 서로 다른 곳에 뿌린다. 꽃의 최대 개수를 구하여라 문제 풀이 배양액을 놓을 수 있는 위치가 여러군데 있습니다. 그 중에서 놓을 곳을 정해야 합니다. 또한 그 위치에 어떠한 색의 배양액을 놓을지 정해야합니다. 그래서 처음에 배양액을 놓을 곳의 순열을 구하고 배양액의 순열을 또..
[BFS, 순열] 백준 18809번 Gaaaaaaaaaarden 자바(java) 풀이BOJ 18809번 Gaaaaaaaaaarden 문제 자바(java) 풀이 난이도: 골드1 BOJ 18809번 Gaaaaaaaaaarden 문제정리 빨간색, 초록색 배양액을 이용해 꽃을 피운다. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져나간다. 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 경우 땅에서 꽃이 핀다. 꽃이 핀 땅에서는 배양액이 사려저 더 이상 배양액이 퍼지지 않는다. 모든 배양액은 서로 다른 곳에 뿌린다. 꽃의 최대 개수를 구하여라 문제 풀이 배양액을 놓을 수 있는 위치가 여러군데 있습니다. 그 중에서 놓을 곳을 정해야 합니다. 또한 그 위치에 어떠한 색의 배양액을 놓을지 정해야합니다. 그래서 처음에 배양액을 놓을 곳의 순열을 구하고 배양액의 순열을 또..
2020.04.03 -
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