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

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

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

그냥 원 사이의 정수 쌍 구하는 문제가 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의 갯수가 나오게된다. => 헌데 이게 그냥 원 한개의 테두리 포함 문제였다면 쉽겟지만, 두 ..

https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Level2: 택배상자와 비슷한 문제다. Stack을 사용하여, 보조 컨테이너를 하나더 생산해서 일을 처리하는 부분에서 그렇다. 근데, 이 과제 진행하기가 조금 더 난이도가 있다. 이것저것 할게 많아서 그런거같다. 사전준비: String -> Int 문자열 정리 메소드 , 시간순서대로 정렬 여기서부터 로직 1. 과제진행 2. 과제를 진행하는데 다음 과제할 시간이 되있는지 체크 2-1 . 2번에서..

문제분석 : 문제 푸는 전략은 쉽게 생각할수 있지만, 구현하다보면 빡코딩이 된다. 그래서 만약, 이 문제를 못풀면 심한 자괴감이 들수있다. 그야.. 푸는 방법은아는데 구현을 못하면 그만큼 억울한 상황이 없으니.. 1. BFS 전략 사용하기 2. BFS 전략을 사용하여 최소거리를 구하는건 맞되, 리코쳇 로봇은 벽 , 장애물을 부딪힐때까지 움직인다. 즉, 원래 BFS는 4방향으로 1칸씩 움직여 도착하는 장소를 결정하지만, 이 문제는 4방향으로 몇칸씩 움직일지 매순간 미지수이므로, 움직여 도착하는 장소를 세밀하게 개선해야한다. 요약하자면 BFS전략에 이동하는 로직만 변경하면되는데, 막상 코딩을해보면 많이 버겁다. 문제풀이: BFS의 기초 방문체크와 Que를 선언했다. 방문체크는 재 방문을통해 무한루프를 방지함..

문제분석: 전형적인 스케쥴링 문제이다. 제일 쉽게 푸는방법은 0시부터 24시까지 1분마다 체크하여 입실,퇴실조치를 하면 편하다. 근데, 이 방법은 효율성이 매우 나쁜건 누구나 아는사실이고 실제로 이방법보다 효율성 좋게 스케쥴링하는방법이 널렸다. 근데 이 문제는 앞선 방법으로해도 풀린다... 그래도 귀찮터라도 효율적인방법으로 접근했다. 전략: 실제로 인간이 스케쥴링했을때 시뮬레이션대로 코드작성 말 그대로, 인간이 스케쥴했을때를 가정하여 짠다. 1. 우선 입실시간순 대로 정렬한뒤, 입실처리를한다. 2. 만약 퇴실시간이 되면 퇴실한다 But, 우리는 1분마다 체크를하는 방법은 포기했으니 다른 방법으로 퇴실시간을 체크한다. Arrange 2 : 이후에 입장할 사람의 입장할 시간보다 적은 퇴실시간은 퇴실조치한다...

문제분석 완전탐색의 국룰과 같은 4방향 탐색 문제다. 문제대로 상, 하 ,좌, 우를 탐색해가며 식량을 더해가면되지만, 여기서 특수한룰이, 섬이 분리되어있으면 섬마다 식량의 갯수를 구해줘야한다. 우선 4방향 완전탐색에서 해야할일은 다음과같다. 1. 방문을체크할 boolean[][] -> 방문체크를안하면 무한루프를 돈다. 2. 재귀를 돌릴 재귀메소드 작성. -> 재귀의 탈출 및 예외조건을 유의해야한다. 3. 추가로 이 문제에서 묻는 섬마다 분리시키는법 우선 분리한 아일랜드의 식량합계를 담는 island 배열과 식량의 합계를 저장할 sum과 방문을 체크하는 visited를 선언했다. visited는 섬의 크기만큼 늘려준다. 이제 하나의 섬을 탐색할 스타팅 포인트를 찾을것이다. 포인트가 "X"가 아니면 숫자니,..

문제분석 딱 보자마자 DP 문제임을 눈치채면 성공 근데 필자는 BFS로 풀었다. 뭔가 BFS가 좀더 효율적인거같아서 햇는데, 결국 빅데이터일수록 DP가 더 빠르더라.. BFS는 레벨을 기준으로 너비탐색을 한다. 필자는 레벨을 연산횟수와 동일하게보고 BFS를 진행했다. 같은 연산을 여러번하는걸 막기위해 Boolean체크도 잊지않게 해주면된다. 전체 풀이 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 import java.util.*; class Solution { public int solution(int x, int y, int n) { int answer = 0; if(x==y){ retu..

문제분석: 아주 간단한문제다 각 인덱스마다 뒤에있는 더 큰 숫자를 반환하고, 없으면 -1를 반환하면 간단한 문제이지만.. 제한사항을 보면 길이가 100만이다. 이걸 보고 빠르게 2차반복문으로 쉽게 풀생각을 접어야한다. 어떻게든 1차 반복문으로 문제를 해결하자. 1차반복문으로 해결하려면 다음과 같은 정보가 필요하다. 1. 해당 인덱스의 숫자가, 앞의 숫자들에게 영향이 끼치는지? -> 예를들어, 3 3 5 6 과같은 숫자배열에서 5인숫자가 앞의 숫자들 3 에게 영향이 간다. 2. 해당 인덱스의 숫자가, 뒤의 숫자보다 작은지? -> 예를들어 3 3 5 6 과 같은 숫자배열에서 5인 숫자는 앞의숫자 6보다 작다. --> 1번을 해결하기위해 Stack이란 배열을 사용했다. 필자는 스택에 int[] 배열로 {해당 ..

문제분석 문제는 매우 간단하다 서로다른 weights 2개를 골라서 그 경우가 총 7개의 케이스 4:3 ,4:2,3:2, 1:1 ,2:3, 3:4, 2:4 인 경우를 판단하면된다. FirstTry : 문제대로 풀기 그냥 문제대로 풀었다. 2차 반복문으로 서로다른 사람의 몸무게를 2개 골라 case를 판별한다. case의 부합한다면 answer++를 증가시키는 간단하게 구현했지만.. 효율성에러 문제 풀고보니 제한사항이 사람의 몸무게 갯수가 10만까지 간다. 구글에 쳐보니 10만*10만이 100억이라고 한다. 당연히 걸릴만한 시간복잡도다.. Second Try: 1차 반복문으로 줄이기 1차 반복문으로 줄여서 구현해야한다. 여기서 생각난게 Arr또는 Map을 구현해서 정보를 저장해두는게 현명하다 보았다. 그 ..