개발조아

문제 링크 : https://www.acmicpc.net/problem/5670 5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 문제 등급은 높지만 어렵지 않은 문제이다. 핵심은 트라이 자료구조를 사용하는 것이다. 현재 문자에서 이어질 다음 문자를 다 저장했다가 사용해야므로 트리구조가 떠올랐고, 그중 다음 글자를 자식 노드로 저장하는 트라이가 떠올랐다. 우선 입력으로 들어온 단어를 모두 트라이로 구성하자. 이때 해당 글자에서 단어가 끝난다는 표시를 해주자. 다음은 루트 노드의 자식 글자에서 시작해서 재귀로 탐색하면..

문제 링크 : https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net MST 문제이다. 나는 크루스칼로 풀이 했다. 문제는 마을을 두개로 분리하고 두부분의 가중치의 합이 최소가 되어야한다. 정점을 n이라 했을 때 n-2개의 간선은 고르면 된다. MST 문제를 풀때 n-1개의 간선을 고르면 된다. n-1개를 고르면 하나의 그래프가 탄생하고 사이클이 형성되지 않은 상태이다. 이때 간선을 하나 지우면 두개의 그래프가 나..

문제 링크 : 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://programmers.co.kr/learn/courses/30/lessons/87694 코딩테스트 연습 - 11주차 [[1,1,7,4],[3,2,5,5],[4,3,6,9],[2,6,8,8]] 1 3 7 8 17 [[1,1,8,4],[2,2,4,9],[3,6,9,8],[6,3,7,7]] 9 7 6 1 11 [[2,2,5,5],[1,3,6,4],[3,1,4,6]] 1 4 6 3 10 programmers.co.kr 내풀이의 핵심은 사각형을 확대 해보는 것이다. 우선 두가지 배열을 사용했다. 사각형의 올라가있는 공간을 표시한 2차원 배열 board 사각형이 올라간 공간이 테두리인지 사각형의 안쪽인지 표시한 3차원 배열 in_out_board 사각형은 최대 4개 이므로 해당 점이 어..

문제 링크 : https://www.acmicpc.net/problem/20207 20207번: 달력 수현이는 일년의 날짜가 1일부터 365일로 표시되어있는 달력을 가지고있다. 수현이는 너무나도 계획적인 사람이라 올 해 일정을 모두 계획해서 달력에 표시해놨다. 여름이 거의 끝나가자 장 www.acmicpc.net 나는 누적합을 활용하였다. 달력의 시작일자에 +1 종료일자+1 에 -1을 해주었다. 해당 일자의 누적합이 사각형의 높이가 될 것이다. 그리고 1~366까지 누적합을 확인하면서 가로,세로 크기의 최대값을 갱신했다. 더보기 누적합 간단히 설명하면 아래와 같다. 입력이 7 2 4 4 5 5 6 5 7 7 9 11 12 12 12 라고 해보자. 시작일에 +1 종료일+1에 -1을 해준다 했다. 그럼 배열..