BFS / DFS 이용한 8-puzzle 문제
·
기타/8-puzzle (Python)
너비 우선 탐색과 깊이 우선 탐색을 이용한 문제를 받게 되어서 이번 글을 쓰게 되었다. 8-puzzle을 파이썬으로 프로그래밍 해보자 문제는 다음과 같다 initial 초기의 배열에 있는 원소를 한번씩 움직여서 내가 원하는 배열(goal)을 찾게되면 탐색을 종료하고 goal이라는 배열을 반환하면 된다. 상태를 나타내는 클래스 # 상태를 나타내는 클래스 class State: def __init__(self, board, goal, moves=0): self.board = board self.moves = moves self.goal = goal # i1과 i2를 교환하여서 새로운 상태를 반환한다. def get_new_board(self, i1, i2, moves): new_board = self.boa..
[알고리즘] 다익스트라 알고리즘(Dijkstra)
·
컴퓨터 과학/알고리즘
다익스트라 알고리즘은 음수 가중치가 없는 그래프에서 동작하는 최단 경로 탐색 알고리즘으로 프림의 MST 알고리즘을 약간 변경한 형태이다. 다익스트라 알고리즘이 프림 알고리즘과 다른 두 가지 차이점은 다음과 같다. 프림 알고리즘은 경계로부터 최소 거리를 정점의 거리 값으로 설정하지만, 다익스트라 알고리즘은 시작 정점으로부터 각 정점까지의 전체 거리를 사용한다.다익스트라 알고리즘은 목적 정점이 나타나면 종료하지만 프림 알고리즘은 모든 정점을 방문해야 종료한다.그래프를 예시로 다익스트라 알고리즘의 동작에 대해 설명해 보겠습니다. 가중치가 부여된 그래프가 있습니다. 1를 시작 정점으로 잡고 퍼져나가는 것을 알아보겠습니다. 구현 (1) : 순차 탐색을 이용한 방법으로 노드의 개수가 N이라고 할 때 각 노드마다 최..
Programmers / 겹치는 선분의 길이 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 겹치는 선분의 길이 (0단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/120876 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include using namespace std; int long_line[200]; int solution(vector lines) { int answer = 0; for (int i = 0; i < lines.size(); i++) { for (int j ..
Programmers / k진수에서 소수 개수 구하기 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: k진수에서 소수 개수 구하기 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include #include #include using namespace std; // visit[0] = 0P0 // visit[1] = P0 // visit[2] = 0P // visit[3] = P bool visit[4] = { false }; ..
Programmers / 주식가격 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 주식가격 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/42584 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include #include using namespace std; vector solution(vector prices) { vector answer; int idx = 0; for (int i = 0; i < prices.size(); i++) { queue q; int..
[알고리즘] 깊이 우선 탐색(DFS, Depth-First Search)
·
컴퓨터 과학/알고리즘
너비 우선 탐색이 시작 정점에서 시작하여 점차 탐색 범위를 넓혀 나가는 방식이라면, 깊이 우선 탐색은 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다.깊이 우선 탐색 깊이 우선 탐색은 시작 정점을 경계에 추가하는 것으로 시작한다. 너비 우선 탐색의 그림 예를 변형해서 가져왔다. 하나의 지점에서 시작하여 가능한 멀리 있는 정점에 도달하고 재귀하는 방식을 가진다.구현 깊이 우선 탐색은 두 가지의 코드를 사용할 수 있다. 1. Stack를 이용한 깊이 우선 탐색 2. 재귀 함수를 이용한 깊이 우선 탐색 이 두 가지가 있다. (1) #include #include #include using namespace std; bool visited[9]; vector ..
Programmers / 타겟 넘버 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 타겟 넘버 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include using namespace std; int result = 0; void bfs(int target, vector &numbers, int idx, int sum) { if (idx == numbers.size()) { if (sum == target) {..
Programmers / 피로도 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 피로도 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include #define MAX 8 using namespace std; int result = 0; bool visited[MAX] = {false}; int dfs(int cnt, int k, vector &dungeons) { if (cnt > result) resu..
Programmers / 분수의 덧셈 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 분수의 덧셈 (0단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/120808 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include using namespace std; vector solution(int numer1, int denom1, int numer2, int denom2) { vector answer; int i = 2; numer1 *= denom2; numer2 *= d..
[알고리즘] 너비 우선 탐색(BFS, Breadth-First Search)
·
컴퓨터 과학/알고리즘
그래프 순회 문제란 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제를 그래프 문제라고 한다.그래프 순회 문제는 그래프에서 특정 정점을 찾기 위한 용도로 사용할 수 있기 때문에 그래프 탐색 문제(graph search problem)라고 부르기도 한다. 오늘 알아볼 것은 여러 그래프 탐색 알고리즘 중 하나인 너비 우선 탐색에 대한 내용이다.너비 우선 탐색 너비 우선 탐색(BFS)은 시작 정점을 경계에 추가하는 것으로 시작한다.(1)의 검정 동그라미가 시작정점이라고 했을 때 퍼져나가는 모습을 표현했다. 그림 예 (1) (2) (3) (4) (5) 즉 이렇게 시작 지점에서 경계에 인접한 정점을 반복적으로 탐색하는 방법을 가진다.이렇게 되면 전체 그래프를 순회할 수 있게 된다.구현 #include #i..
Programmers / 튜플 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 튜플 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include #include #include using namespace std; // pair second를 내림차순으로 정렬한다. // first는 비교할 필요가 없는게 문제 조건에서 중복을 허용하지 않았기 때문이다. bool cmp(const pair& a, const ..
Programmers / 행렬의 곱셈 / C++
·
코딩테스트(프로그래머스 & 백준)/프로그래머스-C++
*문제 출처는 프로그래머스에 있습니다. 문제 제목: 행렬의 곱셈 (2단계) 문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12949 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 나의 풀이 #include #include using namespace std; vector solution(vector arr1, vector arr2) { vector answer; for (int i = 0; i < arr1.size(); i++) { vector arr3; for (int j..
김치바보
'분류 전체보기' 카테고리의 글 목록 (18 Page)
상단으로

티스토리툴바