개발조아

문제 링크 : https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 2차원 배열을 규칙에 바깥부터 한꺼풀씩 돌리는 것이다. 반시계 방향으로 돌리는 것이다. 그냥 쉽게 숫자 하나씩 반시계방향으로 한칸씩 밀면서 하려고 보니 최대 10^9 만큼 돌려야한다. 그러므로 한바퀴 돌릴때 원소의 개수를 구해서 모듈러 연산을 이용하여 횟수를 줄이자. 4x4 행렬일 경우 첫..

문제 링크 : https://www.acmicpc.net/problem/16434 16434번: 드래곤 앤 던전 첫 번째 줄에 방의 개수 N (1 ≤ N ≤ 123,456) 과 용사의 초기 공격력 HATK (1 ≤ HATK ≤ 1,000,000) 가 주어집니다. i+1번째 줄엔 i번째 방의 정보를 나타내는 세개의 정수 ti, ai, hi (ti ∈ {1, 2}, 1 www.acmicpc.net 이분 탐색으로 풀었다. 최대 HP는 모든 칸이 다 몬스터이고 모든 애들의 공격력과 체력이 1백만이라 했을 때 123456*1백만*1백만이다. 1~최대 HP까지에서 이분탐색으로 hp찾아보자. hp를 선택했으니 시뮬레이션 돌려보자. 만약 돌린 결과가 False가 나온다면 선택한 hp로는 부족하다는 뜻이다. 그러므로 m..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr 문제는 간단하다. 좌표를 주고 이를 이진트리로 구성해서 전위,후위 탐색을 수행한 결과 값을 내놔라 이다. 트리 구성은 재귀로 구현했다. 우선 좌표를 정렬했다. y는 작아지게 x좌표는 커지게 정렬하게 되면 부모 노드부터 순서대로 정렬이 된다. 그리고 가장 첫번째 값이 부모노드가 된다. 이제 부모노드를 트리에 넣고 시작한다. 왼쪽은 자신보다 y 좌표가 ..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 막상 풀고보니 그렇게 어려운 문제가 아닌듯 했다. 물론 생각하는데 좀 걸렸지만, 그래도 두시간정도 걸린듯 하다. 로봇을 상하좌우, 회전하여 n,n칸으로 이동할 때 최소 시간을 구하는 문제이다. 로봇의 좌표가 두개이고 n의 크기가 100으로 작아서 4차원 배열로 방문 체크를 했다. 최소 시간을 구하라해서 BFS를 이용했다. 로봇의 이동은 그냥 두좌표 동시에 상하좌우 이동시키고 유..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 그리디하게 dist를 정렬해서 가장 긴 것 부터 풀면 되지 않을까 했다가 계속 틀렸던 문제이다. weak = [0,10,30,50,100,120] dist = [5,10,50,100] 이 경우 답은 1이다 weak가 100인 점에서 길이가 100인 친구가 돌면 된다. 그래서 브루트포스로 해결하였다. dist의 순서를 섞고 0번째부터 그 순서대로 다..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제의 설명은 어렵지 않았다. 처음에는 word에 ?를 하나씩 붙여서 가능한 경우를 다 만들고 그것을 키로하고 값은 개수로 하는 딕셔너리로 만들었었다. 그리고 쿼리문을 키로해서 딕셔너리를 확인했다. word의 길이는 최대 10000자이고, 모든 가사의 길이의 합이 1백만자 이하 이므로 되지 않을까 했다. 근데 문자를 이어붙이는 과정에서 슬라이싱이 많이 들어가서 효율성 테스트에서 틀리지 않았나 싶다. 그래서 해설을 봐보니 트라이 자료구조를 사용해야한다고 한다. 문자열을 트리 구조로 저장해서 단순 비교해서 검색하는 경우 훨씬 빠르다..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 브루트포스로 해결했다. 열쇠의 칸중 최소 한개가 자물쇠에 올수 있도록 범위를 확장해서 열쇠를 올려보면 된다. 문제의 테케 1번으로 설명하면 아래와 같다. key는 3x3이고 lock는 3x3이다. lock에 key의 최소 한칸이 오려면 key의 크기의 -1만큼 왼쪽위로 범위를 확장하고 올려보면 된다. 위 그림처럼 3x3 lock를 -2,-2에서 2,2까지 있는 5x5범위로 확장하여 열쇠를 올려본다..

문제 링크 : https://www.acmicpc.net/problem/7573 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 문제는 간단하지만 겨우겨우 18번만에 푼 문제이다. 풀다풀다 모르겠어서 다른분들의 알고리즘을 참고하고 해결하였다. N이 10000이므로 배열에 다 넣고 돌리면 당연히 시간초과가 난다. 그러니 물고기에만 주목하면 된다. 모든 물고기에 대해서 그 물고기가 그물 테두리에 겹치도록 그물을 펼친 후 그 범위안에 들어오는 물고기를 세주면 된다. 현재 물고기의 좌표를 끝점, 현재 그물의 크기만큼 뺀값을 시작..