코딩 테스트 (8) 썸네일형 리스트형 [백준 1260번] DFS와 BFS - Python 백준 1260문제 문제 파악 그래프에 대한 정보가 주어진다. 해당 그래프의 노드(정점)들에는 숫자가 주어져있으며 DFS와 BFS 각각의 방법으로 탐색했을때 지나가는 순서를 구해야한다. 이 문제를 푸는 과정은 크게 다음과 같이 단계를 나누어서 접근했다. 입력 데이터들을 사용하기 쉽게 변환하여 그래프 배열을 구한다. DFS와 BFS를 수행하는 함수를 만든다. 그래프와 시작 노드 그리고 DFS, BFS 함수 등을 이용하여 방문하는 노드 순서 출력 2번의 경우 이전에 DFS, BFS 알고리즘에서 다루었다. 그래서 나머지 부분은 큰 어려움이 없었다. 무엇을 찾아야하는 조건이 없었고 전역 탐색만 수행하면 되었기에 쉬운 문제라고 생각했다. 하지만 이 문제의 관건은 1번이었다. 주어진 입력 데이터들을 2차원 배열로 정.. [알고리즘] DFS 및 BFS - Python 그래프를 탐색하는 방법으로 DFS와 BFS가 많이 언급된다. 실제로 코딩 테스트 문제로 자주 출제되며, 경험상 해당 문제들을 이러한 알고리즘 기법 도구들을 사용하지 않고 다가가면 아주 어려웠다. 그러나 DFS와 BFS라는 도구를 익힌다면 엄청 어려워 보이던 최단 거리 구하기 같은 문제들에 자신감이 생기게 된다. 알기 전과 후의 차이가 극명한 알고리즘으로 이번 기회에 정리를 해두면 도움이 될 것 같다. (엘리스 sw트랙 스터디 활동으로 [이것이 취업을 위한 코딩 테스트]다의 DFS 및 BFS 강의를 기반으로 작성한다.) 깊이 우선 탐색 (DFS : Depth First Search) 우선 DFS라고 불리는 깊이 우선 탐색을 먼저 살펴본다. 트리나 그래프 구조에서 각 노드를 검사하는 방법으로 다음 branc.. [프로그래머스] 체육복 - 자바스크립트(JavaScript) 문제 파악 프로그래머스 그리디 유형의 문제 중 하나인 체육복 문제를 풀어보았다. 그리디 알고리즘에 관한 문제는 문제 파악이 중요하다. 우선 문제부터 보자. 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 .. [알고리즘] 구현 알고리즘 - 시뮬레이션 및 완전 탐색 구현이란? 알고리즘을 공부하는데 구현은 뭐지? 그런 생각이 들었다. 구현이란 머릿속에 있는 알고리즘을 소스 코드로 바꾸는 과정을 말한다고 한다. 알고리즘 문제를 푸는 입장에서 당연한 것이 아닌가 싶었지만, 풀이를 떠올리기 쉽지만 구현(소스 코드로 옮기기) 이 어려운 문제들을 구현 문제라 부른다고 한다. 다음과 같은 구현 문제에 대한 특징들이 있다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 생각해낸 풀이 방법을 코드로 구현함에 있어서 실수 연산, 문자열 처리, 복잡한 로직 등의 장애물을 돌파하는 것이 관건인 유형이라 볼 수 있다. .. [알고리즘] 그리디 알고리즘(탐욕법) 그리디 알고리즘이란? 알고리즘 중에서 그리디 알고리즘(Greedy Algorithm)은 탐욕법이라고도 불린다. 탐욕이라는 단어는 해당 알고리즘을 가장 잘 표현하지 않았나 싶다. 특정 상황에서 사용되는 방법으로 매 선택 순간마다 묻지도 따지지도 않고 가장 최적의 선택을 반복하여 해답을 구해나가는 방식이다. 선택하는 시점 이후의 상황(최종적인 상황)은 고려하지 않는 방식이라서 그리디 알고리즘을 적용할 수 있는 문제인지 파악하는 것이 관건이다. 그리디를 적용할 수 있는 상황을 다시 말하자면, 지역적인 최적의 선택이 곧 전역적 최적의 선택일 때 사용할 수 있다. 좀 더 확실하게 알아보기 위하여 그리디 알고리즘에 대한 구글링을 통해 자세히 정리된 자료를 가져왔다. 그리디 알고리즘을 적용하기 위한 조건을 다음과 같.. [백준 10039번] 평균 점수 - 파이썬(Python) 백준 10039번 문제 문제 파악 5명의 학생들의 평균 점수를 구하는 문제이다. 유의할 부분은 점수가 40점 미만일 경우에는 40점으로 간주하여 구해야한다. 문제 풀이 상당히 쉬운 문제로 간단한 조건문으로 답을 구할 수 있다. 그런데 이 문제에 사실 큰 함정이 있다. 점수가 모두 5의 배수이므로 평균 점수는 항상 정수라고 명시된 부분이다. 평균은 학생들의 총점을 학생 수로 나누어서 구하는데, 나눗셈 결과의 자료형은 float으로 나온다. 예를들어, 위의 예제 입력값을 이용하여 계산해보면 다음과 같다. total_score = 40 + 65 + 100 + 40 + 95 # 40미만의 점수는 40점으로 치환 print(total_score) # 340 그리고 총점을 학생 수 5로 나누어 준다면 결과는 68... [프로그래머스] 타겟 넘버 - 자바스크립트(JavaScript) 프로그래머스의 깊이/너비 우선 탐색(DFS/BFS) 관련 문제들 중 하나인 타겟 넘버를 풀어보았다. 이 문제는 DFS(Depth First Search) 문제일 것이다. 문제 파악 다음과 같이 사용할 수 있는 숫자가 담긴 배열과 타겟 넘버가 매개변수로 주어지며, 이 숫자들을 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 구해야하는 문제이다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 최단 거리를 구하는 문제가 아닌, 모든 경우의 수를 따져보아야하는 문제였다. 위의 예시에서는 배열의 길이가 5이므로 총 경우의 수는 32가지이다. 즉 주어진 배열의 길이가 N개라면 2 ** N(2의 N승)의 경우의 수가 존재하는 .. [프로그래머스] 게임 맵 최단거리 - 자바스크립트(JavaScript) 문제 파악 게임 맵 최단거리 문제는 깊이/너비 우선 탐색(DFS/BFS) 카테고리에 해당되며 최단거리를 구해야 하므로 BFS(Breadth First Search) 방식으로 해결 할 수 있었다. 우선 BFS란 너비 우선 탐색으로 대표적인 그래프 탐색 방법 중 하나이다. 정점의 자식들을 먼저 탐색하는 방식인 DFS와 다르게 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식이다. 루트(root)와 가까운 노드들 부터 탐색하기 때문에 최단거리를 구할 때 유용하다. 추가적인 특징으로 두 가지의 큐(Queue)를 사용해야하며 DFS 방식보다 메모리가 많이 사용된다. 풀이 과정 1. 현 지점에서 다음 차례에 갈 수 있는 지점을 리턴하는 함수 만들기 다음의 경우를 제외한 좌표값을 반환하도록 만들었다. 이미 지나.. 이전 1 다음
