안녕

0. 문제 링크 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 1. 풀이 방법 우선 특정 좌표를 기준으로 같은 색깔인 그룹을 만든다. 이건 적록색약과 일반인 두 개로 나눠서 하면 되고, 그룹을 만들다가 같은 색이 아닌 색깔을 만나면 check 변수에다가 -1을 집어 넣는다. check가 0인 곳은 탐색할 필요가 있는 곳으로 0이 아닌 좌표는 탐색할 필요가 없다. 이미 그룹화 되어 있으므로 탐색할 필요가 없는 것 아무튼 2중 for lo..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 1. 풀이 방법 + 23.02.04에서 문제를 다시 채점하니 시간 초과가 났습니다.ㅜ 이 문제를 보고 맨 처음 떠오른 생각은 다익스트라였다. 최단 거리를 먼저 찾고, 최단 루트에서 방향이 바뀌는 부분이 거울이니까 그만큼 하면 되겠지 라는 생각을 했다. 하지만 이런 생각은 틀린게, 최단 루트가 최소 거울 개수를 보장하지 않는다! 아래 예시를 보자.. 중간으로 가는 루트가 가..

0. 문제 링크 https://www.acmicpc.net/problem/5014 1. 풀이 방법 BFS를 사용해서 푸는 문제 현재 층과 목적 층이 같다면 끝 그게 아니라면 U만큼 위로 가거나, D만큼 아래로 가면 됨 범위를 벗어나면 안 되고, 이미 방문한 곳을 또 방문하면 안 됨 2. 코드 from collections import deque F, S, G, U, D = map(int, input().split()) if S == G: print(0), exit(0) # 현재 층과 목적지가 같다면 끝 board = [*range(0, F + 1)] board[S] = 0 dy = [U, -D] # U만큼 위로 가거나, D만큼 아래로 가는 것 dq = deque([[S, 0]]) while dq: y, ..

0. 문제 링크 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 1. 풀이 방법 TSP로 문제를 풀었음 BFS를 사용하여 청소기와 쓰레기들의 거리, 쓰레기들 사이의 거리를 모두 파악함 이후 순열을 사용하여 청소기와 쓰레기를 한 줄로 잇는 최단 거리를 파악함 그러나 효율성이 낮으므로, 이 방법 대신 다른 방법을 사용하면 좋을 듯 다른 방법으로는 각 쓰레기에 먼저 방문하는 노드의 경로들을 저장해서 처리하는 방법이 있음 이때 중복은 넣지 않고, (왜냐면 BF..

0. 문제 링크 https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 N개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 1. 풀이 방법 각 구역을 그룹화 한 다음에 처리함 또한 인접한 그룹 번호도 넣어서 최댓값을 찾음 비트마스킹을 써서 벽의 위치를 파악함 cnt는 특정 구역의 블록 갯수이고, adj는 특정 구역의 인접한 구역의 인덱스를 넣어놓았음 check는 블럭의 그룹을 적어놓은 리스트임 참고로 한 구역에 블럭이 하나만 있는 경우를 대비해서, 시작과 동시에 블럭에 그룹 번호를 부여하였음 다만..

0. 문제 링크 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 1. 풀이 방법 에라토스테네스의 체로 소수들을 먼저 찾아놓음 그리고 각 자리수를 추출해서 풀었음 1, 10, 100의 자리 숫자는 0이 되어도 상관이 없지만, 1000의 자리는 0이 되면 안 됨 따라서 반복을 1, 10, 100은 합쳐서 27번, 1000의 자리는 8번 반복해야 함 아무튼 만약 1의 자리가 3이라면 -2, -1, 1, 2, 3, 4, 5, 6 이렇게 원래 숫자에 더하도록 구..

0. 문제 링크 www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 1. 풀이 방법 단순 BFS를 하면 되는데, 추가로 내가 이미 방문한 곳보다 말을 적게 탔을 경우도 생각해봐야 한다. 또한 임계치보다 말을 적게 탔을 경우에는 말을 추가로 탈 수 있도록 처리함 아래에서 check 변수는 어느 지점까지 말을 탄 횟수이고, cur_k는 현재 내가 말을 탄 횟수 그 외엔 특별한 점 없음 2. 코드 import sys from collections im..

P = NP임을 증명하려면 NP에 속한 각각의 문제에 대해 문제를 풀 수 있는 다항 시간 알고리즘을 찾아야 합니다. 하지만 이 작업은 단순화할 수 있습니다. 즉, 많은 문제 중에서 하나만 다항 시간 알고리즘을 찾으면 됩니다. 하나만 다항 시간 알고리즘을 찾으면, 나머지 문제들도 마찬가지로 P에 속하게 되는 NP-Complete에 대해 알아보겠습니다. 우선 알아보기 전에 이론의 기초가 되는 CNF-Satisfiability에 대해 알아봐야 합니다. 그리고 마지막으로 지금까지 결정 문제에 대해서만 NP, P를 따졌는데, 이제는 최적화 문제까지 확장한 NP-Hard에 대해서도 알아보겠습니다. 1. CNF-Satisfiability CNF ~ 는 Conjunctive Normal Form의 약자로, 논리식 사이..

이전 글의 Halting Problem을 기억하시나요? 이처럼 진위 판별을 불가능한 문제가 있고, 진위 판별이 불가능한 문제가 있습니다. 간단하게 진위 판별 문제(결정 문제)로 NP를 제한하면 이론을 전개하기가 쉬워집니다. 우선 결정 문제를 한 번 알아봅시다. 1. Decision Problem 그러기 위해선 우선 지금까지 해온 모든 알고리즘들, Decision Problem과 Optimization Problem에 대해 생각해봐야 합니다. 최적화 문제란 답이 최적해라는 말입니다. 하지만 최적화 문제는 결정 문제로 만들 수 있습니다. 참고로 결정 문제는 yes or no 두 가지 정답만 내놓습니다. 예를 들어서, TSP 문제를 생각해봅시다. 우리는 최소 거리를 구하는 알고리즘을 구현했지만, 만약 특정 거..

새로운 알고리즘을 개발할 때, 이 알고리즘이 다루기 어렵다는 것은 무엇을 의미할까요? 현실에서 다루기 어렵다는 것은 취급하기 또는 작업하기 어렵다로 정의하지만, 컴퓨터 과학에서 다루기 어렵다는 것은 "해당 문제를 다항시간(Polynomial-time)에 풀 수 없다"를 의미합니다. 즉 알고리즘의 Worst Case W(n) = O(p(n)) 만족하는 다항식 p(n)이 없다는 뜻입니다. 다항 시간안에 풀 수 있는 알고리즘은 2n, 3n^3, n lg n등이 있습니다. n lg n은 n에 대한 다항식은 아니지만, n lg n < n^2에 의하여 다항시간 알고리즘으로 분류합니다. 따라서 컴퓨터 과학에서 문제가 다루가 힘들다는 것은 특정 알고리즘의 성질이 아니라 문제의 성질이 되어야 합니다. 사실 최악 시간 복..