문제 https://www.acmicpc.net/problem/1010 문제해설 n개의 점과 m개의 점이 강을 사이에 두고 있다. n개의 점에서 m개의 점으로 다리를 놓으려고 하는데 다리는 한 점당 하나씩이고 다리가 교차하면 안된다. 이 때 만들 수 있는 다리의 최대 개수를 구하는 문제이다. 문제풀이 하나씩 그려보다보면 힌트를 찾을 수 있다. ...

문제 https://www.acmicpc.net/problem/17626 https://www.acmicpc.net/problem/1699 문제해설 두 문제가 같은 문제여서 풀이를 한번만 쓴다. 어떤 자연수의 합을 제곱수로 표현하는 문제이다. 자연수 n이 주어지고 최소 몇 개의 제곱수로 n을 표현할 수 있는지 찾으면 된다. 문제풀이 처음에 풀 ...

문제 https://www.acmicpc.net/problem/16395 문제해설 n과 k가 주어지고 파스칼의 삼각형에서 n번째 줄의 k번째 수를 구하면 된다. 문제풀이 2차원 dp로 풀면 쉽고 간단하게 풀 수 있지만 1차원만 생각하는 바람에 어렵게 짰다. 물론 공간복잡도 상으로는 1차원이 더 효율적이다. 1차원으로 짠다면 (i * (i - ...

문제 https://www.acmicpc.net/problem/14495 문제해설 피보나치와 비슷한 수열이 나온다. n번째의 수를 구하면 된다. 문제풀이 이미 문제에서 f(n) = f(n-1) + f(n-3)이라는 점화식이 주어졌다. 점화식에 맞게 dp를 짜면되고 long long을 써야한다는 것만 주의하자. 전체코드 1 2 3 4 5 6 ...

문제 https://www.acmicpc.net/problem/11403 문제해설 방향 그래프가 주어졌을 때 i에서 j로 가는 경로가 있는지 판단해주는 문제이다. 문제풀이 기본적인 플로이드 워셜 문제이기 때문에 플로이드 워셜을 돌려주면서 해당 정점으로 갈 수 있다면 1을 저장하고 그래프를 다시 출력해주면 된다. 전체코드 1 2 3 4 5 6...

큐, 스택은 느리다 큐와 스택의 push와 pop 연산에는 O(1)의 시간이 걸린다. 그렇다면 1억번의 push를 한다면 1초가 걸릴까? 나는 그렇게 알고있었지만 아니다. 큐와 스택은 생각보다 훨씬 느린 아이였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include<iostream> #include&lt...

문제 https://www.acmicpc.net/problem/1241 문제해설 n명의 학생들이 각각 번호를 갖고 동그랗게 둘러앉아 있다. 한명씩 일어나서 한바퀴를 돌며 자신의 앞의 학생의 수가 자신의 수의 배수이면 그 학생의 머리를 친다. 한바퀴를 돌았을 때 몇명의 머리를 쳤는지 구하는 문제이다. 문제풀이 n이 최대 십만이고 학생이 가질 수 ...

EntityRef: expecting ‘;’ 요즘 계속 블로그 최신 글들이 검색이 안되서 오늘 구글 웹 마스터 도구에 들어가봤다. 사이트맵을 들어가보니 빨간색으로 오류라고 뜬 것을 발견했다.. 사이트맵 검사기에 들어가서 사이트맵을 입력해보니 EntityRef: expecting ';'이런 오류가 발생했다. 열심히 구글검색을 해보니 &가 있...

문제 https://www.acmicpc.net/problem/1105 문제해설 L과 R이 주어진다. L부터 시작해서 R까지의 수 중에서 8이 가장 적게 들어있는 수의 8의 개수를 세어주면 된다. 문제풀이 아이디어만 떠올리면 구현은 어렵지 않다. 우선 두 숫자의 자리수가 다르다면 답은 무조건 0이다. 예를들어 88과 300이 주어진다면 그 사...

비동기란? 자바스크립트는 비동기 방식으로 동작한다. 그렇다면 비동기는 무엇일까? 동기 우선 동기(synchronous)부터 알아보자 동기라는 말의 의미는 동시에 일어난다는 뜻이다. 무엇이 동시에 일어나는 것인가? 요청과 결과가 동시에 일어난다. 동기방식은 작업들이 순서대로 진행되는 것을 말한다. 예를들어 세탁기 돌리고 빨래 널기, 밥 먹고 30...