적자 생존 (Write, Survive!)

백준 1268 - 임시 반장 정하기문제 파악학생 N명에 대해서 1학년부터 5학년까지의 반 배정표가 존재함.1~5학년 다닐 때까지 한 번이라도 같은 반이었던 사람이 가장 많은 사람을 임시 반장으로 세우려고 함.이 때 임시 반장의 번호를 구하는 문제접근 방법3중 for문으로 구현해야 한다.왜냐하면 첫 번째는 학생들을 1번부터 반복하고, 같은 반이었는지 비교하기 위해서 다른 학생들을 이중으로 반복문을 돌린다.세 번째로는 총 5학년이기 때문에 학년을 도는 반복문도 필요하다. 같은 반이라면 카운팅하는 방식이지만, 주의해야 할 점이 있다.바로 한 번이라도 같은 반이었던 사람의 수가 가장 많은 사람을 구하는 문제이기 때문에 여러 번 같은 반이 되었다고 카운트 하는 게 아니다. 여기서 헤맴... 그래서 두 번째 반복문..

백준 2579 - 계단 오르기문제 파악계단에는 각각 점수가 있고, 밟을 때 점수가 된다.계단을 한 칸 또는 두 칸씩 오를 수 있고, 마지막 계단을 꼭 밟아야 함.연속된 세 개의 계단을 밟으면 안될 때, 최대 점수를 구하는 문제접근 방법dp[n-1]을 마지막 계단까지 얻을 수 있는 최대 점수로 놓고 구하면 됨처음에는 단순하게 $max(dp[i-2], dp[i-1])$로 풀 수 있을 줄 알았는데 연속된 계단의 제한이 있어서 번거로운 문제였다.3번째칸 기준으로도 1+2칸, 2+1칸인 경우에 따라 다르고, 2번째칸에서는 무조건 2칸 오르는게 이득이지만 연속 3칸이 안되어서 dp[i-1] + dp[i-2]의 경우도 쓸 수 없었다.그래서 최소 3칸까지는 초기화를 해준다. A를 계단의 배열이라고 할 때,dp[0] =..

