Java/코딩테스트
-
백준 3055, 1600, 7576Java/코딩테스트 2023. 8. 30. 02:54
이번에 문제를 풀 때는 Pos class 따로 만들지 않고 배열로 만들어서도 풀어봤다. 스터디원들이 내 준 문제들이 어째 다 골드여서.. 열심히 풀었다는 tmi... 백준 3055 탈출 🦔 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 🦔 바보같이 S가 비버의 굴...인줄 알고 풀었다. 답이 계속 이상하길래 헤맸다...ㅋㅋ 🦔 물 먼저 퍼트리고, 그 다음 고슴도치를 이동시킨다. 원래 각각에 해당하는 temp 리스트를 만들까 했는데, 메모리가 옹졸하다. 그..
-
백준 2140, 28303, 2258Java/코딩테스트 2023. 8. 22. 16:17
백준 2140 지뢰찾기 💣 https://www.acmicpc.net/problem/2140 2140번: 지뢰찾기 지뢰찾기는 N×N에서 이뤄지는 게임이다. 보드의 곳곳에는 몇 개의 지뢰가 숨겨져 있고, 지뢰가 없는 칸에는 그 칸과 인접(상하좌우 및 대각선)해 있는 8개의 칸들에 몇 개의 지뢰가 숨겨져 있는 www.acmicpc.net 💣 테두리에 인접한 영역만 직접 계산하고, 나머지 가운데 영역들은 모두 지뢰가 있다고 가정해서 지뢰의 최대 개수를 계산한다. 💣 그리디, 구현 문제로 분류되어 있다. 아래 그림의 분홍 형광펜 영역 기준 8방향을 탐색하는 Around함수, 그리고 Around 결과 따라 count를 감소시킬지 / 주변 숫자를 1씩 감소시킬지를 결정한다. 💣 나머진 아래 그림 참고 💣 코드 im..
-
백준 2240Java/코딩테스트 2023. 8. 15. 17:27
https://www.acmicpc.net/problem/2240 2240번: 자두나무 자두는 자두를 좋아한다. 그래서 집에 자두나무를 심어두고, 여기서 열리는 자두를 먹고는 한다. 하지만 자두는 키가 작아서 자두를 따먹지는 못하고, 자두가 떨어질 때까지 기다린 다음에 떨어 www.acmicpc.net 다른 분들이 만들어두신 DP 문제집 뒤지다가 문제 이름보고 귀여워서 풀었다. 아직도 3차원 배열을 DP에 활용하는 건 익숙하지 않음을 깨닫게 된 문제이다.... 써야 하는 것까진 인지를 했는데 조건 분기 나누는게 아직도 어렵다. A4한페이지 가득 채워가며 풀다가 ,,, 그냥 몇 번 움직였었는지를 배열의 마지막 인자로 넣으면 되었음을 ... 구글링을 통해 알아냈다. ㅋㅋㅋㅋㅋ 처음엔 그냥 이전에 움직였는가 ..
-
백준 2293Java/코딩테스트 2023. 8. 15. 03:34
https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제에 들어가보면 알겠지만 시간과 메모리 제한이 매우 옹졸하다. 문제 조건만 봐도 ... 괜히 2차원 배열쓰거나 반복문 크게 돌리면 분명 초과가 날 것이다... 라고 말해주고 있다. 원래 동적계획법 문제는 점화식을 세워버릇 했는데 이건 진짜 모르겠었다. 처음엔 그냥 동전 종류중에 가장 큰 동전의 DP 값 + 나머지 이런 식으로 분할해서 합하는건가 했는데 단순히 그렇게 종이에 계산해봤는데 답이 안 맞..
-
백준 2206, 14442Java/코딩테스트 2023. 8. 13. 22:44
------------------------- 사담 ------------------------- 이 문제는 CS 스터디에서 스터디원분이 추천해준 문제이다. 왜 추천해줬었는지 기억은 안 나지만...추천해준 것만 기억하고 일단 풀었다... 벽 부수고 이동하기 문제가 시리즈로 3인가 4까지 있었던거 같은데 일단 2까지는 풀었다. 처음 2206을 풀고 이해했다면 14442는 변수만 살짝 바꿔서 쉽게 풀수 있을 것이다. https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이..
-
백준 2228Java/코딩테스트 2023. 8. 10. 03:23
https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되 www.acmicpc.net 생각의 흐름.. 1. 처음엔 DFS 방식으로 구간 시작위치를 조합해서 구하려 했었다. 근데 다 생각해보니 답이 다르길래 뭐지 했는데 각 구간 길이가 다를 수도 있었다. 그래서 뭔가 이방식으로 풀어나가기가 애매했다. 2. 구글링을 했는데 DP를 사용하는걸 확인을 했다. 3. 좀 다른 분들 코드를 보다가, DP[ i ][ j ] 를 배열의 첫 번째 원소에서 i 번째 원소까지 ..
-
백준 11000Java/코딩테스트 2023. 8. 8. 10:42
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘. 강의 시작 순서대로 담을 우선순위 큐 하나, 강의 끝나는 시간들만 담아둘 우선순위 큐 rooms하나 이렇게 정의했다. rooms에는 강의 끝나는 시간을 담아두고, rooms.peek(), 즉 가장 일찍 끝나는 강의실의 강의 종료 시점이 다음에 들어올 강의의 시작 시점보다 빠르거나 같은 경우에만 rooms.poll()을 수행하고, 새로 들어온 강의의 끝나는 시점을 다시 rooms에 넣으면 된다. 최종적으로 rooms의 사이즈가 ..
-
프로그래머스 구명보트, 조이스틱Java/코딩테스트 2023. 8. 7. 16:27
오래간만에 프로그래머스에서 문제를 풀었다. 아직도 감을 잘 못 잡고 있는(...) 그리디 문제 2문제 풀어본 내용 정리. 그리디가 시중에 판매되는 알고리즘 책들 보면 꽤 앞쪽에 나와있는데... 난 그리디를 왜이렇게 못하는...? 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 여기서 아무 생각이 없이 풀다가 놓쳤는데, 무조건 보트엔 2명밖에 못 탄다. 그러므로 가장 무거운 사람 + 가장 가벼운 사람 조합으로 가야 한다...이걸 생각..