목록알고리즘 (30)
대웅짱님의 블로그
문제: https://www.acmicpc.net/problem/9997 N개의 단어가 주어졌을 때 이 단어들의 조합으로 a-z까지의 알파벳을 한 번씩 사용하는 문장을 몇 개 만들 수 있는지를 묻는 문제이다. 단어들은 한 번씩만 사용할 수 있다. 예) abcd efgh ijkl mnop qrst uvwxyz 라는 단어들이 주어졌을 때 이 단어들을 모두 한 번씩 사용하면 a-z까지의 알파벳을 모두 한 번씩 사용하게 되므로 상근이가 만들 수 있는 테스트 문장의 개수는 1개이다. 나는 비트 마스크를 이용하여 풀었다. 먼저 시프트 연산을 통해 각 단어의 값을 저장한다. 각 알파벳의 값이 비트의 한 자리씩 담당하게 된다. 예를 들어 단어가 'abc'이고 단어를 저장하는 변수가 str, 단어의 값을 저장할 변수가 ..
문제: https://www.acmicpc.net/problem/2823 행과 열, 빌딩과 길이 주어졌을 때 유턴을 하지 않고 모든 길을 지나면서 다시 시작 위치로 올수 있는지를 물어보는 문제이다. 간단하게 DFS를 이용해서 풀었다. DFS로 갈수 있는 길을 모두 확인하면서 만약 현재 길에서 세 방면 이상이 막혀(빌딩이나 지도의 끝)있다면 이 길은 막다른 길이라고 판단 할 수 있다. 길은 모두 이어져 있다고 문제에 명시되어 있으므로 DFS는 한 번만 수행하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include#includeusing namespace std;int n, m..
문제: https://www.acmicpc.net/problem/10972 순열이 주어졌을 때 다음 순열을 출력하는 문제이다. 순열의 길이는 최대 10000 이다. algorithm헤더의 next_permutation(순열 배열의 시작 주소, 끝 주소)를 사용하면 곧 바로 다음 순열을 알 수 있지만 그냥 다음 순열을 계산하는 방법으로 풀었다. 1. 순열을 뒤에서 부터 앞으로 확인하면서 arr[i-1] < arr[i]인 곳을 찾는다. 2. 만약 모든 숫자를 확인했을 때 위의 조건을 만족하지 않으면 마지막 순열이라는 뜻이므로 -1를 출력하고 종료한다. 3. 1의 조건을 만족하는 지점(j)이 있다면 그 j를 기준으로 순열 두 덩이로 나눈다. 4. [j-n]덩어리에서 뒤에서부터 확인하면서 arr[j-1]보다 큰..
문제: https://www.acmicpc.net/problem/1707 정점과 간선들이 주어졌을 때 이 그래프를 이분 그래프로 나눌 수 있냐 없냐 물어보는 문제이다. 이분 그래프는 그래프를 정점 기준으로 두 집합으로 나누었을 때 그 집합 안에서 정점들 간의 간선이 존재하지 않는 그래프를 뜻한다. 그럼 어떻게 이 문제를 해결할까? 간단하게 DFS를 돌면서 내가 현재 보고있는 정점과 그 정점의 인접한 정점들을 구분지어주면 된다. 난 0과 1를 사용해서 구분지었는데 편하게 색깔이라고 생각하면 될 것 같다. 만약 현재 정점이 0번 색이라면 방문하지 않았던 인접한 정점들은 1번 색으로 칠해준다. 만약 인접한 정점이 이미 방문했던 정점이라면 색을 확인해보고 만약 나랑 같은 색을 가지고 있다면 이 그래프는 이분 그..
문제: https://www.acmicpc.net/problem/1107 보고 싶은 TV 채널 N이 주어졌을 때 최소 몇 번의 리모컨 버튼 누름으로 그 채널에 갈 수 있는지를 물어보는 문제이다. 리모컨은 M개의 버튼이 고장나 있는데 고장나는 버튼은 숫자 버튼이고 위 아래 버튼은 고장나지 않는다. 처음에는 이 문제를 그리디로 접근해서 1. 100 - N번 채널의 절대 값2. N - 고장나지 않은 버튼으로 갈 수 있는 N번 채널의 가장 가까운 아래 채널의 절대 값 + 길이3. N - 고장나지 않은 버튼으로 갈 수 있는 N번 채널의 가장 가까운 위에 채널의 절대 값 + 길이 위 세개 중 최소 값을 구해서 풀려고 했었는데 이 가장 가까운 값을 고르는게 생각보다 싶지 않아 그냥 완전탐색을 이용하여 풀었다. 시간제..