본문 바로가기

Algorithm43

[백준] BOJ 11501 주식(자바/시간 초과) 문제 유형 전부 계산해 보는 그리디 알고리즘이다. 어려웠던 점 1. 먼저 처음 풀이할 때는 배열을 int i = 0부터 시작하여 최대 수익을 계산했다. 이중 for문을 사용하여 문제를 풀었다. 그랬더니 시간초과가 발생했다. 그래서 뒤에서 부터 for문을 돌면서 수익을 낼 수 있으면 결괏값에 더하고, 아닌 경우 max를 갱신했다. 틀렸는데 반례를 확인해봐도 도저히 이유를 몰랐다. 이유는 문제에서 찾을 수 있었다. 무심코 넘어갔던 출력 조건인 부호 있는 64bit 정수형으로 표현 가능하다는 조건이 존재한다. 여기서 long 타입은 64bit 정수형, int 타입이 32bit 정수형이라는 점이다. 따라서, 결과값을 출력할 때 long 타입으로 출력해야 했다. 쉬웠던 문제인데 뭔가 실수도 많았던 것 같다. 조건.. 2023. 5. 2.
[백준] BOJ 7569 토마토 (자바/3차원/BFS) 문제 유형 파악하기 다음과 같은 조건이 주어진다. 이때, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들이 하루가 지날 때마다 익은 토마토로 변한다는 조건으로 인해 전형적인 BFS 문제임을 파악했다. 또한, 위, 아래, 왼쪽, 오른쪽, 앞, 뒤 여섯 방향이라는 조건이 있는데, BFS 탐색하면서 이 방향에 대해 다 확인해 보면 됨을 느꼈다. 문제 풀이 1. 이 문제에서 핵심은 3차원 배열을 사용한다는 점이다. 처음에 3차원 배열을 사용해야 하는지 몰라서 애먹었다. 그래서 나는 3차원 배열을 선언하며 maps[높이][세로][가로]로 설정하여 문제를 풀었다. 2. 큐에는 먼저 익은 토마토의 좌표를 전부 넣어 준 다음 BFS 탐색을 수행하였다. 3. BFS 탐색 시 안 익은 토마토인 경우에는 큐에 넣고 다.. 2023. 4. 29.
[프로그래머스] 구명보트 (자바/그리디) 문제 설명 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해 주세요. 풀이 방법 가장 작은 무게와 가장 큰 무게를 더해서 그게 무게 제한보다 작은지 확인해 보면 되는 문제이다. 어려웠던 점 처음에는 정렬을 한 다음에 무게가 작은 순부터 더해서 답을 구했다. 다음과 같이 50 50 70 80이 주어지면 50+50, 70, 80 이런 식으로 작은 무게부터 2개씩 더해보고 무게 제한보다 작으면 결괏값을 갱신했다. 그러면 주어진 입출력 예제는 맞았는데 제출해 보니 30.0/100.0 임을 알 수 있었다. 이런 방법으로는 다음과 같은 반례가 존재함을 알 수.. 2023. 3. 25.
[백준]BOJ 1068 트리(DFS/반례) [어려웠던 점] 처음에는 '전체 리프 노드 개수 - 지우려는 노드를 루트 노드로 했을 때 리프 노드 개수'를 진행하였다. 그러면, 다음 예시 같은 경우에는 0을 루트 노드로 하면 리프 노드 3개, 1을 루트 노드로 하면 리프 노드 2개이므로, 3 - 2 = 1이므로 답 1을 구할 수 있었다. 그런데, 이와 같은 경우는 다음과 같은 반례를 도출한다. 다음은 노드를 지우고 나면 루트 노드가 하나 남는 상황이다. 그렇다면 답은 1이 나와야 한다. 이와 같은 경우에서 나는 내가 기존에 생각했던 코드의 문제점을 찾아낼 수 있었다. 2 -1 0 1 그래서, 이 코드는 백준에서 70%~80%대에서 틀렸다.... [문제 해결 과정] 문제 해결 과정은 다음과 같다. 1. 연결 리스트에서 지우려고 하는 노드 번호와 일치하.. 2023. 3. 9.

티스토리툴바