목록알고리즘 (226)
궤도
문제 풀이 TMI 난 사실 다익스트라 알고리즘에 트라우마가 있다. 바로 지금보다도 훨씬 아무것도 모르던 2학년 2학기 시절 라이브러리 하나 없이 다익스트라 알고리즘을 구현해야 했던 것이다. 심지어 최단 거리만 출력하는게 아니라 경로도 출력해야 했다. c로 구현해야 했기 때문에 스택, 우선순위 큐 기타 등등을 스스로 구현해야 했다. 하지만 난 이제 라이브러리를 마음껏 사용할 수 있기 때문에 용기를 내보려 한다. 다익스트라 알고리즘은 특정한 출발 노드에서 모든 노드로 가는 최단거리를 구하는 알고리즘이다. 힙을 사용했을 때의 시간복잡도는 O(|E|log|V|)라고 한다. log의 밑은 2다. ko.wikipedia.org/wiki/%EB%8D%B0%EC%9D%B4%ED%81%AC%EC%8A%A4%ED%8A%B..
문제 풀이 솔직히 어려워서 힌트를 봤다. 난 절대 떠올리지 못했을 방법이었다. 일단 이 문제는 비트마스크이다. 2차원 배열에 어떻게 비트마스크를? 싶을 수도 있겠지만 0~(1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1 tmp; for (int j = 0; j < M; j++) matrix[i][j] = tmp[j] - '0'; } for (int i = 0; i < (1
문제 풀이 문제가 참 긴데 사실 마지막 문단을 빼곤 쓸데없는 말이다. 입력값 처리의 벽만 넘으면 아주 못 풀 문제는 아니다. 일단 한줄로 들어온 저 input을 예쁘게 정리하면 - + 0 + + + + - - + 이렇게 된다. S[i][j] = A[i]+A[i+1]+...+A[j]라고 했다. 그럼 S[0][0] = A[i]인 것이고 S[i][i]에는 A[i]의 부호가 있는 것이다. 나름 괜찮은 정보인데 다 풀고보니 난 이 정보를 사용하지 않았다. A[0]부터 A[3]까지의 순서로 값을 구할 것이다. A[0]은 A[0]0, A[1]>0이어야 한다. (0, 1), (1, 1) A[2]은 여기에 또 추가로 A[0]+A[1]+A[2]=0, A[1]+A[2]>0, A[2]> input; int pos = 0; f..
문제 풀이 0~9까지의 숫자를 1번씩만 쓸 수 있기 때문에 visited로 관리할 수 있다. 부등호에 따라 숫자를 넣으며 백트래킹하면 되는데 나중에 stoi를 쓰기 위해 string 변수에 답을 쌓아놓는다. 소스코드 #include #include #include #include using namespace std; vector sign; bool visited[10]; int k; long long min_num = 9876543211, max_num = 0; void backtracking(int pos, string str) { if (pos == k) { //부등호 다 쓰면 최대 최소 갱신 long long result = stol(str); min_num = min(min_num, result)..
문제 풀이 myunji.tistory.com/204 [백준] 14889번 : 스타트와 링크 문제 풀이 팀을 나누는게 가장 중요한 문제이다. 6명이 있을 때 3명을 고르고 나면 선택받은 3명은 스타트팀 선택받지 못한 3명은 링크팀에 넣어 계산하면 될 것이다. 근데, (1,2,3)번 사람을 고르 myunji.tistory.com 각 팀의 인원이 같아야했던 14889번과 달리 이 문제는 인원 수가 달라도 된다. 재귀함수로 풀어도 되지만 사실 이 문제는 비트마스크로도 풀 수 있다. 그래서 이번엔 비트마스크로 풀었다. 4명의 인원이 있다고 하자. 비트는 0 또는 1을 표시할 수 있으니 0은 링크팀, 1은 스타트팀이라고 하자. 0001 이라면 0번째 사람은 스타트팀, 1, 2, 3번째 사람은 링크팀인 것이다. 11..
문제 풀이 이 문제 덕분에 가끔은 정말 무식한 방법이 통할 때도 있단 것을 깨달았다. 원하는 채널로 가는 방법은 2가지가 있다. 1. +-버튼을 계속 누르기 2. 채널번호 입력후 +-버튼 누르기 일단 1번은 간단하다. 목표 채널과 현재 채널의 차이의 절댓값을 구하면 된다. 그리고 2번이 중요한데 난 가능한 모든 채널을 백트래킹으로 탐색해 최솟값을 갱신하려 했다. void backtracking(int pos, int digit) { if (digit == 0) //1 1 1 => 2 return; if (pos == digit) { int mul = 1, ch = 0; for (int i = 0; i < pos; i++) { int num = channel.back(); ch += (num * mul);..
문제 풀이 myunji.tistory.com/208 [백준] 1149번 : RGB거리 문제 풀이 이걸 이렇게 표현하는게 맞나? 싶지만 동적계획법 문제를 풀 때는 i번째가 ~라면 i-1번째는 뭐였을까? 라는 방법으로 접근하는 것이 좋다. 보통 문제를 풀 때 0번째가 이거라면 1번째는 myunji.tistory.com 이 문제의 응용 버전이다. 선형으로 배치됐던 집이 이젠 원형으로 배치된다. 고등학교 시절 원순열을 배울 때 선생님이 이런 말씀을 하셨다. "원순열은 시작점이 없어서 헷갈리니까 일단 한 놈을 죽여서 앉힌다고 생각해" 물론 죽인다 식의 표현은 격한 면이 있지만 덕분에 이렇게 몇년이 지난 지금도 잊지 않고 있다. 이 문제의 접근도 똑같이 하면 된다. 일단 첫번째 집의 색을 고정하고 집들을 색칠해 나..
문제 풀이 주어진 예제 입력이 하나인데다가 대충 생각해도 알 수 있는거라 좀 힘들었다. N의 입력이 무조건 짝수인 것만 계산했지 홀수인 경우에 0을 리턴해야 한다는 생각을 못해서 틀리기도 했고... dp배열엔 N/2를 저장할 것이다. 그니까 N=2면 dp[1]에 그 답이 있고, N=4면 dp[2]에 답이 있다. 아무튼 N=2일 때 타일을 채우는 방법은 다음과 같다. N=4라면 일단 처음 3x2를 N=2일 때처럼 채우고, 그 뒤는 dp[1]을 호출하면 된다. 이런식으로... 그럼 여기서 3*dp[1]이 된다. 근데 다른 방법으로도 타일을 채울 수 있다. 이런 모양이 2종류가 있다. 그럼 2*dp[0]을 하면 되는건가?? 여기서 N=6일때로 가면... 이런 것도 가능하고 이런 것도 가능하다. 그럼 dp[i]..