본문 바로가기

Algorithm14

baekjoon 7490: 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 문제해석: 1부터 주어진 숫자까지의 수를 다 연산하여 0이 되는 경우를 만든다! 사용기술: dfs 백트래킹 완전탐색 일단 n의 크기가 10이하이니 시간초과에 대한 생각없이 풀이시작 문제를 풀고 나서 보니 단순히 while문으로도 구현이 가능할 거 같긴하다. 출력값이 테스트케이스마다 띄어쓰기가 있어서 그부분에 주의 해주어야됨! 문제는 많이 어렵지 않지만 출력오류를 겪음 예를들어 숫자가 3이라면 나같은경우 path라는 배열에 [1, '',2 ,'', 3.. 2022. 7. 1.
baekjoon 5052: 전화번호 목록 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 초기 구현 방법: 완전탐색 but 시간초과 그렇다면 전부 탐색하지 않게 조건문을 넣어줌. but 시간초과 sort를 사용 (단순 올림차순 sort, key를 len으로 둔 sort) but 시간초과 t = int(input()) for tc in range(t): n = int(input()) arr = [] lenArr=[0]*11 for i in range(n): arr.. 2022. 6. 30.
플러드 필(flood fill) 플러드 필 알고리즘은 다차원 배열의 어떤 연결된 영역을 찾는 알고리즘이다. 시간복잡도: 0(N) BFS나 DFS 둘 다 그래프 자료구조에서 모든 노드를 방문하기 때문에 둘다 플러드필을 구현 가능하다. 둘중 하나인 BFS만으로 flood fill을 구현 해보기 위해 예제를 만들어 진행을 해 보겠다. ex) 0으로만 이루어진 2차원배열에 어느 한 점이 1이다 [[0,0,0,0], [0,0,0,0], [0,1,0,0], [0,0,0,0]] 이를 상하좌우로 한칸씩 움직이며 0인 구역을 기준배열에 +1 을 진행을 시켜본다. [[4,3,4,5], [3,2,3,4], [2,1,2,3], [3,2,3,4]] 이를 만들기 위한 flood fill 예제코드는 arr=[[0,0,0,0], [0,0,0,0], [0,1,0,0.. 2022. 6. 22.
programmers 카펫(완전탐색) https://programmers.co.kr/learn/courses/30/lessons/42842 코딩테스트 연습 - 카펫 Leo는 카펫을 사러 갔다가 아래 그림과 같이 중앙에는 노란색으로 칠해져 있고 테두리 1줄은 갈색으로 칠해져 있는 격자 모양 카펫을 봤습니다. Leo는 집으로 돌아와서 아까 본 카펫의 노란색과 programmers.co.kr result = [] def solution(brown, yellow): global result answer = [] for i in range(1,brown+yellow+1): if int((brown + yellow) / i) == ((brown + yellow) / i): #정수로 나누어 지는지 확인 if ((brown + yellow) / i) 2022. 6. 14.
programmers 타겟넘버(DFS/BFS) https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 위 문제는 numbers에 있는 모든 숫자를 이용하여 target을 만드는 경우의 수를 구하는 문제인데, +와 -연산자만 이용하여 경우의 수를 구하여야 한다. 나의 경우 dfs를 사용하여 풀이를 하였는데, numbers의 모든 숫자를 순회하기 위해 dfs의 매개변수로 인덱스(나의 경우 level)을 재귀할 때 마다 키워주었고, Sum이란 .. 2022. 6. 8.
swea 1865. 동철이의 일 분배 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc&categoryId=AV5LuHfqDz8DFAXc&categoryType=CODE&problemTitle=%EB%8F%99%EC%B2%A0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com t = int(input()) for tc in range(1,t+1): n = int(input()) arr = [l.. 2022. 6. 3.

티스토리툴바