이것 저것 올리는 곳

https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 문제 처음으로 Union find알고리즘을 사용해 본 문제다. 문제에 테스트 케이스를 입력받는다 라는 말이 없어서 입력이 헷갈렸던 문제다. 질문 게시판을 보니 나와 같은 사람이 있었다. 문제는 각 테스트 케이스에서 유저 수 친구 관계 수 친구 관계 친구 관계 검사 수 친구 관계 검사 이렇게 입력을 받는다. a라는 유저가 b라는 유저를 친구 관계를 타고 타고 넘어가..

알고리즘 문제풀이 2024. 3. 2. 01:54

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 문제 백트래킹 문제다. 도시의 집과 치킨집의 위치가 주어 졌을때, 치킨집을 m개만 남겼을 경우 도시의 치킨 거리(집과 치킨집 거리가 최소가 되는 합)가 최소가 되는 값을 찾는 문제다. 나는 이 문제를 풀기 위해 우선 치킨집을 m개만 남기는 경우의 수를 찾았다. 각 치킨집의 좌표(x,y)를 하나의 리스트에 저장하고, 이걸 콤비네이션 연산 하면 된다. def make_combin..

알고리즘 문제풀이 2024. 2. 29. 01:07

문제 https://www.acmicpc.net/problem/20300 20300번: 서강근육맨 PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다. www.acmicpc.net PT 한 번에 두 가지 운동 기구를 사용할 수 있고, 각 운동 기구의 근손실 값이 주어진다. 이때, 모든 PT를 받았을 경우(모든 운동 기구를 사용했을 경우) 근손실을 최소로 하는 값을 출력하는 문제다. 처음 문제를 보고 이분 탐색 문젠가 싶었다가 유혹을 참지 못하고 알고리즘 분류를 봤다. 분류를 보니 그리디 문제였고 이를 보자마자 생각한 방법은 정렬된 각 운동기구의 근손실 배열을 앞, 뒤에서부터 중앙으로 인덱..

알고리즘 문제풀이 2024. 2. 22. 02:02

문제 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 처음 문제를 읽고 BFS로 풀면 될 것 같았다. 그래서 BFS로 구현을 시도해 봤는데 아무리 생각해도 연산량이 너무 많은 것 같아 불안했는데, 역시나 메모리 초과를 받았다. 그래서 문제 분류를 확인했는데, 그리디 문제였다. 이게 그리디?라는 의문을 가지고 연습장에 끄적끄적하다 보니 생각보단 빠르게 규칙을 찾을 수 있었다. 모든 값이 0으로 채워져 있는 길이가 N인 배열 A부터..

알고리즘 문제풀이 2024. 2. 9. 20:49

문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙산의 각 높이가 주어지고 매년 빙산기준으로 상하좌우에 있는 바다의 수만큼 빙산의 높이가 낮아진다. 그랬을 때, 하나의 빙산 덩어리가 2개 이상으로 나눠지는 년도를 찾는 문제다. 나는 이 문제를 BFS탐색을 두 번 써서 풀었다. 매년 녹는 빙산을 탐색하기 위해 한번, 빙산 덩어리가 몇개인지 탐색하기 위해 한번 이렇게 총 두 번 사용했다. 문제는 흔한 탐색 문제를 여러개 섞어둔 느낌 오답..

알고리즘 문제풀이 2024. 2. 4. 21:41

문제 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 에라토스테네스의 체로 소수 구하고 너비 우선 탐색으로 조건 만족할 때까지 모든 경우를 탐색했다. BFS는 참 유용한 것 같다. 문제는 소수인 시작 번호 4자리와 목표 번호 4자리가 주어진다. 시작 번호부터 한 자리씩 숫자를 바꿔가며 목표 번호를 만들어 가는 문제다. 단, 시작 번호에서 목표 번호까지 1자리씩 숫자를 바꿔 갈 때도 모두 소수로 바꿔가야 한다. 풀이 우선 10000크기의 리스트를 만들어 ..

알고리즘 문제풀이 2024. 1. 26. 00:43

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 이분 탐색 알고리즘 문제 풀어보는 중인데, 너무 헷갈리는 게 많은 알고리즘이다. 문제를 풀때 한번 만에 풀리는 경우가 거의 없는 것 같다. 조금씩 고치면서 때려 맞추는 느낌.. 깔끔하게 풀고 싶다. 문제는 각 일차에 필요한 금액이 주어지고, 인출 가능 횟수가 주어진다. 시중에 있는 돈이 각 일차에 필요한 금액보다 적을 경우에 다시 인출 가능하다. (여기서 시중에 있던 금액 + 인출 금액이 아닌, ..

알고리즘 문제풀이 2024. 1. 14. 23:51

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 문제는 빗물의 높이 마다 안전 영역의 개수가 달라질 때, 안전 영역의 개수가 가장 많은 경우의 안전 영역 개수를 출력하는 문제다. 문제에는 따로 설명 되어 있지 않지만 읽어보면 빗물의 높이는 0~100까지 가능한 것을 알 수 있다. (처음에 1~100까지로 설정했다가 70%에서 틀렸었다. => 문제 노트에 보면 물에 잠기지 않을 수도 있다고 되어 있다.) DFS로도 풀 수 있을 것 같은데, 나는 B..

알고리즘 문제풀이 2023. 12. 22. 20:06