백준
자바스크립트로 백준 풀이하기
백준 9663번 N-Queen을 파이썬으로 풀다가 백준에서 백트랙킹 문제들을 파이썬으로 풀때 대부분 시간초과가 난다는 사실을 알게되었다. 백트랙킹 공부하려는데 시작부터 의욕이 떨어지니 풀이하는 언어를 바꾸려한다. 자바스크립트로 공부해두면 군대 인트라넷으로 몰래 공부할때도 크롬개발자도구로 컴파일해볼 수 있겠다싶어 자바스크립트를 이용해보려한다. 당분간은 새로운 문제를 더 풀기보다 최근 풀었던 문제들을 자바스크립트로 다시 풀어보려한다. ✏️ 백준에서 자바스크립트 (입력) 백준저지에는 자바스크립트가 없어 node.js로 풀이해야한다. 입력방식을 정리하려한다. 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net fs 모듈 이용 이걸 예시로해..
백준 1915: 가장 큰 정사각형 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net ✏️ 풀이 시작점에서 대각선(n,m)방향으로 뻗어나가면서 사각형이 만들어지는지를 확인한다. [i][j]를 기준으로 [i-1][j], [i][j-1], [i-1][j-1]이 모두 0이 아니라면 최소사각형(2x2)가 만들어졌다는 뜻이다. 아래 코드대로 인풋 매트릭스에 값을 더해가다 보면, 이런식으로 매트릭스가 채워질거다. 가장 큰 값이 정사각형의 한변의 길이가 되고 크기는 그 길이의 제곱이된다. n,m=map(int,input().split()) matrix=..
백준 2667: 단지번호붙이기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net ✏️ 풀이 BFS가 편해서 BFS를 이용해서 풀이하였다. 백준 2178: 미로찾기와 백준 11724: 연결요소의 개수 가 혼재된 느낌의 문제였다. 두개 문제의 아이디어를 섞으면 풀린다. 그래프 탐색 시작점을 모르니까 그래프 전체를 반복문으로 돌면서 bfs를 시작한다. 이때 bfs를 하면서 탐색이 된 위치는 0으로 바꾸어 다시 탐색하는 일이 없도록 해주면 된다. 이렇게해서 bfs()를 몇번..
백준 11724: 연결요소의 개수 해설- python
✏️ 문제 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ✏️ 풀이 visited 리스트를 순차적으로 확인하면서 요소값이 0일때 bfs를 실행할거다. 그러면 만약 1,2,4 연결되어 있으면 bfs 한번실행에 다 1이될거다.. 그러면 다음 반복땐 3에서 bfs를 다시 돌릴거고 이런식으로하면 연결된 부분이 끝날때마다 bfs를 돌릴 수 있게 된다. 이때 bfs돌릴때마다 answer+=1..
백준 2606: 바이러스 해설- python
✏️ 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net ✏️ 풀이 아이디어는 간단하다. BFS를 이용해 1부터 아래로 쭉 탐색해 리스트에 저장하고 리스트의 길이를 출력했다. 입력데이터의 표현방식은 인접행렬을 이용했다. from collections import deque n=int(input()) m=int(input()) # 인접영행렬 matrix = [[0]*(n+1) for i in range(n+1)] # 입력받는 값에 대해 영형렬에 1삽..
백준 1260: DFS와 BFS 해설 (파이썬, node.js)
✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ✏️ DFS와 BFS 개념 DFS와 BFS 개념부터가 가물가물해서 처음부터 정리하려고한다. DFS(Depth-First-Search, 깊이우선탐색) 그림이 좋길래 가져와봤다. 탐색순서: 1->2->4->8->5->3->6->7 (1) 탐색시작노드를 스택에 삽입하고 방문처리를 한다. (2) 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있..
백준 11286: 절댓값 힙 해설- python
✏️ 문제 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net ✏️ 풀이 파이썬의 heapq 모듈을 이용했다. 모듈 사용에 대한 내용은 여기에서 파이썬 heapq 모듈 사용법과 응용 ✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으 duckracoon.t..
파이썬 heapq 모듈 사용법과 응용
✏️ heapq 최소 힙(min heap) 자료구조를 제공한다. 원소는 항상 정렬되어 추가되고 삭제되며 가장 작은 값이 언제나 인덱스 0에 위치하게 된다. import heapq ✏️ 최소힙의 생성 heapq 모듈을 이용함으로써 일반 리스트를 마치 최소 힙처럼 다룰수 있게 된다. 그냥 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘겨서 사용하면된다. 즉 heapq모듈을 통해서 원소를 추가하고 삭제하면 그 리스트는 최소힙이 된다. heap=[] ✏️ 최소힙 원소추가 heappush(), 첫번째 인자는 원소를 추가할 대상 리스트, 두번째 인자는 추가할 원소 시간복잡도: O(logN) heapq.heappush(heap, 4) heapq.heappush(heap, 1) heap..
그리디 알고리즘 개념정리와 문제
✏️ 그리디 알고리즘 간단하게 이야기하면 뒷 일은 생각안하고 당장에 눈 앞에 있는 것중에 가장 좋은 것만을 택하는 알고리즘이라고 볼 수 있다. 시작점부터 시작해서 가장 큰수를 얻어야하는 문제가 있다. 여기서 노란색 화살표로 표현된 것이 그리디 알고리즘, 주황색 화살표로 표현한 것이 최적해이다. 처음에 10을 거쳐야 가장 큰 수인 500을 얻을 수 있지만 그리디 알고리즘은 당장에 가장 큰 수인 15를 먼저 선택했기떄문에 20을 출력하게 된다. 그리디(Greedy)알고리즘은 이처럼 최적해를 보장해주지 않는다. ✏️ 그리디 알고리즘의 사용조건 첫째. 그리디 알고리즘은 최적해를 보장해주지 않는다고 했다. 즉, 그리디 알고리즘을 이용했을때 최적해가 나오는 문제에 그리디알고리즘을 이용할 수 있다. 이를 만족시킬 조..
백준 1654: 랜선자르기 해설- python
✏️ 문제 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ✏️ 풀이 이진탐색을 이용하는 문제다. 이진탐색에 대한 내용은 여기에서 랜선의 길이에 대해서 이진탐색을 시행한다. k,n= map(int, input().split()) line = [] for _ in range(k): line.append(int(input())) start = 1 end = max(line) while(start=n: start=mid+..