본문 바로가기

PS문제풀이

 (15)
그 유명한 N-queen Is this the real life? Is this just fantasy? Caught in a landside, No escape from reality Open your eyes, Look up to the skies and see, I'm just a poor boy, I need no sympathy, Because I'm easy come, easy go, Little high, little low, Any way the wind blows doesn't really matter to Me, to me Mamaaa, Just killed a man, Put a gun against his head, pulled my trigger, Now he's dead Mamaaa, life had j..
백준 1300-K번째수 알고리즘 분류: 파라메트릭 서치, 이분 탐색 설명하기 전에, 파라메트릭 서치(매개 변수 탐색)에 대해 알아볼 필요가 있다. 파라메트릭 서치는 "...한 값을 찾으라" 하는 문제를 "이 값은 ...인가?" 하는 예/아니오를 판별하는 간단한 문제로 바꾸어서 탐색하는 것이다. 그렇다면 파라메트릭 서치는 이분 탐색과 연계되기 매우 좋은 조건을 가지고 있다. 이 문제에서도 "...한 값을 찾으라" 형태의 문제 형식을 따르고 있다. 따라서 이 문제를 풀기 위해 예/아니오를 판별하는 문제로 바꾸는 것이 중요하다. 다음 아이디어를 생각해보자. 어떤 리스트를 오름차순으로 "정렬"한다는 것은 크기가 작은 순서부터 큰 순서대로 배열한다는 것이다. 그렇다면 정렬 리스트에서 제일 마지막 값은 최댓값이고 제일 첫 번째 값은 최솟..
가장 긴 증가하는 부분 수열-2 O(N log N) 알고리즘 이 문제는 풀면서 고민을 많이 했던 문제이다. N의 범위가 1000000 미만인데, 이렇게 되면 O(N^2)알고리즘으로는 택도 없다. 먼저 O(N^2)알고리즘을 연구해보자. n = int(input()) a = list(map(int, input().split())) dp = [1 for i in range(n+1)] for i in range(n): for j in range(i): if a[j] < a[i]: dp[i] = max(dp[i], dp[j]+1) print(max(dp)) 여기에서 시간을 잡아먹는 요인은 무엇일까? 바로 a[j] < a[i]인 부분을 판별하기 위해 반복문을 돌리는 것이다. 만약 a[j] < a[i]인 것을 어떤 형식으로 기록해 놓는다면 어떨까? 이 아이디어를 통해 LIS ..
냅색 연습-2293 동전1, 1535 안녕 먼저, 오랜만에 올리는 PS 일지인 만큼 초심으로 돌아가고자 하여 동적계획법을 연습해보았다. 그리고 언어를 python으로 하였는데, 이전에는 C++로 하였지만 다니는 학교에서 python을 사용하여 python으로 문제를 풀게 되었다. 문법상 구조는 거의 비슷하니 C++에서 python으로 넘어가는 것은 C언어를 처음 배울 때 보다는 어렵지 않았다고 느꼈다. 문제를 분석해보자 n가지 동전이 있다. 각 n가지 동전은 서로 다른 가치를 가지고 있다. 이 동전들을 여러 번 사용하여 k라는 가치를 만드는 방법의 수를 구하는 문제이다. 냅색이라고 하기엔 애매하지만, 냅색이랑 거의 비슷한 구조를 지닌다고 느꼈다. 문제를 분해하여 생각하면 좋을 것 같다. dp[k] += dp[k-coin[i]]가 핵심적인 문제 분..
[PS일지]백준 11657번 타임머신, 벨만-포드 알고리즘 전에 배웠던 다익스트라는 치명적인 결점이 있었다... 바로 음수간선에는 제대로 된 최솟값을 찾지못한다는 것이다! 그리고 무엇보다 음의 사이클(음수가 포함된 회로)를 찾지 못한다. 음의 사이클이 존재하는 그래프에서는 어떤 알고리즘도 정확하게 최솟값을 찾기가 불가능하다 예를 들어 보자 1번에서 2번으로 가는 것의 가중치가 1이고 2번에서 3번으로 가는 것의 가중치가 -10이고 3번에서 1번으로 가는 것의 가중치가 1이라 하자 이의 최단경로는 구할 수 없다. 음의 무한대이기 때문이다. 1번-2번-3번-1번-2번-3번- .... 순으로 가면 음의 무한대가 된다... 이러한 문제들을 해결하는 아주 좋은 도구인 벨만-포드 알고리즘을 배울 것이다. 벨만-포드 알고리즘의 원리는 생각보다 간단하다. W(u, v)를 u-..
[PS일지]백준 1753번 최단경로, 다익스트라기초 DFS, BFS를 배운 뒤 최단경로관련 알고리즘을 배우기 시작하게 되었다. 다익스트라, 벨만-포드, 플로이드-와셜 등 가중치가 없었을 때는 BFS의 아주 좋은 성질로 쉽게 풀 수 있었지만, 가중치(돈, 거리, 시간 등등)가 있는 그래프에서는 BFS를 적용하기 힘들다. 가중치가 있는 곳에서 최단경로를 찾기위해 BFS와 비슷한 방식을 사용하는 알고리즘이 있는데, 그것이 다익스트라 알고리즘이다. 기초적인 연습문제를 풀기 전에 다익스트라 알고리즘에 대해 배워보자 다익스트라 알고리즘은 네덜란드의 전산학자 에츠허르 데이크스트라가 고안한 알고리즘이다 이분은 튜링상까지 받은 매우 유명한 분이다.(수학에서 필즈상으로 보면 된다.) BFS에서 인접한 정점을 모두 방문하듯이 다익스트라 알고리즘은 우선순위큐(priority ..
[PS일지]위상정렬(백준 2252기초, 줄세우기) 오늘 종만북에서 DFS와, 위상정렬, DFS 스패닝 트리 등등... 을 배웠다. 이 시간에 블로그를 쓰다니... 다른 굇수분들의 비해서는 많이 초라하지만 골드 2 기초 위상정렬 문제인 단계별로 풀어보기에 있는 백준 2252번 풀이를 올릴까한다. 어쨌든 나는 닉값하는 코딩 새싹이라 많이 못한다. 잡다한 이야기는 각설하고 일단 문제 분석 들어가자 우리가 구해야할 것은 학생이 줄을 서는 순서이다. 무언가 거창한 알고리즘을 써야할 것 같지만 굳이 그런 것은 아니다. 위상정렬이라는 것을 쓰면 된다. 위상정렬이란 순서를 만드는 거라고 보면 된다. 당신이 프린터기로 사진을 인쇄한다고 생각해보자 1. 잉크를 체운다. 2. 종이를 체운다. 3. 콘센트를 꼿는다. 4. 인쇄버튼을 누른다. 대충 이런 순서로 배열되어있다고 ..

티스토리툴바