개발조아

문제 링크 : https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net MST 문제이다. 다른 변형 없이 크루스칼 알고리즘으로 풀면 된다. 이때 사이클 체크는 유니온-파인드 알고리즘으로 해결하면 된다. 이때 파인드 과정에 경로 압축을 수행하자. from sys import stdin input = stdin.readline n = int(input()) m = int(input()) edges = [tuple(map(int, input().split())) for _ in range(m)] edges.sort(key=lambda x:x[2])..

문제 링크 : https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net 백트래킹, 구현 문제이다. 문제에 요구하는게 많아서 소스가 길어졌다. 우선 나는 물고기가 저장된 배열, 냄새를 표시한 배열 두개를 사용 했다. 물고기를 저장한 배열은 2개의 원소를 갖는다. 0번째 현재 해당칸에 있는 물고기 1번째 복제될 물고기 그래서 문제의 5번단계에서 1번째 값의 물고기들을 0번째 값에 추가해줬다. 냄새를 표시한 배열은 물고기가 ..

문제 링크 : https://www.acmicpc.net/problem/23289 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기 www.acmicpc.net 구현문제이다. 온풍기에 의한 온도 조절은 바로 적용해도 되지만 온도차에 의한 온도 조절은 한번에 진행되야한다. 그래서 나는 2차원 배열에 3개의 원소를 넣었다. 현재 온도, 현재 지점에 들어온 온도, 현재 지점에서 나간온도 들어온 온도는 주변 다른 칸에 의해 현재 칸이 높여진 값을 누적한다. 나간 온도는 주변 칸의 온도를 높였을 때 그 높인 값을 누적한다. 그리고 주의해야할 점이라면..

문제 링크 : https://www.acmicpc.net/problem/23288 23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net BFS + 구현 문제이다. 주사위 굴리는게 귀찮은 문제이다. 주사위만 잘 굴리면 어렵지 않게 풀 수 있는 문제이다. 나는 주사위를 배열로 할까하다가 dict로 보기 편하게 했다. 진행 순서는 다음과 같다. 1. 주사위 굴리기 2. 주사위 회전 3. BFS로 칸 개수 세기 4. 점수 갱신 위의 순서로 k개만큼 반복 하면 된다. 1. 주사위 굴리기 주어진 전개도 보고 ..

문제 링크 : https://www.acmicpc.net/problem/15787 15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 비트 연산, 비트마스킹 문제이다. 명령 1은 해당 자리 비트를 1로 변경한다 명령 2는 해당 자리 비트를 0으로 변경한다 명령 3은 왼쪽 쉬프트 연산이다 명령 4는 오른쪽 쉬프트 연산이다. 주의 할점이 있다. 1. 쉬프트 연산 방향 - 비트는 오른쪽에서 왼쪽으로 순서이므로 방향에 주의하자. 2. 왼쪽 쉬프트 연산 좌석은 최대 20개 이다. 만약 20번째 좌석에 승객이 앉..

문제 링크 : https://www.acmicpc.net/problem/15961 15961번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2 www.acmicpc.net 투 포인터로 해결가능하다. 두개의 포인터(left, right)의 간격을 k로 유지하면서 진행하면 된다. 주의점은 끝나는 시점이다. right가 한바퀴 돌고 다시 right로 오는 시점까지 즉, 같은 구간으로 올때 까지 검사해야한다. 왜냐면 원형으로 이어진 회전초밥이기 때문이다. 이 부분을 놓쳐서 계속 틀렸다. 예를 들어 1 2 3 4고 ..

문제 링크 : https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 나는 BFS로 풀었고 방문체크는 해당 칸을 방문했을 때의 체력을 기록했다. 그래서 다음번에 다시 방문했을 때 해당 칸보다 체력이 높아야 이동이 가능하게 했다. 더 낮은데 해당 칸으로 이동해봐야 기존의 방문했을 때보다 적게 가기 때문이다. BFS 진행시 범위 안에 들어왔을 때 조건들을 체크한다. 만약 E점이라면 종료한다. 아니라면 다음 점이 우산이라면 현재 내구도를 d로 바꾼다. ..

문제 링크 : https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 건물의 개수가 최대 100개고 모든 건물사이의 최단 거리를 구해놓으면 쉬우므로 플로이드 와샬로 해결하였다. 입력으로 반은 건물로 배열을 구성하는데 가중치는 1로 넣자 그리고 플로이드 와샬로 각점에 대해서 최단거리를 구해 놓자. 다음 치킨집을 지으려는 매장 두곳을 골라야한다. 이중포문으로 골라도 되지만 귀찮으니 combinations을 사용했다. 두개의 ..