본문 바로가기

분류 전체보기

 (115)
백준 10451 순열사이클 이 문제의 특징은 '어떠한 노드 s를 목적지로 하는 노드는 1개, 이 s 노드에서 시작하는 노드도 1개'라는 것이다. 이걸 전문용어로 뭐라 있을거 같은데 흠.. 여튼, 그렇기 때문에 bfs같은 탐색을 할 필요 없이 선형으로 탐색하면 된다. 첫번째 반복문은 아직 탐색하지 않은 루트 노드를 선택하는데 쓰고 두번째 반복문은 이 노드로부터 시작하는 사이클을 찾는데 쓴다 탐색을 하다가 이미 방문한 노드를 발견하면 주저없이 반복문을 끝내고 사이클의 갯수를 1증가 시키면 된다. 왜냐하면 위에서 말한 특징 때문에 '이미 탐색한 노드 x를 지금 탐색하였다면 그 x노드는 탐색을 시작했던 노드'라는 명제가 성립하기 때문. #include #include #include #include #include #include usi..
블로그 문제점 을 찾았다 내 코드는 붙여넣기 하면 줄바꿈이 적용이 안되서 붙여넣어지는구나;; 이제 알았네 왜지.. 앞으론 소스코드를 같이 첨부해야겠다
백준 1325 효율적인 해킹 여타 다른 BFS 문제처럼 각 노드별로 그 노드에서 도달할 수 있는 노드의 갯수를 계산해서 최대값을 가진 노드(들)을 출력하면 되는 문제이다. 그런데 이 문제는 4가지의 특징을 가지고 있다. 1. 메모리 평소에 하듯이 adj 배열을 2차원 배열로 선언해버리면 10000 * 10000 * 4byte = 381MB의 메모리를 먹고 short를 써도 190MB를 먹는다 따라서 가변 배열을 써야 한다. 링크는 10만개로 한정되어 있으니 가변 배열을 쓸 경우 100,000 * 4byte라서 1메가도 안된다. 2. 방향그래프 이 그래프는 다른 문제와 다르게 방향 그래프이다 "A가 B를 신뢰한다" 라는 문장은 B->A 와 동치이다. 이것을 유념해두고 문제를 풀어야 한다. 3. 입력 만약 cin으로 입력을 받으면 입력..
백준 1890 점프 혹시 백준에서 채점 돌렸는데 잘 맞추다가 후반부에서 오답나오신분이시라면 결과 출력을 long long으로 했는지 체크하세용 저도 첨에 long long 박아놨다가 막판 출력을 int로 하는 바람에 형번환 되서 한번 틀렸네요 ㅎㅎ BFS문제 풀려고 BFS 눌렸는데 왠 DP문제가 떠서 그냥 풀었다 r만큼 떨어져있는 노드에서 r만큼의 점프가 가능한지 검사하여 가능할 경우 해당 노드까지 도달할 수 있는 경로의 수를 더하는 알고리즘이다 점화식은 아래와 같다. D[i][j] = D[i-r][j] + D[i][j-r], r = [1..9] (if arr[i-r][j] == r, arr[i][j-r] == r) DP는 점화식만 세우면 빠르게 모델링하여 풀수 있다. #include #include #include #in..
백준 10216 Count Circle Groups 노드별로 거리를 계산하고 서로가 통신거리 이내에 있는 노드라면 두 노드를 이어준다( = adj 에 추가한다) 그 후 모든 노드가 탐색될 때 까지 BFS탐색을 여러번 진행하면서 그래프가 몇개 있는지 계산한다. #define getDist(x0,y0,x1,y1) ((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1)) #define dbl(r) (r*r) #include #include #include #include #include #include using namespace std; int testcases; int N; int enemy[3001][3]; bool isVisit[3001]; int enemyNum; int adj[3001][3001]; int adjSize[3001]; int mai..
백준 2667 단지번호 붙이기 2차원 배열을 0,0부터 순차적으로 탐색하다가 집을 만나면 그 집을 루트로 하여 BFS를 시작한다 이 문제에서 약간 다른점은 굳이 isVisit를 쓸 필요가 없다는 것이다. arr[i][j]에서 이미 단지 번호를 붙였고 단지 번호가 붙여져있다는 것은 이미 방문했다는 뜻이니까 isVisit로 방문한지 체크하지 않고 단지 번호가 붙여져있는 것으로 방문한지 체크하면 되기 때문 그 외에 단지 번호를 0부터 붙이고 싶어서 빈땅, 집이 있지만 단지 번호가 붙여지지 않은 집, 단지 번호가 붙여진 집 을 서로 구분하기 위해서 입력을 받을때 0과 1로 받지 않고 -2와 -1로 받았다. #include #include #include #include #include #include using namespace std; i..
[python3] 백준 2739 구구단 숏코딩 python3으로 짰다. 별거 아니지만 숏코딩 순위권... 심심해서 했다n=int(input()) for a in range(1,10):print(n,"*",a,"=",n*a)
[하드웨어] STM32를 이용한 방공시스템 제작 울학교에서 이번 학기에 내가 진행한 프로젝트이다. 통틀어서 1등을 먹었는데, 기록해두면 나중에 면접이든 뭐든 쓸모가 있지 않을까 싶어서 이렇게 기록으로 남겨둔다. 또 혹시 아는가 내 후배들이 내 글을 보고 도움을 받을지... 일단 전체 코드부터 올린다. ↓클릭시 다운 #include "misc.h" #include "stm32f10x.h" #include "stm32f10x_exti.h" #include "stm32f10x_gpio.h" #include "stm32f10x_rcc.h" #include "stm32f10x_dma.h" #include "stm32f10x_usart.h" #include "stm32f10x_adc.h" #include "lcd.h" #include "Touch.h" #incl..

티스토리툴바