개발자 퉁이리

https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 다이나믹 프로그래밍 ⊙ 문제 접근 과정 2차원 배열을 사용하여 문제를 풀었다. 각 문자의 길이만큼 배열을 만들어주고, 규칙성을 찾아내어 정보를 담아준다. i for문과 j for문을 사용해 두 문자열을 비교해주는데 일치하면 dp [i][j] = dp [i - 1][j - 1] + 문자 저장..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 브루트포스 알고리즘 백트래킹 ⊙ 문제 접근 과정 백트래킹 문제였는데 재미있었다. 반복문 i는 4번 돌린다. 범위는 0부터 3으로 각각 0,1,2,3은 순서대로 +, -, *, /이다. 사칙 연산에 대해 값을 모두 탐색하였을 때, 그 값이랑 현재 값이랑 비교하여 큰 값은 maxValu..

https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 비트마스킹 ⊙ 문제 접근 과정 11 & 1 = 1011 & 0001 = 0001 11 & 2 = 1011 & 0010 = 0010 11 & 4 = 1011 & 0100 = 0000 11 & 8 = 1011 & 1000 = 1000 위 코드가 핵심 코드다. 모든 값이 0이라면 벽으로 안 막혀 ..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 다익스트라 0-1 너비 우선 탐색 ⊙ 문제 접근 과정 방문 여부를 카운트로 하여 방문 시에 +1을 count up 해주었다. 만약 순간이동 하는 경우는 방문 카운트를 건드리지 않는다. 왜냐하면 순간이동에 걸리는 시간은 0초이기 때문이다. 그리고 순간이동의 경우에는..

https://www.acmicpc.net/problem/1325

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs코드를 먼저 짜준다. 그다음 rain이라는 변수를 설정해 입력받은 배열에서 가장 큰 높이까지 한 바퀴를 돌 때마다 값을 하나씩 올려준다. 그러다가 그 값이 가장 큰 높이까지 도달하면 bfs로 조사한 안전한 지역 중 최대를 출력해주면 된다. ⊙ ..

https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 ⊙ 문제 접근 과정 윌리암슨수액빨이딱따구리 식구는 식사를 하고 싶어 하는데 귀찮아서 가장 가까운 곳을 가고 싶어 하는 간단한 문제다. 1은 벽, 0은 통로이고 윌리암슨수액빨이딱따구리 식구는 2번이..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 깊이 우선 탐색 ⊙ 문제 접근 과정 bfs를 돌렸다. 2번. 한 번은 입력받은 RGB 그대로 돌려서 구역을 찾아냈다. 마지막 한번은 R을 전부 G로 바꾸고 visited 여부를 초기화해준 후 돌려줬다. ⊙ 문제 풀이 import sys from collections import deque ..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 그래프 탐색 브루트포스 알고리즘 너비 우선 탐색 ⊙ 문제 접근 과정 재귀를 통해 벽을 세우고 3개를 다 세웠으면 그때 bfs를 돌린다. bfs는 바이러스를 기준으로 퍼져나가게 코드를 짜주었고, count 함수를 사용하여 0의 개수를 출력해준다. 0은 안전지역이다. 안전지역이 가장 많은 값을 ans에 저장해 주어 브루트 포스, 모든 경우에..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net ⊙ 문제 ⊙ 입력 ⊙ 출력 ⊙ 예제 입출력 ⊙ 알고리즘 분류 그래프 이론 자료 구조 우선순위 큐 위상 정렬 ⊙ 문제 접근 과정 기존의 위상 정렬에 플러스 알파가 필요했다. 그 플러스 알파는 추가되는 큐에 대해 오름차순 정렬로 입력해줘야한다. 위상 정렬의 특징 중 하나, 위상 정렬에서는 여러 가지 답이 존재할 수 있다. 이 문제에서는 아니다. 가장 난이도가 쉬운 순서대..