본문 바로가기

알고리즘/문제풀이

(26)

백준 1194 - Java (BFS,비트마스킹) https://www.acmicpc.net/problem/1194 풀이 이 문제를 보면 기본적으로 bfs를 사용해서 풀 수 있겠다는 생각이 든다.하지만 어려운 부분은 바로a, b, c, d ,e ,f 라는 열쇠와 그에 대응하는A, B, C, D, E, F 라는 문에 대해서이다. 이에 이진법으로 각 열쇠마다 아래와 같이 대입한다 a= 1(2), b = 10(2), c = 100(2) ...그럼 a와 c열쇠를 가지고 있다면 101(2)이 되는것이다.!그렇다면 a,c열쇠를 가진 상태를 정수로 하면 5가 될것이다.int now = 5 // 현재 가진 열쇠정보A라는 문을 만난다면 아래 조건식처럼 계산하면 된다// 예제코드 문에 해당하는 열쇠검사1if ((now & (1 그리고 a~f 까지면 111111(2) 이..

백준 16236 아기상어 - Java https://www.acmicpc.net/problem/16236 풀이문제의 이 조건 때문에 조금 까다로웠다."먹을 수 있는 생선이 한마리면 그것을 먹고 두 마리 이상이면 가장 가까운 거리의 생선을 먹는다. 또한 가장 가까운 거리의 생선이 여러마리면 가장 위에 생선을 먹고가장 위에 생선역시 여러마리면 가장 좌측의 생선을 먹는다"이 부분에서 해맸지만 레벨탐색으로 레벨마다 체크한다면 거리는 따질 필요가 없으니 좌표만을 비교해 구하면 된다는 것을 깨달았다.!! 나의 풀이 순서는 다음과 같다.1. 입력받은 생선이 1마리 이상이면 실행 아니면 0 출력2. 상어가 갈 수 있는 곳을 탐색한다. (상어크기 이하면 갈 수 있음) 2-1. 상어크기와 생선크기다 똑같다. 이동만 수행. 2-2. 상어크기보다 ..

백준 0 만들기 - Java https://www.acmicpc.net/problem/7490 - 예제입력237 - 예제출력1+2-31+2-3+4-5-6+71+2-3-4+5+6-71-2 3+4+5+6+71-2 3-4 5+6 71-2+3+4-5+6-71-2-3-4-5+6+7 풀이요약:"1+2-3" ... 의 식(String)을 만들어 식의 파라미터로 결과값이 0인지 확인하는isZero(String exp)함수로 0이면 해당 식을 리스트에 저장하고테스트 케이스마다 식을 아스키 순서로 정렬 후 최종출력할 StringBuilder sb에 저장. 테스트 케이스 끝나면 최종 정답 출력 1. n 이 3 이라면1 2 3의 숫자에 + , - " "(붙이기)등의 연산자가 필요하다가능한 모든 경우를 계산해야 한다. 여기서 n이 3이면 세 개의 숫..

백준 1776 문제집 - Java https://www.acmicpc.net/problem/1766 * 예제입력4 24 23 1 * 예제출력3 1 4 2 풀이 이 문제는 n가지 문제 중 특정 문제를 먼저 풀어야 한다. 또한 가능하면 쉬운문제(낮은 번호의 문제)부터 풀어야 한다.이렇게 순서가 정해져 있는 작업의 문제는 위상 정렬 (Topological Sorting)알고리즘으로 풀 수 있다. 위상 정렬 알고리즘의 조건은 비순환 방향 그래프여야 한다. 위상 정렬의 구현을 위해서 일반적으로 큐, 배열 , 인접리스트가 필요하다.이제 순서대로 문제를 풀기 위해 단계별로 설명한다. 또한 이 문제는가능한 쉬운 문제, 즉 번호가 낮은 문제부터 풀어야하므로 일반큐 말고 우선순위 큐를 이용할 것이다. 준비단계문제 우선순위에 따라 인접리스트에 저장한다.e..

