백준133 [백준 2504] 괄호의 값 / 자바 / 구현(괄호) #문제 레벨: G5알고리즘: 구현(괄호)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2504#문제 풀이 괄호문제가 보면 스택문제임을 깨달아야 한다. 근데 평상시 만났던 괄호가 올바른지 검사하는 문제가 아니라 괄호의 값을 계산하는 문제이다. 바로 문제 설명하겠다.( () () ) 가장 안쪽에 있느 ()는 원래 2이다. 그런데 우린 () 앞에 (가 있었으므로 4라고 칠 거다. 그 옆에 있는 ()도 4라고 치자. 그럼 답이 8이 나오지 않은가?이게 어떻게 이렇게 될 수 있을까? 분배법칙 때문에 그렇다. ( () () ) 는 (()) (()) 와 같다. 즉, 2x(2+2) 이나 (2x2 + 2x2)는 같다. 그러니 우리.. 2024. 8. 2. [백준 17144] 미세먼지 안녕! / 자바 / 구현 #문제 레벨: G4알고리즘: 구현풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/17144#문제 풀이 제목이 상쾌하여 문제에 대한 호감도가 올라갔다. 풀면서 구현 문제에 적합한 것 같아 호감도가 더 올라갔다.이문제에서 우리가 구현할 것은1. 미세먼지 확산2. 공기청정기 바람 부는 것 3 . 토탈 먼지 수 구하기이 두가지이다. 1 ~ 2번을 T초 동안 반복 후 최종적으로 3번을 통해 답을 구하면 된다. 미세먼지 확산은 기존배열을 참조하여 temp(임시)배열에 값을 추가하거나 빼주면 된다................(1)기존 배열을 수정하면 다른 미세먼지 확산을 계산할 때 영향을 미치기 때문에 일단은 temp배열에 다 계산해주고 기존 배.. 2024. 8. 2. [백준 14891] 톱니바퀴 / 자바 / 구현 + 자료구조 #문제 레벨: G5알고리즘: 구현 + 자료구조풀이시간: 1시간힌트 참조 유무:https://www.acmicpc.net/problem/14891#문제 풀이 위 문제는 간단한 구현 문제이다. 회전을 하기 전 그 상태가 모든 톱니바퀴의 회전 여부를 결정하기 때문이다. 만약 처음 그상태가 아니라 톱니바퀴 하나를 돌리고 나서 다른 톱니바퀴의 회전 여부를 결정해야 했다면 이것보다는 조금 더 구현이 복잡해졌을 수 있다. 1. 해당 톱니바퀴를 기준으로 연속적으로 왼쪽 톱니바퀴들이 회전하는지 체크하고 같은 방식으로 오른쪽 톱니바퀴들이 회전하는지 체크한다.2. 회전 시켜준다. 3. 스코어를 구한다. 난 이 문제를 통해 구현연습을 한 것도 있지만 자료구조를 더 집중적으로 공부해봤다. 톱니바퀴의.. 2024. 8. 1. [백준 16724] 피리 부는 사나이 / 자바 / dfs #문제 레벨: G3알고리즘: dfs풀이시간: 40분힌트 참조 유무:https://www.acmicpc.net/problem/16724#문제 풀이 문제를 쉽게 설명하자면 "시간은 상관없이 방향에 따라 이동할 때 언젠가는 세이프존에 들어갈 수 있게 해라"이다. 문제에 나와있지는 않지만 방향에 따라 갔을 때 배열을 벗어나는 경우는 없다. 이 부분이 설명이 안 되어있는게 아쉽긴 하다. 그럼 우린 dfs를 통해 싸이클을 돌면 된다. 배열 내에 싸이클의 개수가 답인 거다.dfs+cycle 개념이 이해가 안 간다면 아래에 관련 문제 링크 참조해둘테니 연습해보면 좋을 것이다.#풀이 코드 import java.util.Scanner;public class Main { static .. 2024. 7. 31. [백준 1405] 미친 로봇 / 자바 / dfs #문제 레벨: G4알고리즘: dfs풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/1405#문제 풀이 되게 간단한 문제이다. 문제에서는 배열에서 움직인다고 말을 안해서 눈치를 못챌 수도 있는데, 자기가 직접 30x30(넉넉한 배열)배열 중앙을 시작점으로 로봇을 움직이면 되는 문제이다. 갔던 길은 visited = true로 표시한채 말이다.주의해야 할점은 정답은 10의 마이너스9승까지 나타낸다 했으니 float이 아닌 double로 출력해야 한다.#풀이 코드 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.StringTokenizer.. 2024. 7. 30. [백준 20058] 마법사 상어와 파이어스톰 / 자바 / 구현 + bfs 조금 *** #문제 레벨: G3알고리즘: 구현 + bfs 조금풀이시간: 2시간힌트 참조 유무: 유 https://www.acmicpc.net/problem/20058#문제 풀이 이 문제는 bfs문제로 분류되어있지만, 사실상 구현문제라 생각한다. 이 문제에 핵심은 격자회전시키는 식을 잘 세울 수 있는지이다. 그 방법을 바로 말하겠다. 오른쪽으로 90도 회전한다고 하면 map[i][j]가 map [j][n-1-i]가 된다. 즉, i와 j를 바꿔주고 열은 n-1에다가 바꾼 i를 빼준다. (왼쪽으로 90도 회전한다고 하면 거꾸로 돼서 map[i][j]가 map[n-1-j][i]가 된다.) 우리는 덩어리 째 회전을 시켜야 하므로 이중 for문에서 i+=L 씩 증가시켜줘야 한다. 위 방식을 이해하고 .. 2024. 7. 29. [백준 2250] 트리와 높이와 너비 / 자바 / dfs *** #문제 레벨: G2알고리즘: dfs 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2250 #문제 풀이 처음에는 이런 생각을 했다. 가장 오른쪽에 있는 노드를 찾은 후 같은 레벨에 있고 가장 왼쪽에 있는 노드를 찾은 것을 이용하여 구한 값과, 가장 왼쪽에 있는 노드를 찾은 후 같은 레벨에 있고 가장 오른쪽에 있는 노드를 찾은 것을 이용하여 구한 값 중 최솟값을 구한다. 그러나 나 너무 지엽적인 방법이기도 하고 깊이와 x값을 성정하는 dfs 하나 가장 오른쪽 노드 찾는 dfs 하난 가장 왼쪽 노드 찾는 dfs 하나 dfs를 총 세 번 돌아야 한다. 위 방법보다 더 좋은 방법을 소개하겠다.바로 dfs함수 하나에서 레벨과 x좌표와 그.. 2024. 7. 27. [백준 4803] 트리 / 자바 / bfs #문제 레벨: G4알고리즘: bfs 풀이시간: 40분힌트 참조 유무:https://www.acmicpc.net/problem/4803#문제 풀이 이 문제는 트리와 그래프를 구별할 수 있냐 없냐이다.트리의 간선 개수는 노드-1이다. 그래프의 간선 개수는 노드개수보다 많다. 그래서 우린 노드와 간선의 개수를 비교해서 트리를 구별해야한다. 그 노드를 방문 했든 안했던 해당 노드와 이어져 있는 노드의 간선들을 더한다. 오른쪽 그림을 예시를 들면1 방문 2개 추가(2,3)2 방문 2개 추가 (1,3)3 방문 2개 추가(1,2)총 간선의 개수는 6개이다. 이렇게 나온 이유는 같은 선을 중복해서 계산하기 때문이다. 중복해서 계산을 안 하려고 하면 구현이 어려워진다. 구한 간선.. 2024. 7. 26. [백준 10159] 저울 / 자바 / dfs #문제 레벨: G4알고리즘: dfs 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/10159#문제 풀이 그래프로 나타내면 문제풀이 하기 더 수월하다.위 그래프는 자기보다 가벼운 노드를 나타낸 거다.아래 그래프는 자기보다 무거운 노드를 나타낸 거다. 두 번의 dfs를 통해 자신보다 무거운 노드들, 가벼운 노드들을 알아내면 정답을 알 수 있다. 1번 노드를 예를 들어보자dfs(1,lighter)를 하면 1 -> 2 -> 3 -> 4 = 3(자기자신제외)dfs(1,heavier)를 하면 1 -> x = 0(자기자신제외)6(N) - 1(자기 자신) - 3 - 0 = 2 #풀이 코드 import java.ut.. 2024. 7. 25. 이전 1 ··· 3 4 5 6 7 8 9 ··· 15 다음
