공부의 발자취를 남기는 블로그

문제 분석 문제 목표 : 초침이 시침/분침이 만나는 횟수 구하기 할말이 많은 문제다. 이 문제를 어떻게 접근할것인가 큰 문제다. 결론부터 말하자면, 대부분의 사람들이 이 문제를 "사고력"으로 접근하였다. 즉, 매 초 각도계산하면서 시침/분침과 겹치는지 완전탐색같은건 안돌린다는것이다. => 사고력으로 접근한다는것은 규칙이 있다. 하나의 예시를 줬는데 이걸 잘 이용해 먹어야한다. 간단하게 규칙을 계산해 보자. 1. 1분에 초침은 1바퀴를 돈다. 2. 1바퀴를 돌면, 일반적으로 시침과 분침을 만나게 된다. 3. 즉, 1분이 자나가면 알람이 2번은 울린다. 이 규칙대로면 1시간 = 120번, 24시간 = 2880번이다. 잃어버린 28번은 무엇인가? 이걸 잘 찾아내는것이 문제의 핵심이다. 우선 분침이 정각이 되기..

문제 분석: 1. 석유가 고여있는 부분을 그룹화한다. 2. 주어진 모든 열을 시추를 하였을때, 가장 많이 석유를 뽑을수 있는 열을 고른다. 문제의 독해력도 어렵진 않고 , 구현법은 DFS/BFS 만 알고 있으면 풀 수 있는 문제다. 단, 효율성이 걸려있기때문에 어떻게 완전탐색 로직을 최적화 할지는 고민해봐야한다. 단순하게 생각해서 1번열부터 8번열까지 시추를 시작하여, 석유블록을 발견할때마다 완전탐색(채굴)을 행한뒤 , 가장 높은 석유량을 기록하는 값을 구하면된다. 하지만, 다음과같이 전략을 잡는다면, 이미 1번열에서 채굴한 정보를 2번에서 또다시 채굴을 한다. 즉, 중복이 많이일어난다. 좀 더 효율적인 접근 => 그렇다면 이미 한번 석유채굴한 구역은 메모이제이션 => 어딘가에 저장해둔다. 제일 첫번째 ..

문제 분석 붕대감기 문제 요약 1. 플레이어는 hp가 최대치가 아니면 붕대감기 스킬을 시전한다. 2. 붕대는 1초마다 x만큼 회복하며, 특정한 t초 연속으로 붕대를 감았다면 y만큼 보너스로 회복한다. 3. 공격을 받으면 붕대감기는 취소댄다. 4. 최종적으로 현재 체력을 반환한다. hp가 0이 내려가면 -1를 반환한다 문제 풀이 전형적인 구현 문제이다. 정리해놓은 순서대로 하나씩 구현을 해나가면 된다. 여기서 1초마다 hp를 체크해 나갈것인지, 공격을 받는 구간만 계산하는지 두가지 전략이 있다. 하지만, 1초마다 체크해 나가는 전략은 효율성이 매우 떨어지니, 조금 복잡하더라도 공격을 받는 구간에 hp잔여량을 계산하기로 하자. 우선 hp가 최대치일 경우만 붕대감기를 적용시킨다. 그리고, 공격을 받는 시간과,..

문제분석: 특수조건을 유의하여 최소거리의 갯수 찾기 왜 이 문제는 최소거리의 갯수인가? 자동차는 오른쪽 또는 아래로만 갈수있기때문 위 또는 왼쪽으로 돌아가는 행위는 있을수 없기에, 길이 막히지만 않고 도달한다면 무조건 최소거리다. 특수조건: 0 : 자유로운 통행가능 1: 통행 금지 2: 커브 금지 0과 1인 경우는 간단하지만 2인 경우때문에 로직이 더 복잡해진다. 커브를 금지한다는뜻은, 이전에 온 방향이 왼쪽에서, 또는 위에서 온것인지 판별을 해야하기때문이다. 그래서 거리 방향 판별을 어떻게 할까?? 3차원 배열을 사용한다. 즉, dp[방향][X좌표][Y좌표] = dp[2][N][N] 거리가 0일땐, 모든 방향을 통과하니 (현재 세로방향DP+ 현재 가로방향DP)을 다음 지역에 더해준다. 거리가 1일땐, ..

