2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 접근한 방법 7576. 토마토 문제와 살짝 비슷합니다. 내부, 외부 공간을 굳이 구분할 필요는 없고 매 시간마다 처음 (0, 0) 좌표에서만 bfs를 수행하면서 치즈를 만나는 경우만 체크하여 제거 리스트에 올려주고 그 외 공간은 모두 탐색을 계속 진행하면 됩니다. 치즈를 만나는 경우는 탐색 대상에 들어가지 않기 때문에 애초에 치즈로 둘러쌓인 공간을 탐색할 일이 없습니다. 1. 전체 치즈 수를 체크합니다. 2. 좌표 0, 0 에서 bfs를 실행합니다. 상하좌우를 확인하여 공기만 경우..

2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 접근한 방법 비교적 풀이법이 단순한 완전탐색 문제. 지도가 몇 개의 육지로 나뉘어져 있는 지는 아무 상관 없습니다. L에 해당하는 모든 칸을 확인하여 BFS를 수행합니다. 1. L이면 BFS를 들어갑니다. 2. 시작점을 1로 잡고 이후 상하좌우로 방문하는 L칸 마다 +1씩 더하여 값을 넣어줍니다. (방문 처리) 3. 마지막으로 방문한 칸에서 시작점인 1을 뺀 값이 해당 좌표에서 계산된 시작점에서 가장 먼 지점까지의 거리가 됩니다. 4. 모든 L칸에 대해서 1~3 과..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 접근한 방식 1. 입력으로 n, m을 받고, 2차원 배열 arr에 빙산 정보를 저장합니다. 2. 주어진 4방향(dist)을 이용하여 빙산이 한 덩어리로 얼마나 오래 지속되는지 계산하는 solution 함수를 정의합니다. 3. dfs를 정의하고 모든 빙산이 연결되어 있는지 확인합니다. 4. solution 함수에서는 빙산이 1개로 이루어져 있거나 빙산이 나뉘어 있는 경우까지 계속 반복하여 빙산을 녹이고, 빙산이 1개로 이루어져 있을 때까지 걸리는 시간을 반환..

