본문 바로가기

알고리즘112

[백준 15649 / N과 M(1) / JAVA / 완전 탐색] https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 접근 입력한 N 숫자를 1부터 다 돌아가면서 중복없이 출력해야한다. 재귀 함수로 호출과 귀환을 반복하면서 모든 숫자를 탐색한다. 이해가 안되서 출력을 찍어가면서 했는데도 머리가 어지럽다. 이런 형태로 쓰인다라고 생각하고 필요하면 다시와서 봐야겠다. import java.util.*; import java.io.*; public class Main { static int N; // 여러 메서.. 2023. 4. 21.
[백준 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://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 접근 투 포인터? 두 개의 인덱스를 움직여가며 원하는 값을 탐색한다. right부터 한 칸씩 움직여서 k가 만들어지거나 k를 넘기전까지 right의 인덱스를 차곡차곡 더한다. k를 만들면 그 때의 left, right 인덱스를 저장 k를 넘어가면 left 인덱스의 값을 삭제하고 left를 한 칸씩 움직인다. 이렇게 left, right를 동시에 움직이며 부분 수열 합이 k인 부분을 탐색한다.. 2023. 4. 13.

티스토리툴바