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

문제분석 이 문제같은경우는, 정보처리기사 지식을 요구하는 문제입니다. 혹여나 시험보다가 모르겠다하면 인터넷 검색하면 물론 나오긴합니다. 문제에서는 캐시 교체(페이지 교체)알고리즘인 LRU를 사용하라고 하엿습니다. LRU가 도대체 뭐길래? Least Resently Used로 가장 최근에 썻던걸 쓰겠다란 말인데.. 이걸 반대로생각하셔야합니다. 가장 최근에 있는걸 쓴다는건, 가장 안쓰는건 먼저 삭제가됩니다. 처음 문제를 접할때 또한 cache hit 과 cache miss입니다. cache miss란 주어진 캐시크기 안에 해당 정보가 없으면 Miss가 발생합니다. cache hit이란 주어진 캐시크기 안에 해당 정보가 있으면 Hit이 발생합니다. 즉, 캐시크기는 리스트의 사이즈입니다. 예시를 한번 보겠습니다..

문제분석: 문제 목표 : 각 시간대별로 주식이 떨어지지않는 시간을 구하자 이 문제를 풀기에 앞서.... 이 문제는 스택/큐로 푸는게 맞습니다. 하지만 2중반복문으로 풀리는게 참으로 이상합니다. 사실 2중반복문으로 생각해서 푸는게 제일로 쉽습니다. 거의 Level1 수준으로 말이죠. 그냥 단순하게 1초일때 주식가격 을 n번 돌려서 깍이는 구간을 확인하고 2초일때 주식량을 n번 돌면서 깍이는 구간확인하고 3초일때 .... 하면 n^2걸려서 구합니다. 근데 문제제약을 보면 prices의 길이가 10만입니다. 최대 n^2이 걸리는 문제를 10만^2을 하면 무려 100억번입니다. 근데 이 문제가 2중반복문으로 구현하면 풀립니다. 심지어 효율성테스트도 스택보다 빠릅니다 (아니..대체 왜..??) 바뀐거 아닙니다. ..

