CS/Algorithm 문제
[BaekJoon] 백준 14500번 테트로미노
[BaekJoon] 백준 14500번 테트로미노 🎈문제 https://www.acmicpc.net/problem/14500 💬설명 어려운 문제는 아니었는데 어떻게든 bfs로 풀어보려고 하다가 오래 걸렸다. 결국 bfs로 못품.. bfs로 푸는 경우 ㅁ 모양의 테트로미노를 처리할 수 없어서 visit 여부를 체크하지 말아야 하는데 그 경우 시간 초과가 난다. 그럼 visit 배열을 다시 추가해야 하고 그럼 ㅁ 모양을 처리할 수 없고,, 무한 반복,,ㅠㅠ 결국 dfs -> 백트래킹으로 풀었더니 5분만에 풀었다. 포인트 dfs -> 백트래킹으로 하나씩 들어가면서 풀어줌 4개가 완성되면 max_value 업데이트 ㅓ, ㅏ, ㅗ, ㅜ 모양의 경우 dfs로 처리할 수 없어 예외로 따로 코드를 짜줌 👩💻코드 # B..
[BaekJoon] 백준 14499번 주사위 굴리기
[BaekJoon] 백준 14499번 주사위 굴리기 🎈문제 https://www.acmicpc.net/problem/14499 💬설명 전형적인 삼성의 구현문제 주사위를 굴리는 걸 구현해야 해서 초반에 고민이 필요했다. 푸는건 금방 풀었다. dice 배열과 dice_num 딕셔너리로 주사위의 위치와 방향을 표현해줬다. 👩💻코드 # BaekJoon14499.py N, M, x, y, k = map(int, input().split()) board = [[] for _ in range(N)] for i in range(N): board[i] = list(map(int, input().split())) operations = list(map(int, input().split())) dice = [i for i..
[BaekJoon] 백준 17779번 게리맨더링 2
[BaekJoon] 백준 17779번 게리맨더링 2 🎈문제 https://www.acmicpc.net/problem/17779 💬설명 삼성 기출이라 시간재고 풀었더니 1시간 30분정도 걸렸다. 구현문제라 어렵진 않았는데 5번 구역을 구하는 부분에서 꽤 애먹었다. 더 깔끔하게 구할 수 있을 것 같은데.. 문제에서 주어지는 구역들의 범위 ..
[Programmers] 카펫
[Programmers] 카펫 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42842 💬설명 근의 공식으로 풀 수 있었던 문제 변을 각각 x, y라고 하면 x + y = (brown + 4) / 2, xy = yellow + brown 이 된다. yellow와 brown을 알고 있으니 x, y를 변수로 둬서 근의 공식으로 풀면된다. 👩💻코드 def solution(brown, yellow): a = (brown + 4) / 2 b = yellow + brown x = (a + (a ** 2 - 4 * b) ** (1/2)) / 2 y = (a - (a ** 2 - 4 * b) ** (1/2)) / 2 return sorted([x, y], rever..
[Programmers] 소수 찾기
[Programmers] 소수 찾기 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42839 💬설명 어려운 문제는 아니었지만 알고리즘 문제에서 자주 나오는 소수찾는 로직을 구현해볼 수 있는 문제였다. 과정: 만들 수 있는 모든 순열을 구해서 각각의 숫자가 소수인지 판별 👩💻코드 import math from itertools import permutations def is_prime(number): if number == 0 or number == 1: return False for i in range(2, int(math.sqrt(number)) + 1): if number % i == 0: return False return True def sol..
[Programmers] 모의고사
[Programmers] 모의고사 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42840 💬설명 데이터 크기도 크지 않고 학생 수도 3명으로 정해져 있었기 때문에 약간의 하드코딩을 가미해서(?) 완탐으로 풀었다. 👩💻코드 def solution(answers): answer = [] answer_n = len(answers) correct1 = 0 select1 = [1, 2, 3, 4, 5] correct2 = 0 select2 = [2, 1, 2, 3, 2, 4, 2, 5] correct3 = 0 select3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] for i in range(answer_n): if select1[i % 5]..
[BaekJoon] 백준 21608번 상어 초등학교
[BaekJoon] 백준 21608번 상어 초등학교 🎈문제 https://www.acmicpc.net/problem/21608 💬설명 21년도 상반기 기출이었다. 그때 시험장에서 풀었었는데 준비가 안되어 있어서 제대로 풀지 못하고 헤맸던 것 같다. 지금 다시 풀어보니까 왜이렇게 쉬운 문제인지,,😢 시간을 재서 풀었더니 50분만에 풀었고, 한번에 솔브할 수 있었다. 문제를 보고 5가지 함수를 만들어줬다. solve(): 일종의 main 함수 like_max(arr): 비어있는 칸 중 좋아하는 학생이 인접한 칸이 가장 많은 칸들의 배열을 반환해주는 함수 empty_max(arr): 주어진 arr에서 인접한 칸 중 비어있는 칸이 가장 많은 칸(여러개일 수 있음) 배열을 반환해주는 함수 smallest_posi..
[Programmers] 가장 큰 수
[Programmers] 가장 큰 수 🎈문제 https://programmers.co.kr/learn/courses/30/lessons/42746 💬설명 감이 안와서 다른 사람 코드를 참고했는데 풀이를 봤을 때 더 어려운 문제였다. 과정 1000 이하의 숫자이기 때문에 각 자리수를 3번 곱해준다. 문자열로 각 숫자를 취급하면서 정렬한다. '333', '101010'의 경우 첫번째 수부터 비교하기 때문에 '333'이 더 크다. 정렬한 결과를 붙여서 출력한다. 포인트 3번 곱해주는 이유? '1'과 '112'가 있을 때 두번째 숫자부터 비교가 안된다. 두번 곱해주면 '11', '112112'가 되고 여기선 세번째 숫자가 비교가 안된다. 따라서 입력값의 최대값이 1000이기 때문에 3번 곱해준다. '111', ..