백준 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라는 새로운..
백준 11726 - 2 x n 타일링 (파이썬)
백준 11726 - 2 x n 타일링 (파이썬)
2025.02.21분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/11726풀이점화식을 새워야 한다. 일단 An : 2 * n 타일을 1 * 2, 2 * 1 타일로 채우는 경우의 수를 생각해야한다.An = A(n - 1) + A(n - 2) 라는 점화식을 세울 수 있다.즉 이 문제를 생각해 보면, 숫자가 너무 커지기 때문에 일단 10007로 나눈다는 조건을 생각해야한다.먼저 dp 배열에 들어갈 초기 값을 생각한다.1번의 dp는 2 * 1 타일에 들어 갈수 있는 타일은 1개이다.2번의 dp는 2 * 2 타일에 들어 갈 수 있는 타일은 총 2개이다.1 * 2 타일 2개인 방법 1개2 * 1 타일 2개인 방법 1개예시를 생각해보자, 2 * 5 크기의 직사각형을 채운 한 가지 방법의 예를 확인..
백준 1759 - 암호 만들기 (파이썬)
백준 1759 - 암호 만들기 (파이썬)
2025.02.21https://www.acmicpc.net/problem/1759문제암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다.새 보안 시스템에서 조교들이 암호로 사용했을 법한 문자의 종류는 C가지가 있다고 한다. 이 알파벳을 입수한 민식, 영식 형제는 조교들의 방에 침투하기 위해 암호를 추측해 보려고 한다. C개의 문자들이 모두 주어졌을 때, 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오.바로 어제 최백..
[프로그래머스] 행렬의 합
[프로그래머스] 행렬의 합
2020.10.12def solution(arr1, arr2): result = [] temp = [] for i in range(len(arr1)): for j in range(len(arr1[i])): temp.append(arr1[i][j] + arr2[i][j]) result.append(temp) temp = [] return result for문에서 사실 애먹었다;; for i in range(len(arr1)): #arr1의 요소 2개 (2번 돈다.) for j in range(len(arr1[i)) # arr1의 요소 안의 요소 temp.append(arr1[i][j] + arr2[i][j] result.append(temp) temp = []#요소를 묶기 위해
[프로그래머스] 두 개 뽑아서 더하기
[프로그래머스] 두 개 뽑아서 더하기
2020.10.12def solution(numbers): numbers = sorted(numbers) result = [] for i in range(len(numbers)): for j in range(i + 1, len(numbers)): result.append(numbers[i] + numbers[j]) print(result) result = set(result) print(result) result = list(result) return (result) 처음 시도는 result를 list로 놓고, 5번을 도는 동안, i+1에서는 i값과 j값을 동시에 추가한다. 하지만 이 방법은 실패로 돌아갔고, set을 미리 지정해 주어야한다. def solution(numbers): numbers = sorted(numb..
[프로그래머스] 이상한 문자 만들기
[프로그래머스] 이상한 문자 만들기
2020.10.12def solution(s): s = s.split() temp = [] for i in s: idx = 0 for j in i: if idx % 2 == 0: temp.append(j.upper()) print(idx, j.upper()) else : temp.append(j.lower()) idx += 1 temp.append(" ") temp.pop() print(temp) print("".join(temp)) idx를 사용해서, idx의 위치에 맞는 문자를 대소문자로 변경해준다.
[프로그래머스] 정수 제곱근 판별
[프로그래머스] 정수 제곱근 판별
2020.10.11def solution(n): import math num = math.sqrt(n) if math.sqrt(n) == int(math.sqrt(n)) : #정수값이 나온다 => 제곱근의 존재 return pow(num+1, 2) #num+1 * num+1 return -1
[프로그래머스] 자연수 뒤집어 배열로 만들기
[프로그래머스] 자연수 뒤집어 배열로 만들기
2020.10.11def solution(n): return list(map(int, reversed(str(n)))) map에 대해서 자세히 공부하자
[프로그래머스] 정수 내림파순으로 배치하기
[프로그래머스] 정수 내림파순으로 배치하기
2020.10.11def solution(n): print(n) a = list(str(n)) # a라는 변수를 지정해, n의 값들을 list형태로 저장 print(a) # ['1', '1', '8', '3', '7', '2'] intList = list(map(int, a)) #intList라는 리스트를 지정해, str형태의 원소를 int형태로 지정 print(intList) #[1, 1, 8, 3, 7, 2] intList.sort(reverse=True) print(intList) #[8, 7, 3, 2, 1, 1] a = ''.join(map(str,intList)) #join을 사용하기 위해서는 다시 str형태로 지정해야한다. return int(a)
[프로그래머스] 시저 암호
[프로그래머스] 시저 암호
2020.10.11def solution(s, n): answer = [] for i in s: if i.isalpha(): if( 65 122: result = ord(i) + n - 26 answer.append(chr(result)) else : result = ord(i) + n answer.append(chr(result)) else: answer.append(' ') print(answer) return ''.join(answer)
[프로그래머스] 소수 찾기
[프로그래머스] 소수 찾기
2020.10.10def solution(n): count = 0 for i in range(1, n+1): temp_cnt = 0 for j in range(1,i+1): if i % j ==0: temp_cnt +=1 if temp_cnt == 2: count += 1 return count
[프로그래머스] K번째수
[프로그래머스] K번째수
2020.10.10def solution(array, commands): result = [] for i in commands: print(i) i_i = i[0] j_j = i[1] k_k = i[2] temp = array[int(i_i)-1:int(j_j)] temp = sorted(temp) result.append(temp[k_k-1]) return result 그냥 슬라이싱을 이용하는 문제이다. def solution(array, commands): return list(map(lambda x:sorted(array[x[0]-1:x[1]])[x[2]-1], commands)) 이렇게도 할수 있다...
[프로그래머스] 약수의 합
[프로그래머스] 약수의 합
2020.10.10def solution(n): result = 0 for i in range(1, n+1): if n % i == 0: result += i return result 약수를 result 에 계속 더한다.