분류 전체보기 (89) 썸네일형 리스트형 소수 판별법에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. PS와 장비에 대한 고찰 (제 2회 KAUPC 후기) 싸지방에서 해보는 대회의 비공식참가 싸지방 컴퓨터의 컴퓨터, 모니터, 키보드, 마우스 그리고 난생 처음 보는 OS의 합작은 상상 이상으로 적응하기 힘들었다. 오타는 계속 나고.. 마우스는 자꾸 이상한데로 삐져나가고.. PS도 장비를 탄다는 것을 느꼈다. 그리고 역시 구현력은 구현을 잘 안푸니까 꽤나 많이 죽었다. 이번에도 저번처럼 한 문제에 2시간 가까이 쏟으며 시간을 버렸고, 끝까지 못맞췄다는 것도 동일했다. 물론 이번에는 왜 틀렸는지는 알았으나 손이 안따라주는 것은 오랜만이었다. 그와는 별개로 내 코드는 매우 더럽고, 난잡하며 세련되지 못한 코드였다. 원래 내 풀이 방식이 노트나 뭐 검정하면서 풀기 보다는 '어 이거 이렇게 하면 될 것 같은데?' 싶으면 그렇게 짜기 시작한 뒤 그 다음 다듬기 시작하는.. 소수 판별에 대한 고찰 소수 판별은 기초적인 알고리즘이며 여전히 코딩 테스트에서도 자주 출몰하고 여러 문제에 섞여들어가고는 하는 단골 유형이다. 그렇다면 소수를 판별하는 방법에 대해 고민해보자. 단일 소수 판별법 하나에 자연수에 대해 소수인지 판별하는 경우 아래와 같은 시간복잡도로 해결할 수 있다. 1. O(N) - 모두 탐색 말 그대로 모두 탐색하면 된다. n=(int(input()) isPrime=True if n>1 else False for i in range(2,n): if n%i==0: isPrime=False break 위와 같이 코드를 작성하면 2~n-1 까지의 수로 모두 나눠보며 나눠진다면 최종적으로 isPrime은 False일 것이고 나눠지지 않는다면 최종적으로 isPrime은 True일 것이다. 하지만 이렇.. 깊이우선탐색 구현에 대한 고찰 깊이우선탐색은 탐색 알고리즘이고 스택의 원리를 이용해서 구현된다. (너비우선탐색은 큐, 다익스트라는 힙의 방식을 이용한다) 대부분의 사람들은 깊이우선탐색을 함수를 이용해서 구현하고는 한다. 실제로 함수가 호출되고 종료되며 작동하는 것은 스택의 원리와 유사하게 작동하지만 왜 실제로 스택을 이용하지 않는 것일까? 파이썬에서는 특히 이 점을 신경써야 한다. 왜냐하면 기본적으로 재귀 제한이 3천밖에 안되므로 만약 깊이우선탐색으로 일자로 4천개의 노드가 이어져 있는 그래프를 탐색한다면 Recursionerror를 반환할 것이다. 그러므로 sys 라이브러리의 setrecursionlimit을 이용해 재귀 제한을 풀어주어야 한다. 이러한 번거로움이나 문제점을 발생시키지 않도록 그러면 스택을 이용해서 구현을 해주면 되.. 다익스트라와 0-1 BFS에 대한 고찰 가중치가 존재하는 그래프 즉 0과 1 이 두 개만 존재하는 그래프가 존재한다고 했을 때 이때 다익스트라 알고리즘을 사용하면 O(ELogV)의 시간복잡도를 갖는다. 하지만 이런 상황에서는 우선순위 큐가 아닌 덱을 활용하여 O(E+V)의 시간복잡도로 해결할 수 있다. logV가 매우 강력한 복잡도이긴 하지만 역시 곱보단 합이 훨씬 시간적으로 이득이다. 그 방법또한 간단하다. 덱을 이용해서 다음에 넘어가려는 곳의 가중치가 1이라면 덱의 뒤쪽에 append 0이라면 앞에 append해주면 된다. append와 pop은 O(1)이고 V개의 정점에서 탐색하고 E개의 간선만큼의 값이 큐에 들어가므로 O(V+E)이다. 원리는 다음과 같다. 일단 탐색을 진행하면서 다음 노드가 0이라면 누적값에 0을 더하면 값이 변하지 .. 다익스트라 알고리즘과 플로이드 와샬 알고리즘에 대한 고찰 E개의 간선과 V개의 정점을 갖는 그래프가 있다고 가정하였을 때 다익스트라는 한 개의 정점에서 나머지 연결된 정점들까지의 거리를 O(ElogV)의 시간복잡도로 구할 수 있다. 시간복잡도에 대한 이유는 간선 만큼의 heap에 push가 발생한다. 그 횟수가 E이고 heap에 push하는데 걸리는 시간은 LogN 이므로 E개에 간선에 대해서 push가 발생하므로 LogN이 걸리는 push를 E번 수행 즉 E*logV 이다. 플로이드 와샬 알고리즘은 모든 정점에서 다른 모든 정점까지의 거리를 O(V^3)의 시간복잡도로 구할 수 있다. (왜냐하면 3중 for문 으로 구하니까) 그렇다면 모든 정점에서 다른 모든 정점까지의 거리를 구하려 할때 모든 정점에서 다익스트라를 사용한다면 시간복잡도는 V (모든 정점에 대해.. XOR을 이용한 간단한 트릭들 XOR 연산은 비트를 기준으로 연산을 하게 되는데 두 비트가 같으면 0 다르면 1이다. 다시말해 자기 자신과 xor 연산을 하게 된다면 모든 비트가 같으므로 0이 나오게 되고 0과 xor연산을 하게 되면 자기 자신이 나오게 된다는 뜻이다. 이 것을 이용해서 한번 값을 스왑해보자. 맨 처음 x=n, y=m이 들어있다고 가정해보자. (n,m은 정수) x에 x^y값을 넣어준다. 따라서 현재 x에는 n^m이 들어있는 상태이다. 그 상태에서 y에 x^y값을 넣어주자. 그렇게 된다면 y에는 (n^m)^m 값이 들어가게 되고 m^m은 0이고 0^n=n이므로 y에는 n이 들어가게 된다. 마지막으로 x에 x^y값을 넣어주게 된다면 (n^m)^n이므로 n^n=0 0^m은 m으로 x에는 m이 들어가게 된다. 최종적으로 y=.. 루트 노드가 정해진 트리에서 부모 - 자식 관계를 O(1)에 구하는 법 루트 노드가 정해진 트리에서 두 노드의 부모 - 자식 관계를 확인할 때 여러 방법이 있다. v는 정점(vertext) e는 간선(edge)이다. 일단 간단하게 한 노드에서 BFS를 진행하여 루트 노드까지 탐색하는 경우로 이 경우에는 미리 루트 노드에서 탐색을 진행하여 루트 노드로부터의 거리값을 알고 있어야 더 수월하게 진행된다. 시간복잡도는 루트 노드에서의 탐색 O(V+E) + 한 노드에서의 탐색O(V+E)이다. 위의 방법을 조금 발전시키면 그것이 최소 공통 조상 즉 LCA(least common ancestor) 알고리즘이다. LCA 알고리즘의 대략적인 흐름은 루트노드까지의 거리를 구해 놓고 거리가 먼 쪽을 이동시켜 거리가 같도록 맞춰준다. 그 다음부터 두 노드를 한 칸씩 이동시키고 그리고 높이가 같아.. 22 현대모비스 알고리즘 경진대회 예선 후기 일단 결과는 예선 합격을 했다.. 상상치도 못했던 예선을 합격하게 되어서 매우 놀랐다 ㅋㅋㅋㅋ.. 대회 자체에는 할말이 많았지만 그래도 7월 18일날 입대를 하게 되는데 빠르게 예선 본선을 진행해주는 현대모비스가 고마울 뿐이다. 물론 상품 수령까지 하지는 못하고 가겠지만 ㅠ 다만 불편한 점이 한두가지가 아니어서 여러모로 개선해주었으면 하는 부분은 많았다. 대회 자체에서는 고급 알고리즘이 꽤나 많이 나온 것 같았다. 알고리즘을 공부하면서도 "아 ㅋㅋㅋㅋ 이건 어지간한 대회에서도 안나오겠지" 라고 생각했던 알고리즘들이었다. 이런 알고리즘에 익숙하지 않다면 일반적으로 그냥 틀릴 문제들이 꽤나 있었다. 사실 대회를 거의 장난으로 쳤었다. 군대에서 휴가나온 친구랑 아침부터 영화보고 집에서 돈까스 튀겨먹고 놀다가 .. HTML 문법 - 7 (입력 양식 태그) 입력 양식 태그 입력 양식 태그는 회원가입할 때 이름, 나이, 성별 같은 것을 입력할 때 사용하는 태그들이다. 이 태그는 무언가 정보들을 받아올 때 사용하는 태그이다. 다음과 같은 속성들을 가지고 있다. name 폼의 이름 action 입력 데이터를 처리하는 웹 프로그램 (jsp,php 와 같은) method 전송 양식 (GET, POST) type 입력 양식 모양 에서 사용가능한 태그들 입력 여러줄에 대한 입력 입력 요소에 대한 라벨링 form에 관련된 요소 요소에 대한 설명 선택 목록 생성 선택 목록에서 관련 옵션 그룹 선택 목록의 옵션 버튼 입력에 대한 미리 정의해놓은 옵션들 계산 결과 아래와 같이 입력이 가능한 박스를 하나 생성한다. 닫는 태그가 존재하지 않는다. value속성을 이용하여 초기값을.. 이전 1 2 3 4 5 6 7 ··· 9 다음