문제 분석: 목표 : 모든 강철 부대원이 복귀하는 최단 복귀시간 roads는 지나갈수있는 길 sources는 강철부대원이 현재 있는 지역 destination은 복귀해야하는 지점 문제를 읽어보니 그래프 문제다. 그래프 문제도 수많은 푸는 기법이 있다. (최소 신장트리, 다익스트라, 플로이드 와샬..등등) 근데 이 문제는 다익스트라로 푸는게 바람직하다. 그 이유는 도착지가 동일하기 때문이다. "각 병사가 도착지를 향해 가는것"을 반대로 생각하여, "도착지에서 병사가 있는곳으로 간다"로 생각할수가 있기 때문입니다. 다익스트라는 그래프+DP 이기때문에, 써야하는 자료구조가 좀 많다. 문제 풀이: 먼저, 그래프를 표현 해줘야한다. 그래프를 표현해주는 방법은 다양하게 있지만, 필자는 Map으로 표현하였다. Key..

문제분석 연속 행렬의 연산수를 최소화 시키는 문제다. 계산을 할 수 없는 행렬은 입력으로 주어지지 않는게 특징이다. 즉, 연속된 행렬의 인접한 숫자는 무조건 같다. 1. 첫번째 접근 연속된 두 행렬을 merge , 계산하면 인접한 숫자는 사라진다. 즉, 인접한 숫자를 "먼저" 없애면 연산을 최적화 할수 있다고 생각했다. 즉, [5,3],[3,10],[10,6] 이면 인접한 숫자 10을 먼저 소거시키면 적은 연산을 이룰수 있을줄알았다. 1. 인접한 숫자와 위치를 먼저 뽑는다. 2. 인접한 숫자가 제일큰 순서대로 정리한뒤, 그 위치에있는 2개의 행렬을 merge한뒤에 삽입한다. 이 과정을 행렬이 한 개 남을때 까지 반복한다. => 틀림 이유는, 추측이 잘 안되지만.. 인접한 숫자가 가장 큰 순서대로 뽑아 연..

https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제분석 시청자의 동영상 로그를 토대로, 최적의 광고타이밍을 선정해야한다. 동영상 상영시간은 최대 99:59:59 초, 광고의시간은 동영상시간보단 적다. 필자가 처음 접근한 전략 => 이분탐색 으로 최적의 광고타이밍을 구한다 => X 시청자의 동영상로그가 한쪽에 몰려있을수가 있다. 이런경우 이분탐색으로 탐지를못한다. 차선택: => 결국 시청자 동영상로그를 효율적으로 탐색해야한다. => 누적합 개념..

https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제는 매우간단 실제로 나오는 코드도 매우 간단하게 나오긴한다. 근데 문제 -> 코드로 가는 그 사고력.. 그게 어려우니 레벨 4였던것같다. 괄호.. 2쌍이 생겨나는 경우를 한번 살펴보자. 괄호 2쌍은 ()() , (()) 2개의 경우다. (())은 이전 괄호 1쌍에있던 모든 경우를 마치 감싸듯이 나오는 형태고, ()() 는 괄호 1쌍을 2개 붙인경우다. EX) f(1)*f(1) 괄호 3쌍을 살펴..

https://school.programmers.co.kr/learn/courses/30/lessons/140105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제분석: n쌍의 쌍둥이 빌딩이 그림과같은 규칙으로 서있을때, 은비가 바라봣을때 보이는 모습이 몇가지가 존재하는지 반환하는 모습이다. 즉, 은비가 그림과같이 바라보는 모습은 서로다른 쌍이 2개이니, 서로다른 2개의 건물이 겹쳐보이는 n쌍의 빌딩의 경우의수를 구하면된다. 일단 계산값을 100,000,007로 나눠달라는것과 규칙성의 냄새가나면 점화식 DP다. 일반 구현으로 해결할수있는 DP는 조금 ..

그냥 원 사이의 정수 쌍 구하는 문제가 2레벨에 있었던거같은데, 두 원 사이의 정수쌍을 구하는 문제가 나왔다.. (이게 같은 2레벨?) 코딩테스트가 점점 난이도가 높아져가 수능이되어간다..; 문제분석 일단, 하나의 원 안쪽에있는 정수쌍을 구하는법은, 피타고라스의식 x^2+y^2 = r^2 을 쓰면된다. 이것도 기출을 파악해야 바로 떠오르지, 안풀어본사람은 떠오르기 힘들엇을것같다. 그 이유는, r은 문제에서 주었고, X를 0~r 까지 탐색한다 가정하면, y의 갯수가 추정이된다. 즉, y^2= r^2- x^2 (x는 0부터 r까지 인덱스값) 이렇게 식을짜면, x가 0, 1 , 2 ..일때 가능한 y의 0 ,1 , 2의 갯수가 나오게된다. => 헌데 이게 그냥 원 한개의 테두리 포함 문제였다면 쉽겟지만, 두 ..