백준 1541 - 잃어버린 괄호문제 파악수식이 입력값으로 주어진다. 양수, +, - 로 이루어져있음.괄호를 적절히 배치해서 수식의 결과를 최소로 만드는 문제접근 방법-를 기준으로 오른쪽 값이 최대가 되어야 한다.- 이후의 덧셈만 모두 수행하면 됨.- 기호를 기준으로 split나눠진 파트를 + 기준으로 다시 나눈 후 덧셈을 계산첫 번째 요소는 더해주고, 나머지 요소들은 뺄셈 수행하면 최솟값이 나온다.코드 구현import java.util.*;/* BAEKJOON 1541번 잃어버린 괄호 https://www.acmicpc.net/problem/1541*/public class Main { public static void main(String[] args){ Scanner in..

백준 1744 - 수 묶기문제 파악길이가 N인 수열이 있고, 이 수열의 합을 구하려고 한다.합을 구하기 전에는 수열 안에서 임의의 두 수를 묶어서 곱한 후 수열의 합에 계산하려고 함.위치는 상관없으며, 한 번씩만 묶을 수 있을 때 수열의 합이 최대가 되는 합을 구하는 문제접근 방법음수, 양수, 0, 1의 경우를 나눠서 생각한다.음수일 경우에는 - x - 가 + 양수임을 이용해서 작을 수록 곱했을 때 큰 값이 나오기 때문에 오름차순 정렬을 한다.양수일 경우에는 반대로 최대값이 나오려면 큰 값을 곱해야 하므로 내림차순 정렬을 한다.0은 계산에 들어가진 않지만 음수가 하나 남았을 경우를 대비해 카운팅한다.1은 곱하면 의미가 없기 때문에 무조건 더하기 위해 1의 개수를 카운팅한다.우선순위큐 양수, 음수를 이용해..

백준 1715 - 카드 정렬하기문제 파악이미 정렬된 숫자 카드의 묶음 A, B가 있다고 할 때, 이 A,B를 하나로 만드는데 A+B번 비교해야 함.예시) 20, 30 → 20 + 30 = 50번여러 묶음이 있을 경우에는 10, 20, 40 → (10+20 = 30번), (30+40 = 70번)으로 총 비교횟수는 30+70 = 100번이 된다. 숫자 카드의 묶음이 주어질 때, 최소 비교횟수를 구하는 문제접근 방법작은 수끼리 더하는게 이득이기 때문에 오름차순 정렬을 이용해야 한다.우선순위 큐를 이용해서 더한 후에 다시 추가하여 자동으로 정렬되게 함.우선순위큐의 카드 뭉치들이 1개 남을 때까지 반복두 개의 묶음을 선택둘을 더하고 새 묶음을 큐에 다시 추가한다.더한 값은 누적큐가 종료되었을 경우 누적된 값을 반..

백준 7576 - 토마토문제 파악토마토가 심어져있는 밭에서 토마토가 전부 익는 최대 일수를 구하는 문제익은 토마토 1, 익지 않으면 0, 토마토가 심어져있지 않으면 -1로 표기한다.익은 토마토가 옆에 인접해 있을 경우에만 토마토가 익으며, 대각선 방향으로는 간섭할 수 없음.접근 방법우선, 익은 토마토부터 탐색을 시작하여 전파하기 위해서 익은 토마토 1의 위치를 구하여 시작한다.익지 않은 토마토를 발견했을 경우, 이전 토마토가 익은 일수 + 1로 익은 일수를 표현한다.전체 익은 일수로 표기된 grid 배열에서 최대값을 구한 후 -1을 하여 최대 일수를 반환한다.그림을 참고하면 다음과 같다. 코드 구현import java.util.*;import java.io.*;/* BAEKJOON 7576번 토마토..

백준 1931 - 회의실 배정문제 파악한 개의 회의실을 N개의 회의에 대해 사용하기 위해서 회의실 사용표를 만들려고 함.각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않고 최대로 사용할 수 있는 회의의 수를 구하는 문제회의는 한 번 시작하면 중단될 수 없으며, 한 회의가 끝나는 동시에 다음 회의가 시작될 수 있음. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 됨.접근 방법끝나는 시간 순으로 우선순위큐에 저장 (처음에 시작 시간 순으로 정렬해서 망함…)반복문으로 다음 시작 시간을 현재 시간이랑 비교해서 회의를 진행회의가 진행되면 카운팅코드 구현import java.util.*;import java.io.*;public cl..

백준 1260 - DFS와 BFS문제 파악DFS와 BFS로 그래프를 탐색한 결과를 각각 출력하는 문제하지만 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건이 있다. (이걸 몰라서 첨에 틀렸음…)접근 방법그래프를를 연결한다.노드의 다음 방문 노드 그래프를 정렬방문배열 초기화DFS 구현 및 실행방문배열 다시 초기화BFS 구현 및 실행코드 구현import java.util.*;import java.io.*;public class Main { static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new ..

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 파악위에는 N극, 아래에는 S극이 흐르고 있는 자성체들이 놓여있는 테이블이 존재함.자성체들은 각각 빨간색(N극 성질)은 S극에 반응하고, 파란색(S극 성질)은 N극에 반응함. 서로 이끌려서 테이블에 떨어지려고 할 때, 서로 충돌이 나게 되면 이를 교착 상태라고 함. 셋 이상의 자성체들의 충돌도 하나의 상태지만, 각각 다른 교착 상태일 경우에는 2개의 교착 상태로 봄. 100x100 테이블이 주어질 때, 교착상태의 수를 구하는 문제접근 방법빈칸은 무시하고, 1,2의 경우만 처리파란색(2)를 찾고, 직접값이 빨간색(1)인 경우 교착상..

SW Expert Academy SW Expert AcademySW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!swexpertacademy.com 문제 파악주어진 숫자판들 중에 두 개를 선택해서 정해진 횟수만큼 서로의 위치를 교환할 수 있음.예시) 3, 2, 8, 8, 8의 5개의 숫자판들이 주어지고 교환 횟수가 2회일 때 3과 8의 위치를 두 번 교환해서 88832로 만들 수 있음.오른쪽부터 1원이고 10의 배수로 증가한다고 할 때 최종 보너스 상금은 88832원을 획득하게 된다.교환횟수만큼 반드시 교환이 일어나야 하고, 1회라도 수행해야 함. 정해진 횟수만큼 숫자판을 교환했을 때 받을 수 있는 가장 큰 금액을 계산하는 문제접근 방법두 수를 교환하는 형태 → 전체 L개 중에서 ..