![]()
BFS/DFS 를 응용한 그래프 탐색문제이다. 문제 조건에 대해 생각해볼 것들이 있는 문제여서 좋은 문제 같다 https://www.acmicpc.net/problem/5547 5547번: 일루미네이션 첫째 줄에 두 개의 정수 W와 H가 주어진다. (1 ≤ W, H ≤ 100) 다음 H줄에는 상근이네 집의 건물 배치가 주어진다. i+1줄에는 W개의 정수가 공백으로 구분되어 있다. j번째 (1 ≤ j ≤ w) 정수의 좌표는 www.acmicpc.net 1. BFS 탐색 기준 처음에는 빌딩들을 기준으로 순회하고 외벽을 하나씩 세려고 했으나, 그 방법보다는 거꾸로 빈공간인 0을 탐색하고 1을 발견할 때마다 count를 해주는 방법이 적절하다. 위의 예시와 같이 (2,3) 같은 경우 빌딩을 기준으로 센다면, 6..
https://www.acmicpc.net/problem/9465 전형적인 dp 문제 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 비슷한 문제를 이전에 풀어서 쉽게 풀 수 있었다 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 다만 1309번은 경우의 수만 세어주면 되는데, 9465번은 스티커의 값을 누적해서 합해야 한다는 것이 다르다. import sys input ..
![]()
Q. 네이버.com 을 사용자가 브라우저에 입력했을 때 일어나는 일에 대해 설명하라. (웹 동작 방식에 대해 설명하시오.) 사용자가 웹 브라우저에 url을 입력한다. DNS 시스템을 통해 domain과 매핑된 ip 주소를 찾는다. HTTP 프로토콜을 사용하여 HTTP 요청 메세지를 생성한다. HTTP 요청 메세지가 TCP/IP 연결을 통해 웹서버로 전송된다. 웹서버는 HTTP 프로토콜을 활용해 HTTP 응답 메세지를 생성한다. TCP/IP 연결을 통해 요청한 컴퓨터로 HTTP 응답 메세지를 전송한다. 컴퓨터에 도착한 HTTP 응답 메세지는 웹페이지 데이터로 변환되고, 브라우저에 의해 출력된다. 사용자는 출력된 화면을 확인할 수 있다. Q.GET 방식과 POST 방식을 비교하시오. 1) GET 방식 - 데..
https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net dp 는 3 * (n+1)의 공간으로 만들어 주었다. 사자를 배치하는 것에 대해 생각해보면 다음과 같은 세 가지 이다. 1. 사자를 배치하지 않는 경우 dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] 2. 사자를 왼쪽 칸에 배치하는 경우 사자를 연속해서 왼쪽 칸에 배치할 수 없으므로, 이전 계산 값 (dp[i-1])에서 오른쪽에 배치한 경우와 배치하지 않는 경우의 수를 가져온다. dp[i][1] = dp[i-1][0] + dp[i-1][2] 3. 사자를 오른 쪽 칸에 배치하는 경우 사자를 연속..
https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1) 시간초과 풀이 n = int(input()) array = list(map(int, input().split())) answer = 0 def dfs(total, index, target): global answer if total 20: return if index == n-1: if total == target: answer += 1 return if 0
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 네트워크 덩어리를 찾을 때마다 dfs가 실행되고 그래프 탐색이 종료되면 그 네트워크 덩어리의 탐색이 끝났다는 것이다. 즉, dfs가 몇번 실행되는지 카운트 해주면 된다. 생각할 점은 인접그래프 형태로 computers 2차원 배열이 주어진다는 것이다. def solution(n, computers): answer = 0 visited = [False] * n def dfs(start): visit..
https://www.acmicpc.net/problem/15724 15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net 누적합 문제이다 백준 11660 구간합 구하기 5 문제를 지난주에 풀었어서 복습하는 차원으로 풀었다. https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다...
![]()
https://www.acmicpc.net/problem/22856 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 이 문제 풀다가 잘 안되서 리마인드용으로 1991 번도 다시 봤다 1991번 풀이 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc..
