본문 바로가기

전체 글

 (346)
[백준] 9251. LCS 풀이 (Python, TypeScript) 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. 적록색약 풀이 (Python, JavaScript) 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 접근한 방법 적록색약인 배열의 R값을 모두 G, 혹은 G값을 모두 R로 바꿔준 후 적록색약이 아닌 배열과 동일하게 탐색을 넣어줍니다. 모든 값에 대하여 방문이 가능한 경우에만 결괏값을 +1카운트한 후 DFS로 상하좌우를 확인해 진입 시작값과 같은 값들을 모두 방문처리 해줍니다. 2번 탐색을 하고나면 적록색약이 아닌 경우와 적록색약인 경우의 결괏값을 얻을 수 있습니다. Python import sys sys.setrecursionlimit(4000) inpu..
[백준] 1339. 단어 수학 풀이 (Python, JavaScript) 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. 연구소 풀이 (Python, JavaScript) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 접근한 방법 dfs를 이용한 조합과 bfs를 이용한 탐색을 이용한 문제입니다. 먼저 벽을 세울 3개의 자리를 순차적으로 구성해봐야 하므로 dfs를 이용해서 3개가 카운트될 때까지 빈칸을 찾아 진입합니다. 3개가 구성되면 bfs를 이용해 바이러스를 퍼트립니다. bfs를 여러번 동작해야 하므로 탐색을 시작할 때 미리 구성된 큐와 연구소 배열을 복사합니다. python에서는 큐는 deque의 copy, 어레이는 copy 라이브러리의 deepcopy를 이용하고 js에서는 어레이만 J..
[백준] 1707. 이분 그래프 풀이 (Python, JavaScript) 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 1707. 이분 그래프 접근한 방법 까다로운 테스트케이스, 조건들이 많아서 풀기에 꽤 재미있었던 문제. 이분그래프는 개념만 보면 한번에 이해하기 어려울 수 있는데 그림으로 표현하면 쉽습니다. 정점을 1 또는 0으로 표현했을 때 같은 집합 안에서 1과 1이 인접하거나 0과 0인 정점이 인접하는 경우가 없다면 이분그래프입니다. 이 그림에서는 왼쪽이 이분그래프, 오른쪽은 아닙니다. 이 아이디어 그대로 모든 정점을 1 또는 0으로 표시해놓을 표시용 배열(코드에서는 ma..
[백준] 16947. 서울 지하철 2호선 풀이 (Python, JavaScript) 16947번: 서울 지하철 2호선 첫째 줄에 역의 개수 N(3 ≤ N ≤ 3,000)이 주어진다. 둘째 줄부터 N개의 줄에는 역과 역을 연결하는 구간의 정보가 주어진다. 같은 구간이 여러 번 주어지는 경우는 없고, 역은 1번부터 N번까지 번호 www.acmicpc.net 16947. 서울 지하철 2호선 접근한 방법 그래프에 존재하는 사이클까지 각 노드가 도달가능한 최소 거리를 구하는 문제입니다. 두 가지 과정이 필요합니다. 1. 사이클 그래프 찾기 2. 사이클 그래프로부터 각 노드 도달거리 탐색하기 1번에서는 DFS로 사이클이 나올때까지 탐색합니다. 사이클을 찾는 방법은 탐색 출발 노드와 다음 탐색 노드가 같은 경우를 찾으면 됩니다. 단 사이클은 노드가 3개 이상이어야 하므로 깊이가 3회이상인 경우에만 ..
[프로그래머스] lv3. 최고의 집합 풀이 (Python, JavaScript) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr lv3. 최고의 집합 접근한 방법 문제 예시들을 보면 곱이 최대인 경우는 항상 0~s의 중간값이 가장 많은 집합의 곱이 가장 큰 값임을 알 수 있습니다. s가 짝수인 경우는 그대로 중간값들로 이루어진 배열을 리턴하면 되지만 홀수인 경우는 s를 n으로 나눈 나머지 횟수만큼 1씩 더해주어야 합니다. 문제 예시를 예로 들면 n = 2, s = 9일 경우 일단 원소가 s / n인 [4, 4]의 배열을 구성하고 s는 홀수이므로 나머지인 1회만큼 앞에서부터 원소를 1씩 더하면 [5, 4]가 되고 이 집합이 최고의 집합이..
[백준] 16919. Two Dots 풀이 (Python, JavaScript) 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..

티스토리툴바