문제분석 목표 : 끝말잇기를 진행하여 탈락하는 사람의 차례와 번호를 출력하라 끝말잇기에 탈락하는 조건은 2가지입니다. 1. 이전에 나왔던 마지막글자의 끝말을 잇지 못할경우 2. 이제까지 나왔던 단어들을 중복으로 말할경우 이 2가지 경우중 하나일경우 탈락하게됩니다. 그리고 탈락할경우의 턴은 i/n +1을하면 출력이되며, 탈락한 사람의 번호는 i%n +1을하면 구할수있습니다. (i 는 word[]의 인덱스) P.s 자료구조를 몰라도 풀수있는 쉬운 Level2문제인것 같습니다. 문제풀이 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 import java.util.*; class Solution { public int[] solution(i..

문제분석 목표: 삼각달팽이의 규칙에의해 새롭게 탄생한 배열 출력하기 문제의 규칙은 이렇다. 높이가 n이 주어지면, n만큼 내려온후 방향을 오른쪽으로 바꾼다. 그리고 n의 길이만큼 이동한뒤 왼쪽 대각선으로 바꾼다. ->이를 반복함 이를 배열과 코드로 표현해보면, 내려올때는 배열의 y값을 늘리면된다. arr[i][j] -> arr[i+1][j] 오른쪽으로 이동할때는 배열의 x값을 늘리면된다. arr[i][j]-> arr[i][j+1] 대각선 왼쪽으로 이동할때는 배열의 x,y를 하나씩 줄이면된다. arr[i][j]-> arr[i-1][j-1] 여기까지 알면 나머지는 쉽다. 만약 n이 4면 4만큼 내려오고 3만큼 오른쪽 2만큼 대각선 1만큼 내려온다. 만약 n이 5면 5만큼 내려오고 4만큼 오른쪽 3만큼 대각선..

문제분석 문제 목표: 0과 1로 이루어진 배열이 주어집니다. 1.만약 모든배열이 0 또는 1로 전부 채워져있으면 압축합니다. 2.전부 채워져있지않으면, 배열을 4등분한뒤 1번을 반복합니다. 0과 1의 갯수를 구해주세요. 그림을보면 계속 4등분하는 로직을 '반복'하는걸 주목하셔야합니다. 무슨 알고리즘을 써야하는지 감이 오셧겟지만, 재귀함수를 사용해야합니다. 코드를 보면서 문제에대한 접근을 설명하겟습니다. 우선 메인함수와 전역변수입니다. 전역변수의 zero 와 one은 각각 0의 갯수와 1의 갯수입니다. rec();를 호출하고 zero와 one의 갯수를 세줍니다. 그래서 rec()를 보시자면 문제를 읽어보시면 1.먼저 1또는 0으로 배열이 모두 채워졋는데 확인한다. 2.만약 모두채워지지않았다면 4등분한뒤 다..

문제분석 문제목표: 데이터를 탐색해서 후보키의 갯수를구하자. 특징: 후보키를 구하기위해서 유일성과 최소성이 만족되어야한다. 데이터베이스의 기초지식이 갖추어져있다면 익숙하겠지만, 모르면 좀 난감하게 와닿을수있다. 유일성: 유일하게 식별이 가능한상태 , 즉 이 튜플로 모든데이터를 구별이 가능해야한다. 더 쉽게말하면 중복이 단 하나도없는 컬럼이여만한다. 최소성: 예시로 설명하자면, A={1,2} B={1,2,3} 이면 최소성이 깨진다. 그 이유는, A가 이미 {1,2}로 유일하게 식별이가능한데, B={1,2,@}는 볼필요도없이 유일하게 식별이가능하다. B와같은 쓸데없는 후보키를 제거하는것이 최소성이라고한다. 즉, 어떤 컬럼의조합이 다른 컬럼에 포함되면 안된다. 문제를 읽어보면 우리가 필요한게 컬럼들의 모든 조..

https://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 문제가 길어 링크로 대체합니다. 문제분석: 목표: 라이언과 어피치의 과녁점수가 최대일때 맞춘 과녁의 점수판을 반환해주세요. 특수조건: 1. 라이언과 어피치가 동점일경우, 어피치의 승리입니다. 2. 어피치가 승리할경우 -1을 반환 3. 만약, 과녁점수가 동일한기록이 여러개 존재할경우, 낮은 점수를 많이 맞힌것을 정답으로합니다. 이 문제가 정말 어렵다고 느끼게하는건 바로..

문제분석: 요구사항: 1. 영역은 몇개인가? 2. 영역중에서 가장 많은넓이를 차지하는값은 무엇인가? 보는바와 같이, 완전탐색을 행해야한다. 모든 영역을 탐색한뒤에 영역을 나누고, 영역의 넓이를 더해야한다. 완전탐색을 쓰기전에 DFS, BFS 둘중 하나를 골라야한다. 필자는 여기서 DFS를골랐다. DFS는 재귀 , 스택을 사용하니 비교적 깔끔한 코드가 나온다. 먼저 DFS를 쓰기위한 재료? 들을 준비해야한다. 뒤에서 쓸 재귀함수의 파라미터를 깔끔하게 하기위해서 필요한 재료들은 미리 전역변수로 올려놨다. v 와 h는 너비와 높이제한을 위해서, visited는 이미 체크가 완료된 블록을 중복체크를 방지하기위해서 target은 같은영역만을 체크하기위한 기준을 잡기위해 board는 picture과 동일한기능이지만..

문제의 이해 이 문제는 어느한 숫자 x를 2진법으로 치환한뒤, 그 2진법의 비트 1~2개가 다르며 보다 큰 수를 찾는 문제입니다. 비트가 1~2개 다르며 큰 수를 찾는방법을 찾는건 처음 생각하기에 매우 까다롭습니다. 따라서 차근차근 하나씩 경우의수를 찾아가며 규칙을 찾는게 중요합니다. 1.뒷자리가 00일경우 : 뒷자리가 00일경우, 바로 다음숫자가 조건에맞는 숫자입니다. EX) 100 ->101 비트가 1개다르며 큰 수 2.뒷자리가 01일경우 : 뒷자리가 01일경우, 바로 다음숫자가 조건에 맞는 숫자입니다. EX) 101->110 비트가 2개 다르며 큰 수 3.뒷자리가 10일경우 : 뒷자리가 10일경우 , 바로 다음숫자가 조건에 맞는 숫자입니다. EX) 110->111 비트가 1개 다르며 큰 수 4.뒷자..

https://programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제가길어서 링크로 대체합니다. 문제분석 구현을 해야할것은 딱 3가지입니다. 1. 제거할 4블록을 확인하는 로직 2. 제거할 4블록을 삭제하는 로직 3.제거한 공간을 아래로 내리는 로직 이 3가지로직을 While 반복문에 넣으면 우리가 원하는 기능이 만들어집니다. 1. 제거할 4블록을 확인하는건 i행 j열 블록을 남은 3블록과 같은지를 체..