프로그래밍
자바스크립트로 백준 풀이하기
백준 9663번 N-Queen을 파이썬으로 풀다가 백준에서 백트랙킹 문제들을 파이썬으로 풀때 대부분 시간초과가 난다는 사실을 알게되었다. 백트랙킹 공부하려는데 시작부터 의욕이 떨어지니 풀이하는 언어를 바꾸려한다. 자바스크립트로 공부해두면 군대 인트라넷으로 몰래 공부할때도 크롬개발자도구로 컴파일해볼 수 있겠다싶어 자바스크립트를 이용해보려한다. 당분간은 새로운 문제를 더 풀기보다 최근 풀었던 문제들을 자바스크립트로 다시 풀어보려한다. ✏️ 백준에서 자바스크립트 (입력) 백준저지에는 자바스크립트가 없어 node.js로 풀이해야한다. 입력방식을 정리하려한다. 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net fs 모듈 이용 이걸 예시로해..
NQueen 문제 파이썬과 자바스크립트 풀이
백준 9663번 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net ✏️ 구상 N*N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 배치해야한다. 퀸의 움직임은 직선방향, 대각선방향이다. 그렇다면 생각나는 기본적인 로직은 우리는 퀸을 한줄에 하나씩만 배치할 수 있다는 것이다. 우선 배치한다고 생각해보고 하나씩 손으로 배치를 해보자. 두 번째 줄에선는 1,2번째 칸에 퀸을 배치할 수 없다. 두번째 줄에도 배치했으니 이제 세번째로 넘어간다. 세번째줄에 배치가 불가능하다. 따라서 다시 두번째 줄로 돌아가 4번째 칸에 배치한다. (3번..
백트랙킹 기법 정리
백트랙킹(backtracking)이 무엇인가? 뭐 탐색을 하면서 그냥 필요없는 경로는 손절치고 가지치기하는 알고리즘이다. DFS랑 유사하다 이정도로 대충 알고있었다. 따라서 이번에 공부하면서 정리해보려한다. ✏️ Backtracking 정의는 이렇다. '해를 찾는 도중에 해가 아니어서 막히면 다시 되돌아가서 다시 해를 찾는 기법.' 이걸 가지치기(pruning)이라고 하는데 가지치기를 얼마나 잘하느냐에 따라 효율성이 결정된다. 구현방식? DFS등으로 모든 경우의수를 탐색하는 과정에서 조건문등으로 답이 절대 될 수 없는 상황을 정의하고 그런 상황에서는 탐색을 중지시키고 다시 처음으로 가서 다른 경우를 탐색하게끔 구현할 수 있다. 트리에 대해서 DFS 실시 각 노드가 유망한지(promising) 점검 해당 ..
백준 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..
DFS와 BFS 각각 사용하는 경우
✏️ DFS와 BFS의 구현방법과 차이 설명 아래글에 설명해두었으니 이 내용은 여기서 확인바란다. 백준 1260: DFS와 BFS 해설- python ✏️ 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에.. duckracoon.tistory.com ✏️ DFS와 BFS 각각 어떤 상황에서 사용할까? 어떤 문제를 풀때 DFS를 써야할지, 어떤 문제를 풀때 BFS를 쓸지 난감한 경험때문에 정리한다. When is it practical to use Depth-First Search (DFS) vs..