백준 20922 - 겹치는 건 싫어 (파이썬)
백준 20922 - 겹치는 건 싫어 (파이썬)
2025.02.27https://www.acmicpc.net/problem/20922풀이진짜 단순히 배열에서 K개 이상의 dic을 만들어서 종료하는 구문으로 풀어볼까 했는데, 어림도 없지 당연히 틀렸다.import sysinput = sys.stdin.readlineN, K = map(int, input().split())arr = list(map(int, input().split()))dic = {}answer = 0for i in arr : if i in dic : dic[i] += 1 else : dic[i] = 1 if dic[i] > K : break else : answer += 1문제를 이해하면 다음과 같다. 주어진 정수 배열 A에..
백준 14502 - 연구소 (파이썬)
백준 14502 - 연구소 (파이썬)
2025.02.26https://www.acmicpc.net/problem/14502풀이이 문제는 BFS와 완전 탐색을 조합하여 해결하는 문제이다.문제에서는 연구소에서 벽을 3개 세우는 모든 경우의 수를 고려하고, 이후 바이러스가 퍼지는 과정을 BFS로 시뮬레이션하여 안전 영역의 최대 크기를 구하는 방식으로 해결한다.사용한 해결 전략은 다음과 같다.연구소에서 빈칸 (0)의 좌표를 찾는다.빈칸 중 3곳을 선택하여 벽을 세운다. (여기서 필자는 combinations()를 통해 조합을 구함)BFS를 이용해서 바이러스를 퍼뜨린다.바이러스가 퍼진 후 남은 안전 영역(0)을 계산한다.벽을 세우기 전 상태로 되돌린다. (백트래킹)가장 큰 안전 영역 값을 저장하여 출력한다.cells = [(i, j) for i in range(N) ..
백준 6064 - 카잉 달력 (파이썬)
백준 6064 - 카잉 달력 (파이썬)
2025.02.25풀이이 문제는 브루트포스 방법을 이용해 특정 해가 몇 번쨰 해인지 구하는 문제이다.단순히 모든 연도를 하나씩 증가시키며 탐색하면 시간 복잡도가 O(M * N)으로 너무 커지기 때문에 시간 초과가 일어 날 수 있다.found = Falsefirst = yfound = False: x:y에 해당하는 해를 찾았는지 여부를 저장하는 변수first = y: y를 기준으로 탐색을 시작for i in range(M): if first == x: print(y + i * N) found = True breakfirst 값을 N씩 증가시키면서 x와 같은 값을 찾기만약 first == x가 되는 순간, 해당 연도가 답이므로 출력 후 종료first += Nif first > N: ..
백준 9342 - 염색체 (파이썬)
백준 9342 - 염색체 (파이썬)
2025.02.25분류 : 문자열 + 정규 표현식https://www.acmicpc.net/problem/9342풀이먼저 T를 입력받아 테스트 케이스 개수를 정함T만큼 반복하면서 문자열 S를 입력받음기본적으로 문자열 S의 길이가 3미만이면 패턴을 만족할수 없으므로 “Good”을 출력하고 다음 반복으로 넘어감첫문자가 “A”가 아니라면 “A”, “B”, “C”, “D”, “E”, “F”에 속하는지 확인만약 속하지 않는다면 “Good”을 출력하고 다음 반복으로 넘어감만약 속한다면 이를 제거하고 진행한다.마지막 문자를 먼저 확인해 “C”가 아니라면 “A”, “B”, “C”, “D”, “E”, “F”에 속하는지 확인속하지 않는다면 “Good”을 출력하고 다음 반복으로 넘어감만약 속한다면 이를 제거하고 진행한다.여기서 T라는 새로운..
백준 2015 - 수들의 합 4 (파이썬)
백준 2015 - 수들의 합 4 (파이썬)
2025.02.24분류 : 누적합링크 : https://www.acmicpc.net/problem/2015풀이부분합을 활용하여 특정 구간 합이 K가 되는 경우의 수를 찾는 문제이다.단순한 방법으로는 O(N^2) 시간 복잡도로 모든 구간을 확인 할 수 있지만, 주어진 N의 최대값이 200,000 이므로, 이는 비효율적인 방법이다.따라서, 누적합과 해시맵을 활용하여 O(N)으로 해결해야한다.psum = [0] * Npsum[0] = A[0]for i in range(1, N) : psum[i] = psum[i - 1] + A[i]psum[i] 는 A[0] 부터 A[i] 까지의 합을 저장하는 누적합 배열이다.psum[i] = psum[i - 1] + A[i]를 이용하여 이전 누적합에 현재 값을 다하는 방식으로 누적합을 구..
백준 20365 - 블로그2 (파이썬)
백준 20365 - 블로그2 (파이썬)
2025.02.24https://www.acmicpc.net/problem/20365분류 : 그리디https://www.acmicpc.net/problem/20365풀이이 문제는 그리디 알고리즘을 활용하여 최소한의 작업 횟수로 문제들을 원하는 색상으로 칠하는 방법을 찾는것이다.주어진 문자열 S에서 연속된 같은 색상의 블록을 그룹화 하여 최소한의 횟수로 전체를 칠 할 수 있도록 해야한다.8BBRBRBBR예시로 위와 같은 예제가 있다면 색상을 그룹화 하면 다음과 같다.BB | R | B | R | BB | R즉, B 그룹: 3개, R 그룹: 3개이 경우, 한쪽 색상만을 먼저 칠하고, 나머지를 한 번에 칠하는 것이 최소 작업 횟수를 보장한다.문제 풀이의 주요한 알고리즘연속된 같은 색상을 하나의 그룹으로 압축압축된 그룹에서 B ..
백준 1759 - 암호 만들기 (파이썬)
백준 1759 - 암호 만들기 (파이썬)
2025.02.21https://www.acmicpc.net/problem/1759문제암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.바로 어제 최백..
백준 2579 - 계단 오르기 (파이썬)
백준 2579 - 계단 오르기 (파이썬)
2025.02.03https://www.acmicpc.net/problem/2579전형적인 DP 문제이다..이 문제의 조건은 다음과 같다.1. 연속된 3개 계단을 모두 밟으면 안된다.2. 마지막 도착 계단은 반드시 밟아야한다.3. 계단은 한번에 한 계단 또는 두 계단씩 오를 수 있다.위 그림의 예제에서는 6개의 계단이 주어진다.S = 10, 20, 15, 25, 10, 201. 마지막 층인 20은 무조건 밟아햔다. 그럼 10을 밟게 되면 25는 못 밟으니까, 10을 버리고 25를 밟는게 최적2. 15를 밟게 되면 10, 20을 못밟으니까, 15를 버리고, 10, 20을 밟는게 이득3. 총 4개를 밟는 것이 최선, 총 75의 값을 가지게 된다.수열로써 값을 나타내면 다음과 같다.1. aN은 N번째, 최대 점수 (바로 전 ..
백준 11725 - 트리의 부모 찾기
백준 11725 - 트리의 부모 찾기
2025.02.01https://www.acmicpc.net/problem/11725 먼저 예제 1번을 바탕으로 문제를 이해하면, 71 66 33 54 12 44 7 (그리면서 풀면 더 쉽다..)2번 노드 -> 4번3번 노드 -> 6번4번 노드 -> 1번5번 노드 -> 3번6번 노드 -> 1번7번 노드 -> 4번1번부터 N번까지의 노드가 있다. 입력받은 인접한 두 노드를 트리로 완성하고, 각 노드의 부모가 누구인지 확인하는 문제이다.import syssys.setrecursionlimit(10**6)# input = sys.stdin.readline()N = int(input())adj = [[] for _ in range(N)] # 인접리스트for i in range(N - 1) : a, b = list(map(i..
[백준] 4673 - 셀프 넘버 (파이썬 / C++)
[백준] 4673 - 셀프 넘버 (파이썬 / C++)
2020.04.09general = set(range(1, 10001)) change = set() for i in range(1, 10001): for j in str(i): i += int(j) change.add(i) result = general - change for i in sorted(result): print(i) #include using namespace std; bool selfnum[10001]; int main(void) { memset(selfnum, true, sizeof(selfnum)); for(int i=1; i
[백준] 15596 - 정수 N개의 합 (파이썬)
[백준] 15596 - 정수 N개의 합 (파이썬)
2020.04.09def solve(a): ans = 0 for i in a: ans += i return ans
[백준] 4344 - 평균은 넘겠지 (파이썬) (C)
[백준] 4344 - 평균은 넘겠지 (파이썬) (C)
2020.04.09import sys input = sys.stdin.readline N = int(input()) for i in range(N): list_temp = list(map(int, input().split(' '))) average = sum(list_temp[1:]) / list_temp[0] count = 0 for j in list_temp[1:]: if j > average: count += 1 print(str('%.3f' % round(count / list_temp[0] * 100, 3)) + '%') #include int main() { int num; float sum=0; float count=0; int stu_num; int score[1000]; scanf("%d", &num); ..
[백준] 8958 - OX퀴즈 (파이썬) (C++)
[백준] 8958 - OX퀴즈 (파이썬) (C++)
2020.04.09N = int(input()) for i in range(N): score = 0 cnt = 0 result = input() for j in range(len(result)): if result[j] == 'O': cnt += 1 score += cnt elif result[j] == 'X': score += 0 cnt = 0 print(score) #include #include using namespace std; int main() { int num; cin >> num; int *save_total = new int[num]; for (int i = 0; i > answer; for..
[백준] 1546 - 평균 (파이썬)
[백준] 1546 - 평균 (파이썬)
2020.04.08N = int(input()) score = list(map(int, input().split())) modify = [] for i in score: modify.append(i/max(score) * 100) print("%0.2f" % (sum(modify) / N)) 먼저 N에 과목의 개수를 입력받는다. 그후 list와 map, split을 통해서 과목의 점수를 score 리스트에 담는다. 그후 조작하고 나서 저장할 변수은 modify를 선언한다. 그후 score에서 값을 하나씩 꺼내와서 score의 가장 높은 점수로 나눠주고, 100을 곱해주고 modify 변수에 저장한다. 그후 마지막에 모든 modify 값들을 더하고 과목의 개수로 나눠주면, 조작된 평균을 구할 수 있다.
[백준] 3052 - 나머지 (파이썬)
[백준] 3052 - 나머지 (파이썬)
2020.04.08num_list = [] for i in range(10): temp = int(input()) num_list.append(temp % 42) num_list = set(num_list) print(len(num_list)) 먼저 num_list의 배열을 선언하고, 10개의 수를 입력받는다. 수를 입력 받음과 동시에 주어진 조건인 42로 나눠주고, 나머지를 num_list에 저장한다. 그 후 set 함수를 통해서 중복 값을 제거해주고, 리스트의 개수를 출력한다.