본문 바로가기

Algorithm77

[SWEA] 4013. 특이한 자석(Python) / DFS swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeV9sKkcoDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 난이도가 낮은 편에 속하는 SW Expert Academy 삼성 SW 역량 테스트 모의 문제이다. 41분 소요로 워낙 많이 풀어본 문제라 오래 걸리지 않았다. DFS의 구조를 익힌 것이 도움이 됨 dfs 함수 안에서 num이 3보다 작을 때와 0보다 클 때를 모두 봐야 해서 둘다 if 조건문을 걸어줘야 한다! 오른쪽/왼쪽 방향 살피기(자성 같거나 달라서 회전할 수 있는지 여부 확인하며 재귀로 넘기기) 마지막에 자.. 2021. 3. 7.
[SWEA] 5644. 무선 충전(Python) / BFS + Simulation swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWXRDL1aeugDFAUo SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 모의 SW역량테스트 문제 중 어느정도 난이도가 있는 문제에 속한다. 1시간 37분 소요. BFS + Simulation BFS로 각 BC의 충전 범위를 그려줌(다음에 풀 때는 BFS 안 쓰고 위치의 절대값으로 BC의 범위를 그려보자) 핵심은 두 개 이상의 BC의 범위가 겹칠 때, 성능이 큰 순으로 내림차순 정렬하는 것. 이동할 때, 시작 위치도 포함해야 함. 가장 까다로운 부분은 두 사람이 같은 BC에 있는.. 2021. 3. 7.
[SWEA] 4014. 활주로 건설(Python) swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 어렵지 않은 삼성 모의 SW역량테스트 문제였다. 문제 푸는 데 1시간 정도 소요. 가로(행) 탐색, 세로(열)의 모든 케이스를 check_slope 함수에 넣어 가능하면 1, 불가능하면 0 리턴. check_slope () 함수에서 같은 높이이면 cnt += 1 높이 1 높아질 때, 그동안의 쌓아온 거리가 경사로 길이보다 크거나 같다면 가능한 경우이므로 cnt = 1로 초기화 높이 1 낮아질 때, 현재 쌓아온 거.. 2021. 3. 7.
[BOJ] 11053. 가장 긴 증가하는 부분 수열(Python) / DP www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net LIS(Longest Increasing Subsequence, 최장 증가 부분 수열 문제)는 가장 전형적인 Dynamic Programming 문제! 수열의 크기가 N일 때, 기본적인 DP 알고리즘으로 시간 복잡도 O(N^2)으로 해결할 수 있다. dp[i] = array[i]를 마지막 원소로 가지는 부분수열의 최대 길이 모든 0 2021. 3. 4.
[BOJ] 1759. 암호 만들기(Python) / DFS www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net DFS 알고리즘과 combination 모듈을 활용한 것 두 가지 방법으로 풀어보았다. 물론 조합(Combination)을 구한다는 본질은 같다. 파이썬 풀이는 다음과 같다. 방법 1 - dfs로 comb 함수 구현. 시간은 148ms 소요 import sys input = sys.stdin.readline def comb(depth, k, temp): if depth == L: vowel = 0 for s in t.. 2021. 3. 4.
[BOJ] 2583. 영역 구하기(Python) / BFS www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net # 22분 소요 아주 간단한 BFS 문제 M*N크기 맵 1로 초기화 Input 받은 내용을 미리 M*N크기의 맵에 0으로 그려줌 이후 맵에서 1일 때 연결된 곳 BFS 이용하여 0으로 지워주면서 갯수 셈 연결된 곳 0으로 지우는 작업 끝날 때마다 resut += 1, parts에는 갯수 append 해주고, 마지막 출력할 때 sort 파이썬 코드는 다음과 같다. import sys input.. 2021. 3. 4.

티스토리툴바