본문 바로가기

CS

[Python] 백준 2902번: KMP는 왜 KMP일까?
[Python] 백준 2902번: KMP는 왜 KMP일까? https://www.acmicpc.net/problem/2902 [풀이]입력 받아서 하이픈으로 구분 후 가장 첫 번째 문자만 따서 약자를 구성한다. [코드]import sysinput = lambda: sys.stdin.readline().rstrip()s = input().split('-')print(''.join([i[0] for i in s])) [시간복잡도]O(1) CS/Algorithm 2025. 9. 3.
[Python] 백준 33675번: L-트로미노 타일링
[Python] 백준 33675번: L-트로미노 타일링 https://www.acmicpc.net/problem/33675 [풀이]타일의 세로 길이는 무조건 3가로 길이가 2의 배수여야 각각 2개의 방법씩 대입할 수 있다. 가로의 길이가 N이라면,짝수인 경우, 해당 방법은 2 * (N // 2)만큼 나올 수 있다.홀수인 경우, 0개이다. (빈 공간이 발생하기 때문) [코드]import sysinput = lambda: sys.stdin.readline().rstrip()result = []for _ in range(int(input())): n = int(input()) x = int(2 ** (n / 2)) if n % 2 == 0: result.append(str(x)) else: result.appe.. CS/Algorithm 2025. 8. 30.
[Python] 백준 30446번: 회문수
[Python] 백준 30446번: 회문수 https://www.acmicpc.net/problem/30446 [풀이]문제 조건은 다음과 같았다.실행시간 1초, 메모리 1024MB, N의 최대 크기 10^10 (100억) 단순히 1부터 100억 까지의 숫자를 반복문으로 계산해서 회문을 비교하게 되면, 100초가 걸릴 것이 뻔하다.(대략 1억에 1초로 친다.) 그럼 어떻게 해야하나.우선, 각 숫자 범위마다 회문의 조건을 만족하는 수의 개수를 구해보았다. 1 ~ 10 : (9개) 1, 2, 3, 4, 5, 6, 7, 8, 911~100 : (9개) 11, 22, 33, 44, 55, 66, 77, 88, 99101~1000 : (90개) 101, 111, 121, 131, 141, 151, 161, 171, 181, 191, ..., 9991001~.. CS/Algorithm 2025. 8. 26.
[Java] 백준 2852번: NBA 농구
[Java] 백준 2852번: NBA 농구 https://www.acmicpc.net/problem/2852 [풀이]미리 득점에 대한 정보를 data 변수에 넣어놨다.그리고 0초부터 2880초(48분)이 되기 전까지 1초씩 반복하면서 득점 상황을 보며 비교한다. 다만, data에 들어오는 시간이 시간 순으로 기록되어 있는 것이 보장되어 있기 때문에, 모든 data를 다 확인하는 것이 아니라, lastIndex값을 기록하여 해당 시간이 지났다면, 다음 index를 조회할 수 있도록 값을 저장시켜두었다. 추후, 시간조건이 매우 커진다면 득점 상황만을 가지고 더 효율적인 코드를 만들어야 할 것이다. [코드]import java.io.*;import java.util.*;public class Main { public static int .. CS/Algorithm 2025. 6. 28.
[Python/Java] 백준 14626번: ISBN
[Python/Java] 백준 14626번: ISBN https://www.acmicpc.net/problem/14626 [풀이]간단한 수학+구현 문제였다 홀수 번째의 경우(짝수 인덱스인 경우), 10의 배수인 몫으로 나눈 나머지에 대해 10에서 뺀 값이 *에 들어간 경우이고짝수 번째의 경우(홀수 인덱스인 경우), 임의로 들어갈 값에 대해 3배한 값과, 나머지 자릿수를 규칙을 적용한 합을 더해 나오는 결과에 대해 10으로 나누고 난 나머지가 0이 되는 경우를 구해주었다. [코드]- Pythonisbn = input()result = 0is_even = Falsefor i in range(13): if isbn[i] == '*': if i % 2 != 0: is_even = True continue .. CS/Algorithm 2025. 6. 7.
[Python] 백준 16395번: 파스칼의 삼각형
[Python] 백준 16395번: 파스칼의 삼각형 https://www.acmicpc.net/problem/16395 [풀이]기존 연산이 다음 연산에 영향을 미치기 때문에 DP로 풀이했다.우선 대각선 형태로 되어 있는 것을 N*N 형태의 배열로 만들었다. 또한, 초기값을 1로 만들고 나서 다음 연산할 부분만 2중 for문으로 만들어서 파스칼의 삼각형을 완성했다. [코드]n, k = map(int, input().split())dp = [[1] * (n + 1) for _ in range(n + 1)]for i in range(3, n + 1): for j in range(2, i): dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]print(dp[n][k]) [시간복잡도]O(N^2) CS/Algorithm 2025. 6. 2.
[Java] 백준 11293번: Password
[Java] 백준 11293번: Password https://www.acmicpc.net/problem/11293 [풀이]영어로 되어 있어서 그렇지, 알고 보면 쉬운 문제이다.일단 기본적으로, 문제 내에서 표기하는 모든 숫자는 1번 인덱스부터 시작한다. 그 다음,첫 번째 숫자는 몇 번째 암호와 비교할지두 번째 숫자는 해당 암호의 몇 번째 글자와 사용자의 첫 번째 글자와 비교할지세 번째 숫자는 해당 암호의 몇 번째 글자와 사용자의 두 번째 글자와 비교할지를 나타낸다. 특별히 신경쓴 점은, 암호를 입력받을 때 중간에 띄어쓰기가 없이 char 배열로 입력받아야 했기 때문에 replace 함수를 통해 공백을 제거한 후, toCharArray()를 통해 char 배열로 만들어주었다. 그리고 자바의 배열에서 0번 인덱스부터 시작하는 점과, 입력받을 때는 .. CS/Algorithm 2025. 5. 28.
[Python] 백준 17087번: 숨바꼭질 6
[Python] 백준 17087번: 숨바꼭질 6 https://www.acmicpc.net/problem/17087 [풀이]최대 공약수를 구하면 간단히 해결되는 문제이다. 테스트케이스 1번을 예시로 들면, 수빈의 위치는 3동생들의 위치는 각각 1, 7, 11이다. 수빈의 위치와 비교해서 상대적인 거리를 측정하기 위해서는 각 거리의 차에 대한 절댓 값이 필요하다.이를 계산하면 2, 4, 8이 된다. 해당하는 거리들을 서로 비교하여 최대 공약수를 구할 수 있다면, 이번 문제의 답을 얻을 수 있다.이는, 유클리드 호제법을 통해 결과를 얻을 수 있을 것이다. (https://wikidocs.net/205459) --- 기본적으로, a와 b에 대한 최대 공약수를 구하기 위해서는 a와 b 중 작은 숫자로 먼저 나누어 보고,숫자의 크기를 1씩 줄여나가면서 나.. CS/Algorithm 2025. 5. 27.
[Python] 백준 1964번: 오각형, 오각형, 오각형…
[Python] 백준 1964번: 오각형, 오각형, 오각형… https://www.acmicpc.net/problem/1964 [풀이]처음에는 이렇게 나누어 풀었었다.좌측 하단의 꼭짓점을 기준으로, 중앙의 점 1개그 외 꼭짓점으로부터 뻗어나가는 부분 4개에 대해 (n-1)개그리고 나머지 3개 부분에 대한 (n-1)!개의 꼭짓점을 합해서1 + 4n + 3 * (n - 1)! 개라고 식을 도출했었다. 하지만, 이렇게 하면 factorial을 사용해야 했기 때문에, 더 좋은 방식을 찾고자 했다.등차수열을 이용하는 것이다. 우선, 전체에 대해 각각의 오각형을 중복을 생각하지 않고 개수를 구한다면5 + 10 + 15 + 20 + ... 5 * n 개의 꼭짓점이 나올 것이고이것을 공식화 한다면 5 * (n * (n - 1)) / 2 라는 공식이 나온다.1, 2, 3.. CS/Algorithm 2025. 5. 27.
[Python] 백준 1932번: 정수 삼각형
[Python] 백준 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 [풀이]처음에는 완전탐색 기반의 DFS로 풀었다.하지만 정수 삼각형이 500 depth까지 들어가다 보니 중복 연산으로 인해 시간초과가 되었다. 이것을 해결하기 위해 DP 개념을 활용하였다.DP는 이미 진행한 연산에 대해 저장해두고, 기존 연산 결과를 다시 활용하는 기법이다. 예를 들어 1-2-1-1 이라는 경로와, 1-2-2-1 이라는 경로를 지나갈 때1-2 경로에 대해서는 해당 누적된 값에 대해 최댓값을 미리 구했다면, 여러 번 연산 할 필요 없이 기존 연산 결과를 활용하면 된다. 때문에, DP 테이블을 별도로 만들어 두어 기존 경로를 지나온 것에 대한 누적된 연산 결과를 그대로 활용할 수 있도록 코드를 변경하였다. [코드]n .. CS/Algorithm 2025. 5. 25.

티스토리툴바