자료구조&알고리즘
-
[알고리즘 문제 풀이][DP] 백준 9184번 - 신나는 함수 실행자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 12. 25. 18:59
반례가 많이 발생하는 문제였기에 기록 필요 - 문제 설명: https://www.acmicpc.net/problem/9184재귀함수 w(a,b,c) 를 재귀함수를 사용하지 않고, 아래에 조건에 맞게 출력되도록 구현하라는 문제입니다.if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a - 문제 풀이:재귀를 사용하지 않는다면 합을 계산하기 위해 DP 를 이용할 수 있습니다. a, b, c가 하나라도 20을 넘는 경우는 모두 w(20,20,20) 으로 같은 결과가 나오기 때문에, w(20,20,20) 의 결과값까지만 구현하면 됩니다.또한 a, b, c 중 하나라도 0 이하인 경우에는 답이 1이기 때문에 w(0,0,0) 부터의..
-
[알고리즘 문제 풀이][비트마스킹] 백준 23630번 - 가장 긴 부분 수열 구하기자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 11. 24. 15:48
풀이 참고 블로그: [Python] 23630번 가장 긴 부분 수열 구하기 - 문제 설명: 23630번: 가장 긴 부분 수열 구하기 N개의 자연수로 이루어진 수열 A = {A1, A2, ..., AN} 이 주어집니다.다음 조건을 만족하는 가장 긴 부분 수열을 찾아야합니다.(1) Ai1 & Ai2 & ... & Aim 이 0 이 아니어야 합니다. (선택한 수들끼리 AND 비트 연산을 했을 때 겹치는 비트가 1개 이상이 있어야합니다.)(2) 1 N 의 최대 크기는 1,000,000 이며, Ai 의 최대 수 또한 1,000,000입니다. - 문제 풀이:조건을 만족하는 가장 긴 부분 수열을 찾는다고 하면, 백트래킹을 먼저 생각해볼 수 있습니다.하지만, N이 1,000,000 이기 때문에 이 크기의 수열을 ..
-
[알고리즘 문제 풀이][Union-Find] 백준 13383번 - Oil자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 8. 28. 00:45
한붓 그리기 + Union Find 문제 백준 13383 Oil 문제의 풀이 방법을 정리한 내용입니다.저는 문제를 파악하는데 시간이 걸렸어서 다른 분들을 위해 풀고 나서 정리해두었습니다. 도움이 되길 바랍니다. - 문제 설명: 13383번: Oil (acmicpc.net) 최대 100개의 집이 주어집니다.각 집 사이에 z 개만큼의 기름 자국이 남아있습니다.기름 자국이 남았다는 것은 두 집 사이를 한 번 지나갔다는 것을 의미합니다.문제에서 주어진 기름 자국들을 보고 Mike 씨 한 명이 다 지나다닌 것이 맞는지 맞추는 문제입니다. - 문제 풀이:Mike 한 명이 모든 집을 왔다갔다 하려면 한붓 그리기 문제처럼 풀 수 있을 것입니다.또한 왔다갔다한 집들을 합쳐줘야하기 때문에 Union-Find 도 필요합니다..
-
[알고리즘 문제 풀이][수학] 백준 23364번 - Almost Always자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 7. 15. 00:22
백준 23364 Almost Always 문제의 풀이 방법을 정리한 내용입니다. - 문제 설명: https://www.acmicpc.net/problem/23364 1부터 2*10^9 까지 범위의 숫자를 5*10^5 개 뽑습니다. 문제에서 주어지는 n 은 항상 5*10^5로 고정입니다.이때 n 개의 숫자 중에 한 숫자가 다른 숫자로 나누어 떨어지면 두 숫자의 위치를 답하는 문제입니다. (나누는 수 먼저, 나누어지는 수 나중) 예제 입력 1을 보면104 9 8 10 5 28 3 62 9 17 이 주어집니다.이 중, 10 을 5로 나눌 수 있으므로 5와 4를 응답합니다.(예제이기 때문에 n = 10 으로 주어집니다) - 문제 풀이:이 문제는 Birthday Problem (생일 문제) 를 활용하는 문제입니..
-
백준 2545 팬케익 먹기 증명 (라그랑주 승수법)자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 4. 4. 23:06
수학 무지렁이의 증명 노트 2024.04.14 1) 문제 백준 2545번 팬케익 먹기 문제 https://www.acmicpc.net/problem/2545 2545번: 팬케익 먹기 두 번째 테스트 케이스를 보자. 왜 정답이 64일까? 가장 먼저 4 * 5 변에 맞춰서 2번 팬케익을 자르면 남은 팬케익은 4*5*4가 된다. 그 다음에 4 * 4 변에 맞추어 팬케익을 자르면 4*4*4가 된다. 따라서 6 www.acmicpc.net 박스 모양의 팬케익의 가로 세로 높이가 각각 A cm, B cm, C cm 일 때 D번 자르고 남은 부피를 최대화 하는 방법 A, B, C 를 각각 어떻게 값을 줄여야 A*B*C 가 최대가 되는지 찾는 문제 요약하면, x+y+z = c 로 일정할 때 x*y*z 를 최대화하기 (..
-
Python 출력시 앞에 0 채우는 방법자료구조&알고리즘/알고리즘 - 언어 기초 2024. 2. 2. 16:28
문제를 풀 때마다 매번 까먹고 다시 찾아보는 정해진 자릿수만큼 출력하는 방법 ex) 0003 과 같이 항상 4자리로 출력하고 싶을 때 앞에 0 을 채우는 방법 숫자를 출력하는 경우가 가장 많은데, 숫자는 아래 방법으로 사용하면 된다. 1. 숫자 앞에 0 붙이는 방법 print(f"{1:04d}") >>> 0001 python 3.6 이상 사용 가능한 f-string 방식으로 이와 같이 간단하게 쓸 수 있다. f"{출력할숫자:0전체자릿수d}" 순서대로이다. 혹은 이전 버전이라면 아래의 방식을 사용해도 된다. 출력할 숫자가 number 의 자리에 들어가고, '0전체자릿수' 혹은 '{0:0전체자릿수d}' 형식이다. number = 1 a = format(number, '02') b = '{0:04d}'.for..
-
[알고리즘 문제 풀이][그리디] 백준 3211번 - kino자료구조&알고리즘/알고리즘 - 대회 알고리즘 2024. 2. 1. 16:25
백준 3211 kino 문제의 풀이 방법을 정리한 내용입니다. - 문제 설명: https://www.acmicpc.net/problem/3211 3211번: kino In the first row there is an integer N, 2 ≤ N ≤ 10 000, number of friends. In the next N rows there is one integer per row Zi, 1 ≤ Zi < N. That numbers represent requests of all Mirko’s friends, that is, minimal number of people they are willing to www.acmicpc.net 미르코 (Mirko) 는 친구들을 영화관에 데려가려고 합니다. 각 친구들..
-
[알고리즘 문제 풀이][기하학] 백준 16483번 - 접시 안의 원자료구조&알고리즘/알고리즘 - 대회 알고리즘 2023. 2. 11. 19:16
백준 16483 접시 안의 원 문제를 푼 방법을 개인적으로 정리한 내용입니다. - 문제 설명: https://www.acmicpc.net/problem/16483 - 문제 풀이: 문제에 따라 안쪽에 있는 원의 접선을 그리면 아래와 같습니다. 그리고 문제에서 접선과 바깥 원이 만나서 생기는 두 점 사이 거리를 T 로 준다고 하였으니 T 도 함께 표현하면 아래와 같습니다. 원의 테두리는 반지름들이 모여 이루어진 것이기 때문에 접선이 지나는 점 또한 중심으로부터 거리가 반지름과 같을 수밖에 없습니다. 따라서 바깥 원의 반지름인 a 와 안쪽 원의 반지름인 b 를 표현하면 아래와 같습니다. 원의 중심으로부터 접선까지 선을 그으면 직교하기 때문에 피타고라스 정리에 따라 a^2 - b^2 = (T/2) ^ 2 이 됩..