전체 글 검색 결과
477 개의 검색 결과가 있습니다.
알고리즘(python)/기본

[Python]동적계획법3 백준 11723

문제 https://www.acmicpc.net/problem/11723 매우 간단해 보이지만 연산수가 300만이다.배열을 이용하여 구현하면 실패한다.비트마스크의 사용이 필요하다.비트마스크의 특징을 살펴보자.https://codemcd.github.io/algorithm/Algorithm-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%81%AC/빠르고 간결하며 더 작은 공간복잡도를 가지게 할수있다.컴퓨터의 기본적인 연산인 AND,OR,XOR,NOT등을 알아야한다. 12345678910111213141516171819202122import sysT=int(sys.stdin.readline())S=0for _ in range(T): opcodeStr=sys.stdin.readline..

2020. 2. 27. 13:34
알고리즘(python)/탐색

[Python]최단경로 백준 1956

문제 https://www.acmicpc.net/problem/1956 사이클이 될수있는 구간중 가장 짧은 경로 구하는것이다.시작지점이 정해지지 않았고 모든구간에서 확인해야 하기때문에 플로이드 와샬을 이용해 모든 정점에서 모든 정점으로 가는 최소 거리를 구한뒤 i->i가 가장짧은것을 구하면된다. 역시 알고리즘의 복잡도가 O(V^3)이라서 파이썬으로는 통과할수 없었다.pypy3를 이용하여 제출하면 성공할수있다. 1234567891011121314151617181920212223import sys V,E=map(int,sys.stdin.readline().split())INF=sys.maxsizematrix=[[INF for _ in range(V+1)] for _ in range(V+1)]for _ in ..

2020. 2. 27. 00:12
알고리즘(python)/탐색

[Python]최단경로 백준 10217

문제 https://www.acmicpc.net/problem/10217 냅색과 다익스트라의 혼합문제 정도 되는거같다.처음엔 최소힙을 사용하여 구현하였으나 시간초과가 나왔다. 쓸데없는 부분에서 너무많은 탐색을 하는거같다.그냥 순서대로 모두 확인하는 방법이 나을거같다.비용을 열로 두고 도착지점을 행으로 둔 메트릭스를 하나 만들고 DP를 이용해 풀어보자.비용이 더 줄어들수는 없기때문에 비용이 0~M까지 차례대로 도착지점을 확인하며 DP에 소요시간을 넣어주면 된다.간단한 예시를 통해 보면 이해하기 쉽다. 14 10 61 2 3 31 3 6 81 4 9 132 3 3 42 3 7 33 4 4 5 먼저 비용이 10까지 이고 도착지가 4개 있으므로 5행10열의 배열을 만들어준다.첫줄은 입력의 편의를 위해 사용한것으..

2020. 2. 26. 14:20
보안/써니나타스

써니나타스 6번

6문제로 들어가 보면 게시판이 보인다. 다른 게시물들에는 간단히 내용만이 담겨있고 README라는 곳에 들어가보면 Password input창과 함께 "select szPwd from T_Web13 where nIdx = '3' and szPwd = '"&pwd&"'" 이렇게 DB쿼리가 노출되어있다. ' or 1=1#이라는 구문을 통해 확인해보자 역시 필터링이 되어있다. No hacking이라는 구문을 보아 필터링을 확인해 보아야 할거같다. ' or 여기 까지는 wrong query라는 구문이 뜬다.띄워쓰기 ,' ,or은 필터링 되지 않는다.#과 =이 필터링 되고있다.주석에 사용하는 # 대신 뒤의 구문을 모두 무시하는 --로 =은 like로 바꾸어 작성해보자 ' or 1 like 1-- 이렇게 넣어주면 ..

2020. 2. 25. 12:29
알고리즘(python)/탐색

[Python]최단경로 백준 11404

문제 https://www.acmicpc.net/problem/11404 이전 다익스트라 알고리즘이나 벨만포드 알고리즘은 하나의 노드에서 갈수있는 최소거리를 구하는 문제였다면이번엔 모든 노드에서 모든노드로 갈수있는 최소거리를 모두 구하는 문제이다.위 알고리즘들을 사용했을시에는 O(EV^2)이라는 시간이 걸릴것이다.새로운 방법을 써야하는데 플로이드 워셜 알고리즘이다.코드는 간단한 편이며 DP라고 볼수도 있겠다.시간복잡도는 O(EV)이다.https://mygumi.tistory.com/110위 사이트가 이해하기 제일 쉬웠던거 같다. 123456789101112131415161718192021222324252627import sys n=int(sys.stdin.readline())m=int(sys.stdin...

2020. 2. 23. 00:00
알고리즘(python)/탐색

[Python]최단경로 백준 1865

문제https://www.acmicpc.net/problem/1865 문제가 매우길다.하지만 내용은 웜홀은 음의 간선이고 음의 사이클을 가지는 알아보면된다.그런데 벨만포드 알고리즘은 출발노드와 도착노드가 정해져 있어야한다. 이문제는 모든 출발점에서 확인해야한다.원래의 시간복잡도 O(E*V)를 V만큼 다시 반복해줘야하는것이다.주어진 시간을 봤을때 어림도 없다. SPFA라는 벨만포드를 개선한 알고리즘이 있지만 그것또한 최악의 경우 O(E*V)이기 때문에 불가능하다.질문을 조금 찾아보니 문제에 문제가 있는거같다.출발지점을 정해주거나 모든 위치는 연결되어있다등의 추가 조건이 필요할거같다.모든 노드를 검사하는 문제는 아니며 아마 출발지점을 1로 두었을때 일반적인 방법으로 벨만포드알고리즘을 사용하면 해결되는 문제이..

2020. 2. 22. 00:47