백준 1520 내리막길(dfs,메모이제이션) - Java https://www.acmicpc.net/problem/1520 - 예제 입력4 550 45 37 32 3035 50 40 20 2530 30 25 17 2827 24 22 15 10 - 예제 출력3 풀이 처음에 단순히 BFS로 풀었는데 메모리 초과로 실패했다.때문에 메모이제이션을 사용하는 방법으로 한다.위 예제 입출력으로 답이 3이다.이 사진처럼 (0,3)위치에서 목적지(최 우측 하단)로 가는방법은 2가지가 나온다. 그렇다면 n*m 크기의 dp배열에해당 경로에서 목적지까지 가는 경로의 경우의 수를 메모이제이션 해서 쓰는 방식으로 한다면 복잡도를 크게 줄일 수 있다.또한 탐색은 dfs 재귀를 이용한다. dp배열은 -1 값으로 초기화 한다.dp[?][?] == -1 => 탐색dp[?][?] != ..

백준 11497 통나무 건너뛰기 - Java https://www.acmicpc.net/problem/11497 - 예제 입력 13713 10 12 11 10 11 1252 4 5 7 986 6 6 6 6 6 6 6 - 예제 출력 1140 풀이 이 문제는 그리디 성격의 문제인거 같다통나무들의 높이가 들어있는 배열이 아래와 같이 있다고 할때{2, 4 ,5 ,7 ,9}인접한 통나무들의 높이의 차 중에 가장 높은값이 난이도가 되는데 , 최소 난이도를 구해야 한다.또한 0번째 통나무와 마지막(n-1) 번째 통나무는 인접해있다.위 배열에서 보면 인접한 통나무는 아래와 같다.2 9 -> 난이도: 72 4 -> 난이도: 24 5 -> 난이도: 15 7 -> 난이도: 27 9 -> 난이도: 2난이도는 7이 된다. 자 그럼 이제 통나무의 순서를 우리는 ..

백준 14503 로봇 청소기(시뮬레이션) - Java https://www.acmicpc.net/problem/14503 - 예제입력13 31 1 01 1 11 0 11 1 1 - 예제출력11 - 예제입력211 107 4 01 1 1 1 1 1 1 1 1 11 0 0 0 0 0 0 0 0 11 0 0 0 1 1 1 1 0 11 0 0 1 1 0 0 0 0 11 0 1 1 0 0 0 0 0 11 0 0 0 0 0 0 0 0 11 0 0 0 0 0 0 1 0 11 0 0 0 0 0 1 1 0 11 0 0 0 0 0 1 1 0 11 0 0 0 0 0 0 0 0 11 1 1 1 1 1 1 1 1 1 - 예제출력257 풀이 문제는 조금 길지만 간단한 구현 문제이다.청소 안된방 = 0 , 청소한 방 = -1, 벽 = 1 로 하기로 한다.로봇 청소기가 바라보는 방향 s..

백준 1823 수확(DP) - Java https://www.acmicpc.net/problem/1823 * 예제입력513152 * 예제출력43 풀이1. DP로 풀어야 한다.n=5이고 5번 숫자를 입력받는다. 이를 정수형 배열에 넣는다.배열 arr의 크기는 n이 아닌 편의를 위해 n+1 로 지정함.그럼 arr={0, 1, 3, 4, 5, 7} 2. DP로 풀기위해 2차원 배열 생성.int [][]dy = new int[n+1][n+1];먼저 단일 반복문으로 1~n까지 dy[i][i] = arr[i] 에 넣는다.그럼 아래 이미지와 같다. 이 말은 1, 3, 1 ,5, 2 각 한자리 수로 수확하는 값이다1*1, 3*1... 은 자기 자신이니까 값이 대입된다. 2. 이제부터가 중요하다.dy[1][2]를 구해야 한다.참고로 dy[1][2]의 의..

이전 1 2 3 4 다음

티스토리툴바