Algorithm 썸네일형 리스트형 [Baekjoon]백준 1260 DFS와 BFS(실버 2) - Python 문제를 살펴보면 이전에 작성한 코드를 활용하여 DFS와 BFS로 노드를 탐색하고 탐색한 노드들의 번호를 순서대로 출력하면 된다 이전에는 visited 리스트에 방문 순서를 저장하였기때문에 해당 함수들을 그대로 사용하되,마지막 출력 형식을 바꾸어주기만 하였다 대신 같은 변수를 쓰면 헷갈리기도 하고 값이 초기화가 제대로 되지 않을 수 있기 때문에 visited리스트와 cnt 변수는각 함수 역할(dfs, bfs)에 맞게 다시 선언해주었다 visited 리스트를 그대로 사용하지 않고 다른 방법을 사용할지잠깐 고민을 해보았지만 그렇게 되면 dfs, bfs의 가독성이 더 떨어지지 않을까 라는 생각으로 그대로 사용하였다이후 visited 리스트에 저장된 방문순서를 바탕으로 각 순서에 따라 어떠한 노드를 방문하였는지새.. 더보기 [Baekjoon]백준 24445 알고리즘 수업 - 너비 우선 탐색 2(실버 2) - Python 문제를 살펴보면 이전 문제처럼 너비 우선 탐색으로 해결을 하되, 이번에는 인접 정점을 내림차순으로 방문한다따라서 이전 코드를 그대로 사용하되, sort()를 sort(reverse=True)로 바꾸어 사용하면 정답을 확인할 수 있다이전문제 블로그 링크 : https://reflesh02.tistory.com/168 [Baekjoon]백준 24444 알고리즘 수업 - 너비 우선 탐색 1(실버 2) - Python문제를 살펴보면 이전 단계에서 풀었던 dfs(깊이 우선 탐색)이 아니라 bfs(너비 우선 탐색)로 해결해야하는 문제이다dfs는 한 노드에서 가능한 깊이까지 내려간 뒤 더이상 내려갈 수 없다면 한 단reflesh02.tistory.comimport sysinput = sys.stdin.readline.. 더보기 [Baekjoon]백준 24444 알고리즘 수업 - 너비 우선 탐색 1(실버 2) - Python 문제를 살펴보면 이전 단계에서 풀었던 dfs(깊이 우선 탐색)이 아니라 bfs(너비 우선 탐색)로 해결해야하는 문제이다dfs는 한 노드에서 가능한 깊이까지 내려간 뒤 더이상 내려갈 수 없다면 한 단계씩 돌아오는 탐색방법이며bfs는 한 노드에서 인접한 노드들을 모두 방문한 뒤 그 다음 단계로 넘어가 점차 멀리 있는 노드를 방문하는 방법이다 그래서 이전에 제출하였던 코드(24479-python)를 일부 수정하여 코드를 작성하였다우선 덱을 사용하기 위해 from collections import deque를 사용하였다이후 문제에서 주어진 입력들을 입력받고 해당 정보를 바탕으로 graph에 간선 정보를 입력을 해주었다문제에서 인접정점은 오름차순으로 방문한다고 주어졌기 때문에 graph를 sort()로 정렬해주어.. 더보기 [Baekjoon]백준 1202 보석 도둑(골드 2) - Python 문제를 살펴보면 가방에는 최대 하나의 보석만 넣을 수 있으며 각 보석당 가격이 주어진다최종적으로 가방에 최대한 비싼 보석들을 가져가 최대 가격이 되는 것이 목표이다 일단 보석정보를 하나의 리스트로 저장해주었다 map으로 무게와 가격을 입력받고, [무게, 가격]을 append해주었다이후 가방의 크기를 입력받은 후에 보석정보과 가방의 크기가 저장된 리스트를 정렬해준다-> 효율적으로 값을 확인할 수 있기때문 이후 각 가방을 순차적으로 확인하면서 현재 가방에 들어갈 수 있는 보석들을 최대힙에 넣는다최대힙에 넣을 때는 가격을 음수로 넣어야하는데, heapq는 최소힙이기 때문에 이를 최대힙으로 사용하기위해서음수로 값을 넣어주어야한다힙에서 pop하여 가장 비싼 보석을 선택해 가방에 담고 가격을 누적하여 최대값을 갱신.. 더보기 [Baekjoon]백준 17626 Four Squares(실버 3) - Python 문제를 살펴보면 모든 자연수가 4개 이하의 제곱수의 합으로 표현가능하다고한다주어진 수를 몇개의 제곱수 합으로 표현가능한지 구하는 문제이다 문제를 보자말자 가장 먼저 든 생각은 제곱수를 활용해서 위에서부터 내려가며 제곱수로 표현가능한지 확인하는것이었다이전에 풀었던 문제에서 sol()함수를 구현했어서 해당 함수를 수정하여 코드를 완성하였다먼저 if문을 통해 현재 입력받은 수의 제곱근을 구하였을때, 제곱근이 정수인지 확인해주었다제곱근이 정수가 아니라면 하나의 제곱수로 나타낼 수 없다는 뜻이 된다이후 for문을 통해 특정 제곱수를 입력받은 k에서 뺀 후에 해당 값(제곱근)이 정수인지 확인하면된다3개의 제곱수가 필요한 경우는 for문을 두 개 만들어 확인해주면 된다최종적으로 3개의 제곱수로도 표현이 되지 않는다면.. 더보기 [Baekjoon]백준 15663 N과 M (9)(실버 2) - Python 문제를 살펴보면 중복되는 수열을 출력하지 않고, M의 길이를 가진 수열을 모두 출력하는 문제이다예전에 해당 문제를 백트래킹 알고리즘으로 해결하였던 기억이 있어서 이번에도 백트래킹을 활용하였다우선 문제 조건에 해당하는 값들을 입력받은 후에, 수열은 오름차순으로 정렬을 수행해준다이후 재방문여부를 확인하기 위한 리스트를 하나 만들어준 후, 결과값(수열)을 저장할 빈 리스트도 하나 만들어주었다이후부터가 문제인데, 백트래킹 알고리즘은 항상 고민을 하고, 여러 실패를 겪으며 작성하게 되는 것 같다 해당 과정을 간단하게 정리하면 다음과 같다1️⃣ sol 함수는 인자로 현재까지 선택한 개수 k를 받음2️⃣ 만약 k가 목표 길이(length)에 도달하면, 현재까지 구성한 result 수열을 출력하고 함수를 종료(retu.. 더보기 [Baekjoon]백준 1568 새(브론즈 2) - Python 문제를 살펴보면 새가 노래를 부르게 되는데 해당 새는 1, 2, 3...처럼 숫자를 증가하며 노래를 부른다그리고 노래를 부를 때 말하는 숫자만큼 나무에 앉은 새가 날아가게 된다단, 노래를 부르는 타이밍에 해당 숫자보다 나무에 앉아있는 새가 더 작다면 1로 초기화하여 다시 노래를 부른다즉, 4마리가 남아있을때 5를 부를 타이밍이라면 1을 부른다는 것이다 해당 조건을 만족하기 위해 while bird_num > 0이라는 조건을 사용하였다 bird_num이 0이 될 때 해당 while문이실행되지 않아야 하므로 > 를 사용하였다 이후 bird_num과 sing_num을 비교하여 sing_num이 더 큰지 확인한다만약 더 크다면 sing_num을 1로 초기화한 후에 나머지 동작을 하면 된다나머지 동작의 경우 걸리.. 더보기 [Baekjoon]백준 2776 암기왕(실버 4) - Python 문제를 살펴보면 수첩1에 정보들을 입력받고, 수첩2에 또 다시 정보를 입력받아 수첩2에 적힌 정보가 수첩1에 존재한다면 1을, 아니라면 0을 출력하는 간단한 문제이다 허나, 숫자를 탐색하는 방법은 다양하지만 리스트로 입력받고 리스트로값을 찾게 된다면 시간 출력이 발생한다따라서 이분탐색 또는 집합 등 다른 방법을 통해 숫자의 존재 여부를 확인해야한다 알고리즘 연습을 위해 문제를 풀고있기때문에 해당 문제를 이진탐색 함수를 직접 구현하여 해결하였다함수에 low, high, find(찾고자하는 값)을 전달한 후, low가 high보다 커질때까지 mid의 값을 조절하면서 값을 찾아나가면 된다mid는 low와 high의 중간값으로 설정하고, 만약 해당 위치의 값이 찾고자하는 값보다 크다면 high의 값을 조절하고그.. 더보기 이전 1 2 3 4 5 ··· 9 다음
