programming/알고리즘32 [백준, 1113, 자바] 수영장 만들기 https://www.acmicpc.net/problem/1113 1113번: 수영장 만들기 지민이는 수영장을 만들려고 한다. 수영장을 만들 곳의 크기는 N*M이고, 각 칸은 직육면체이다. 따라서, 각 칸의 직육면체의 높이가 쓰여 있는 다음과 같은 땅을 생각할 수 있다. 16661 61116 16661 이 www.acmicpc.net 1. 문제 핵심 물은 항상 높이가 더 낮은 곳으로만 흐르고, 직유면제 취의 표면에는 물이 없다. 땅의 높이는 0이고, 땅은 물을 무한대로 흡수할 수 있다. 2. 문제 접근 접근법 1. 한 노드부터 BFS로 주변 노드를 검사. 해당 노드의 높이보다 낮은 노드가 있으면 수영장이 될 수 없다고 판단. 가장자리와 맞닿아있으면 물이 새기 때문에 수영장 불가 판단. visit 배열로 .. 2022. 8. 4. [백준, 18500, 자바] 미네랄2 문제 링크 : https://www.acmicpc.net/problem/18500 18500번: 미네랄 2 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 1. 문제 핵심 막대기로 인해 분리되는 클러스터는 막대기 당 최대 1개밖에 없습니다. 분리된 클러스터는 낙하하며 다른 미네랄이나 바닥에 부딪히기 전까지 멈추지 않습니다. 왼쪽에 던졌을 때는 클러스터가 [상, 우, 하] 로 발생할 수 있고 오른쪽에서 던졌을 때는 클러스터가 [상, 좌, 하] 로 발생할 수 있습니다. 2. 문제 접근 막대기를 던집니다. 막대기가 미네랄을 만나면 해당 미네랄을 파.. 2022. 7. 25. [백준, 1027, 자바] 고층 건물 https://www.acmicpc.net/problem/1027 1027번: 고층 건물 세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작) www.acmicpc.net 1. 문제 핵심 빌딩의 수는 최대 50개. 빌딩의 높이는 최대 10억보다 작거나 같은 수 2. 문제 접근 총 빌딩의 수가 50개밖에 되지 않아 완탐으로 한 빌딩과 그 외 나머지 빌딩을 모두 비교하면서 진행해도 괜찮다고 생각했습니다. [현재] 빌딩과 [비교] 빌딩 바닥 사이의 거리 / A빌딩과 B빌딩 꼭지점 사이의 거리 == 기울기 값을 구할 수 있다. 기준 빌딩 왼쪽, 오른쪽 각각 진행하며 각 기.. 2022. 7. 25. [백준, 23791, 자바] K번째 음식 찾기 1 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1 한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면 www.acmicpc.net 1. 문제 핵심 두 종류의 음식이 존재하기 때문에 두 번의 이분 탐색이 필요 한식과 양식 모두 첫번째부터 i, j 번째까지 범위가 존재 2. 문제 접근 이분탐색의 기준으로 특정 한식 배열 중 하나의 값을 사용했다. 그리고 해당 값보다 작은 양식의 개수를 조사해서 한식과 양식이 몇 번째인지 확인하고 두 음식의 번호를 더했을 때 k가 되는지 확인한다... 2022. 7. 7. [백준, 17780, 자바] 새로운 게임 https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 1. 문제 핵심 흰색, 파란색, 빨간색 자리 별로 이동이 다르다. 외곽은 파란색과 동일한 타일 취급한다. 최대 1000번까지 루프를 반복하며 그 이상은 -1을 출력한다. 2. 문제 접근 말의 자리와 쌓여있는 높이를 수월히 계산하기 위해서 보드와 해당 보드 칸에 쌓여있는 말의 번호를 저장하는 3차원 배열이 존재하고 각 말들이 어느 행, 열의 칸에 몇 번째 레벨에 쌓여있는지 저장하는 2차원 배열로 관.. 2022. 7. 7. [프로그래머스, 자바] 여행경로 1. 문제 핵심 항공표는 왕복이 아닌 편도행 티켓 시작 공항과 도착 공항이 같은 티켓이 여러 장 존재할 수 있다. 2. 문제 접근 Arrays.sort와 hashmap을 활용하여 순서를 정렬한 뒤, 해당 순서로 출발 공항, 도착 공항을 정리한 표를 생성한다. 해당 표에서 ICN 공항을 시작으로 모든 항공표를 사용하는 경우의 수를 구하면 된다. 자바코드 더보기 package _0629_ChungLee; import java.io.*; import java.util.*; public class PG_여행경로 { static class Reader { int bfs = 1 2022. 6. 30. [프로그래머스, 자바] 징검다리 1. 문제 핵심 이진탐색의 대상은 바위 사이의 최소 중 최대 거리값 0과 최대 거리 위치에도 돌이 놓여져있고 이 돌은 제거 불가 제거해야 할 돌의 개수 n이 주어졌을 때 n보다 적은 수의 돌을 제거해도 조건을 만족하면 정답 2. 문제 접근 이분탐색 문제를 몇 문제 풀어보면서 감을 잡지 않았나 생각했는데 최소최대값을 정하는 것부터 그것을 각 바위들 사이를 돌면서 검사하고 몇 개의 돌을 제거하면 되는지를 시작부터 감을 잡지 못했다. 자바코드 더보기 package _0629_ChungLee; import java.util.*; import java.io.*; public class PG_징검다리 { static class Reader { int bfs = 1 2022. 6. 30. [백준, 3954, 자바] Brainf**k 인터프리터 문제 링크 : https://www.acmicpc.net/problem/3954 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 1. 문제 핵심 명령어는 최대 5천만번 이상 수행된 뒤, 항상 종료되거나 무한 루프에 빠진다. 여러 종류의 연산을 수행하고 연상이 종료되는지, 무한 루프에 빠지는지 검사한다. 2. 문제 접근 명령어를 수행하고 5천만번 이전에 끝나면 terminates를 출력 명령어가 5천만번이 수행되었다면 1. 모든 명령어가 수행되었다면 terminates를 출력.. 2022. 6. 22. [백준, 1799, 자바] 비숍 문제 : https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 1. 문제 핵심 1. 비숍은 대각선으로만 움직일 수 있다. 2. 체스판 가로, 세로는 열 개 이하의 칸을 가진다. 3. ↓ 핵심 더보기 흰 색 칸에 속하는 비숍은 검은 색 칸의 비숍에게 간섭을 못하고, 검은 색 칸의 비숍은 흰 색 칸의 비숍에게 간섭하지 못한다. (중요) 2. 문제 접근 1. 백트래킹으로 비숍을 놓을 수 있는 각 칸마다 해당 칸의 좌상 대각선, 우상 대각선에 다른 비숍이 있는지 확.. 2022. 6. 21. 백준 1644 소수의 연속합 [자바] 문제 링크 : https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 접근 : 1. 목적수 이하까지의 모든 소수를 구한 다음 슬라이딩 윈도우를 사용해서 크기를 조정해가며 해당하는 값들을 구한다. 2. 1은 소수가 아니다. 팁 : 작은 소수를 구했다면 그 소수를 목적수까지 2,3,4,~ N배를 해주며 예외처리를 해준다. 그러면 자연스레 남은 모든 수들은 소수가 되기 때문에 소수 검출에 시간을 대폭 줄일 수 있다. (i.e. : 에라토스테네스의 체) 더보기 코드 보기 package _0606.ChungLee; import java.io.DataInputStream; i.. 2022. 6. 6. 이전 1 2 3 4 다음
