개발조아

문제 링크 : https://www.acmicpc.net/problem/1553 1553번: 도미노 찾기 도미노의 크기는 1×2이고, 크기가 1×1인 칸으로 나누어져 있다. 칸은 수를 나타내며, 위와 같이 총 28가지가 있다. 크기가 8×7인 격자가 있고, 격자의 각 칸에는 정수가 하나씩 들어있다. 위의 도 www.acmicpc.net 도미노를 놓는 방향은 ㅡ ㅣ 두가지 모양밖에 없다. (0,0)부터 두 방향으로 묶어서 백트래킹으로 완탐해보자. 도미노를 (0,0)에서 (7,6)까지 순차적으로 확인하면 되므로 왼쪽이나 오른쪽을 향하도록 놓지 않아도 된다. 그래서 나는 처음에 오른쪽방향으로 도미노를 만들어 보고 다음 아래쪽 방향으로 도미노를 만들어 봤다. 이때 이미 사용한 도미노인지, 해당방향의 칸에 번호를..

문제 링크 : https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 브루트포스 문제이다. 재귀로도 할수 있겠지만 파이썬은 이미 아주 훌륭한 조합를 제공한다. 1개,2개,n개까지 뽑는 조합을 다 만들어서 조건을 만족시키고 합이 최소가 되는 것을 찾아서 출력했다. 그리고 중간이 합이 같다면 사전순으로 앞선것이 와야한다. 그래서 두개를 하나의 튜플로 만들어 정렬하고 앞에것을 저장했다. from sys import stdin from itertools i..

문제 링크 : https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 브루트포스, 백트래킹 문제이다. 나는 연산자 끼워넣기랑 유사하게 풀었다. https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개..

문제 링크 : 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/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이므로 배열에 다 넣고 돌리면 당연히 시간초과가 난다. 그러니 물고기에만 주목하면 된다. 모든 물고기에 대해서 그 물고기가 그물 테두리에 겹치도록 그물을 펼친 후 그 범위안에 들어오는 물고기를 세주면 된다. 현재 물고기의 좌표를 끝점, 현재 그물의 크기만큼 뺀값을 시작..

문제 링크 : https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 백트래킹, 브루트포스 문제이다. 1~N까지 숫자들 사이에 연산자 '+','-',' ' 중 한가지를 반드시 넣고 결과를 계산해서 그 값이 0인 것의 식을 출력하는 것이다. ' '의 경우 두수를 붙이는 것이다. 연산자들을 모두 넣고 마지막에 계산해야한다. 중간중간에 계산한다면 더 복잡해질 것이다. 1-2 3 같은 경우가 힘들듯하다. 그래서 모든 자리에 다 연산자를 넣고 마지막에 값만 계산해서 확인하면 된다. 연산자 넣는 것은 간단한 백트래..

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 질문하기에 너무 공감됐던 글이다. 1,2주차는 쉬웟는데 갑자기 너무 어려워졌던 문제였다. 올해 LG CNS 8월 입사자 4번 문..