프로그래밍/백준
자바스크립트로 백준 풀이하기
백준 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=..
백준 7576: 토마토 해설- python
✏️ 문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net ✏️ 풀이 BFS로 풀이한다. from collections import deque m,n=map(int,input().split()) #토마토를 받아서 넣기 matrix=[list(map(int, input().split())) for _ in range(n)] queue=deque([]) #이동표현 dx,dy=[-1,1,0,0],[0,0,-1,1] #정답을 담을 변수..
백준 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삽..
백준 2178: 미로탐색 해설- python
✏️ 문제 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ✏️ 풀이 미로에서 최단거리를 구하는 문제다. 최단거리를 구하는 탐색문제의 경우 BFS가 적합하다. from collections import deque n,m=map(int,input().split()) matrix=[] for _ in range(n): matrix.append(list(map(int,input()))) dx=[-1,1,0,0] dy=[0,0,1,-1] def bfs(a,b): queue=deque([[a,b]]) while(queue): x,y=queue.pop..
백준 10866: 덱 해설- python
✏️ 문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net ✏️ 풀이 파이썬의 collections.deque를 이용하였다. 사용법에 대한 내용은 여기에서 from collections import deque import sys n=int(sys.stdin.readline()) dq=deque() for _ in range(n): order=list(sys.stdin.readline().split()) if order[0]=='..
백준 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..