2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 접근한 방법 입력받은 용액들을 오름차순 정렬한 후 투 포인터로 해결할 수 있습니다. 포인터를 각각 배열의 왼쪽, 오른쪽 부분에서 시작하도록 설정하고 두 포인터가 엇갈리지 않을 때까지 포인터가 가리키는 각 배열의 값의 합의 최솟값을 갱신합니다. 값을 갱신할 때는 0에 수렴하는 값을 넣어줘야 하므로 절댓값으로 바꿔 넣어줍니다. 현재 순회중인 각 포인터가 가리키는 배열의 합이 0보다 큰 경우 오른쪽(큰 값)값을 줄여줘야 하므로 오른쪽..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 접근한 방식 입력받은 문자열을 각각 A와 B라고 한다면 크기가 (A의 길이 +1) * (B의 길이+1)인 2차원 DP 테이블 d를 만듭니다. d[i][j]를 계산하기 위해 다음 점화식을 사용합니다 a[i-1]과 b[j-1]이 같은 글자라면 d[i][j] = d[i-1][j-1] + 1을 넣어줍니다. LCS에 값을 추가할 수 있다는 것을 의미합니다. a[i-1]과 b[j-1]이 다르다면 d[i][j] = max(d[i..

10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근한 방법 적록색약인 배열의 R값을 모두 G, 혹은 G값을 모두 R로 바꿔준 후 적록색약이 아닌 배열과 동일하게 탐색을 넣어줍니다. 모든 값에 대하여 방문이 가능한 경우에만 결괏값을 +1카운트한 후 DFS로 상하좌우를 확인해 진입 시작값과 같은 값들을 모두 방문처리 해줍니다. 2번 탐색을 하고나면 적록색약이 아닌 경우와 적록색약인 경우의 결괏값을 얻을 수 있습니다. Python import sys sys.setrecursionlimit(4000) inpu..

1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 접근한 방법 각 단어들의 자릿수들을 계산해줍니다. 예를 들어 예제 2의 GCF에서 G = 100, C = 10, F = 1 이 되고 ACDEB에서 A = 10000, C는 한번 나왔으므로 기존 값에 더해서 10 + 1000, D는 100, E는 10, B는 1이됩니다. 모든 알파벳에 대한 26개의 공간을 만들어두고 앞서 이 값들을 배열로 표현하면 아래와 같이 됩니다. [ 10000, 1, 1010, 100, 10, 1, 100, 0, 0, 0, 0, 0, ..

14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근한 방법 dfs를 이용한 조합과 bfs를 이용한 탐색을 이용한 문제입니다. 먼저 벽을 세울 3개의 자리를 순차적으로 구성해봐야 하므로 dfs를 이용해서 3개가 카운트될 때까지 빈칸을 찾아 진입합니다. 3개가 구성되면 bfs를 이용해 바이러스를 퍼트립니다. bfs를 여러번 동작해야 하므로 탐색을 시작할 때 미리 구성된 큐와 연구소 배열을 복사합니다. python에서는 큐는 deque의 copy, 어레이는 copy 라이브러리의 deepcopy를 이용하고 js에서는 어레이만 J..

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1707. 이분 그래프 접근한 방법 까다로운 테스트케이스, 조건들이 많아서 풀기에 꽤 재미있었던 문제. 이분그래프는 개념만 보면 한번에 이해하기 어려울 수 있는데 그림으로 표현하면 쉽습니다. 정점을 1 또는 0으로 표현했을 때 같은 집합 안에서 1과 1이 인접하거나 0과 0인 정점이 인접하는 경우가 없다면 이분그래프입니다. 이 그림에서는 왼쪽이 이분그래프, 오른쪽은 아닙니다. 이 아이디어 그대로 모든 정점을 1 또는 0으로 표시해놓을 표시용 배열(코드에서는 ma..

16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 16947. 서울 지하철 2호선 접근한 방법 그래프에 존재하는 사이클까지 각 노드가 도달가능한 최소 거리를 구하는 문제입니다. 두 가지 과정이 필요합니다. 1. 사이클 그래프 찾기 2. 사이클 그래프로부터 각 노드 도달거리 탐색하기 1번에서는 DFS로 사이클이 나올때까지 탐색합니다. 사이클을 찾는 방법은 탐색 출발 노드와 다음 탐색 노드가 같은 경우를 찾으면 됩니다. 단 사이클은 노드가 3개 이상이어야 하므로 깊이가 3회이상인 경우에만 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 최고의 집합 접근한 방법 문제 예시들을 보면 곱이 최대인 경우는 항상 0~s의 중간값이 가장 많은 집합의 곱이 가장 큰 값임을 알 수 있습니다. s가 짝수인 경우는 그대로 중간값들로 이루어진 배열을 리턴하면 되지만 홀수인 경우는 s를 n으로 나눈 나머지 횟수만큼 1씩 더해주어야 합니다. 문제 예시를 예로 들면 n = 2, s = 9일 경우 일단 원소가 s / n인 [4, 4]의 배열을 구성하고 s는 홀수이므로 나머지인 1회만큼 앞에서부터 원소를 1씩 더하면 [5, 4]가 되고 이 집합이 최고의 집합이..

16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 16919. Two Dots 접근한 방법 DFS로 완전탐색합니다. 사이클을 확인하는 방법은 시작 점을 다시 되돌아올 경우이므로 이차원 배열로 모든 정점을 DFS로 탐색해서 탐색 경로가 4회 이상이면서 사이클이 만들어지는 경우를 찾습니다. Python import sys sys.stdin = open("input.txt", "r") # 제거 input = sys.stdin.readline n, m = map(int, input().split()) visit..