•
백준 알고리즘 문제풀이
◦
백준 2872 문제
이번문제는 greedy알고리즘을 활용한 문제이다.
처음에 이 문제를 처음 봤을때는 퀵소트를 활용하는 문제인지 고민했었는데 문제를 읽어보니 책을 정렬하는 방법이 정렬할 책을 빼서 가장 위에 올리는 방식으로 정렬한다고 되어있었다.
가장 먼저 떠오른 해결방법은
1.
첫번째 위치의 값을 pivot으로 둔다.
2.
순회하면서 만약 pivot값보다 작은 값이 들어온다면 count를 증가시킨다.
3.
pivot보다 큰 값이 들어오면 pivot을 변경한다.
이렇게 3 단계로 생각하였다.
하지만 이렇게 구현하는 경우 작동이 안하는 경우가 생기게 된다! 예를들어
2 1 4 3
인풋이 이렇게 들어온다면 count는 두번 증가한다.
하지만 결과는 3이 나와야한다. 2는 3보다 작지만 첫번째 pivot으로 지정되었기 때문에 옮겨야 하지만 체크가 안되고 있는 것을 볼 수 있다.
그래서 다른 방법을 생각해 두었다.
1.
n의 값을 pivot으로 절정한다.
2.
books배열을 뒤에서부터 순회하면서 가장큰 값으로 지정된 pivot과 같은지 비교를 한다.
3.
pivot과 해당 인덱스의 책의 값이 같으면 pivot을 줄여준다
왜 이렇게 하냐?
•
책은 1부터 N까지 번호가 책 이름순으로 사전순으로 매겨져있다.
•
밑에서 부터 큰수부터 하나씩 줄여나가면서 비교를 한다.
•
첫번째로 가장 위로 정렬되어야 하는 값이 뒤에서부터 봤을 때 정렬이 되지 않은 가장 큰 수가 되어야 하기 때문( ex. 3 4 1 2 5 가 인풋으로 들어왔을 때 4를 가장 먼저 올려야 움직이는 횟수를 최소로 할 수 있다)
•
우리는 그럼 배열의 뒷부분부터 큰수 기준으로 정렬이 되어있지 않은 것만 세면 된다.
4.
pivot과 해당 인덱스의 책의 값이 다르면 count를 늘려준다.
위의 방법을 적용해서 아래와 같은 방법으로 코드를 구현할 수 있다.
#include <iostream>
#include <vector>
int result;
int n;
std::vector<int> books;
void input()
{
std::cin >> n;
books.resize(n);
for (int i = 0 ; i < n ; i++)
std::cin >> books[i];
}
void solution()
{
int pivot = n;
for (int i = n - 1 ; i >= 0 ; i--)
(pivot != books[i]) ? ++result : --pivot;
}
void output()
{
std::cout << result;
}
void preset()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);
}
int main(void)
{
preset();
input();
solution();
output();
}
C
복사
◦
백준 1348 문제
이번 문제는 bfs와 dfs를 모두 활용해야 하는 문제이다.
하지만 bfs를 구현해본적이 없어서 bfs부터 천천히 공부하기로 하였다. bfs는 너비 우선 탐색으로 큐를 활용해서 구현하여야 한다. 일단 해당 위치에서 갈 수 있는 공간을 큐에 집어넣어서 현재위치에서 갈 수 있는 모든 공간을 우선 탐색한다. 이후 큐에 들어있는 다음 값을 가져와 해당 위치에서 갈 수 있는 모든 값을 큐의 뒷쪽에 또 추가한다. 이렇게 쭉 너비부터 우선 탐색을 진행한다.
dfs와 마찬가지로 visited배열을 만들어서 방문한 노드는 탐색을 진행하지 않고 넘어간다.
1-2
| |
3-4
C
복사
위와 같이 구성된 그래프의 탐색 순서는
1→2→3→4
가 된다.
큐의 구성을 보면
1 : 1
2 : 2
3 : 2 3
4 : 3 4
5 : 4
6 :
위와 같이 진행이 된다.
1-2-5
| |
3-4
C
복사
하나의 노드를 더 추가하게 되면
1 : 1
2 : 2
3 : 2 3
4 : 3 4 5
5 : 4 5
6 : 5
7 :
이런식으로 진행이 이루어진다.
너비 우선 탐색이기 때문에 5번 노드를 가장 마지막에 탐색하게 된다.
bfs의 의사코드를 구성해 보았다.
void bfs()
{
q.push(시작위치);
visited(시작위치) = true;
while(!q.empty())
{
void 값 = q.front;
q.pop;
for (탐색 가능한 범위)
{
다음값 = 기존값 +- a;
if(방문체크, 가능성체크)
continue;
q.push(다음 값);
visited(다음 값) = true;
}
}
}
C
복사
bfs를 활용해 코드를 구현한 후 해당 위치까지의 길이를 구해야 하는데 길이를 어떤 지점에서 증가시켜야 할 지 감이 오지 않았다. 도저히 생각이 나지 않아서 인터넷의 힘을 빌렸다..
visited배열을 기존에 -1 로 초기화해두고 시작 위치를 0으로 방문하지 않았다면 이전값에서 +1을 해주는 방법으로 구현해서 visited배열의 좌표로 인덱싱하면 거리를 얻을 수 있었다. 남은 이분매칭은 이후에 도전해 볼 예정이다.
