본문 바로가기

알고리즘/백준33

[백준 14719번 / 빗물 / JAVA / 투포인터] https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 문제 접근 가로 길이와 크기가 같은 배열을 만들고 각 인덱스에 높이를 지정 각 인덱스를 돌면서 각 인덱스 기준으로 왼쪽의 가장 큰 높이와 오른쪽의 가장 큰 높이를 찾는다. 그럼 그 사이 공간에 빗물이 고이며 빗물은 최소한 가장 큰 높이인 왼쪽, 오른쪽 중 작은 숫자에서 각 인덱스의 높이를 뺀 만큼은 차게 된다. 이렇게 모든 인덱스를 돌면서 해당 인덱스마다 고이게 되는 빗물을 탐색.. 2023. 4. 20.
[백준 19637 / IF문 좀 대신 써줘 / JAVA / 이진 탐색] https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 문제 접근 밀리야.. * 이분(이진) 탐색은 정렬되어 있는 데이터에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법 * 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야한다. https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%.. 2023. 4. 19.
[백준 5014번 / 스타트링크 / JAVA / BFS] https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 문제 접근 모든 층을 탐색하는 건 쉽게 나왔으나 목표층을 방문하지 못할 시 실패 문구를 뜨게하는 조건이 문제였다. UP, DOWN으로 모든 층을 탐색하고 도달하지 못하게 될 경우 반복문을 나와서 출력해주자라곤 생각했으나 쉽지 않았다. 핵심은 큐를 사용해 탐색할 층을 넣어두는 것, 더 이상에 큐에 값이 없단 건 새로 방문할 층이 없단 것 while문을 돌면서 계속 큐에 값을 삽입하고 층 탐색 시 값을 꺼낸다. .. 2023. 4. 18.
[백준 3020번 / 개똥벌레 / JAVA / 누적합] https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제 접근 List에 차례대로 모든 석순과 종유석을 저장하니 시간 초과가 떴다. 다른 방법을 참고하니 모든 석순과 종유석을 저장하는 게 아니라 각 높이 별로 석순과 종유석이 몇 개 있는지 카운팅해서 사용하는 게 시간을 단축해주는 방법이더라 → List 대신 배열로 인덱스 마다 해당 높이의 석순, 종유석 갯수 체크 이후 각 구간 별로 이전까지의 석순과 종유석을 누적 합산 높이만큼 반복문을 돌면서 (전체.. 2023. 4. 16.
[백준 / 팰린드롬 만들기 / JAVA] https://www.acmicpc.net/problem/1254 1254번: 팰린드롬 만들기 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 규완이는 팰린드롬을 엄청나게 좋아한다. 팰린드롬이란 앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다. 동호는 www.acmicpc.net 문제 접근 머릿 속에서 떠올리는 거랑 직접 코드로 짜는 거랑은 다르다고 느꼈다. 문제를 풀 수 있는 규칙을 떠올리는 과정이 쉽지 않았다. 그래서 다른 사람의 도움을 받았음 1. 앞에 문자부터 하나씩 잘라가면서 만든 문자열로 앞, 끝 문자를 한 칸씩 땡기면서 비교 (전체 틀) 2. 비교하면서 문자가 다르면 다시 돌아와서 기존 문자열 크기에 +1 → 잘라버린 앞 문자를 문자열 맨 뒤에 붙여서 팰린드롬을 만.. 2023. 3. 31.
[백준 1205번 / JAVA / 구현] https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 태수의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보 www.acmicpc.net #문제 설명 태수가 즐겨하는 디제이맥스 게임은 각각의 노래마다 랭킹 리스트가 있다. 이것은 매번 게임할 때 마다 얻는 점수가 비오름차순으로 저장되어 있는 것이다. 이 랭킹 리스트의 등수는 보통 위에서부터 몇 번째 있는 점수인지로 결정한다. 하지만, 같은 점수가 있을 때는 그러한 점수의 등수 중에 가장 작은 등수가 된다. 예를 들어 랭킹 리스트가 100, 90, 90, .. 2022. 12. 21.

티스토리툴바