tony1724 님의 블로그

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/60059 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :자물쇠의 빈 공간에 열쇠의 돌기가 맞아야 한다.자물쇠의 돌기와 열쇠의 돌기가 맞닿으면 안 된다.키는 특정 부분만 사용하여 자물쇠를 열 수 있다. 문제 풀이 시간 : 1시간 30분문제 성공 여부 : 성공 접근 방법(성공) :자물쇠에 대해 가능한 모든 열쇠 모양을 시뮬레이션 다음과 같은 키와 자물쇠가 주어진다고 보자. 자물쇠에 대해 모든 key 모양을 다 대입시키려면, 적어도 키의 한 칸은 자물쇠와 맞물려야 한다. 따라서, 자물..

문제 설명 : https://www.acmicpc.net/problem/14003 문제 요약 :수열 A에 대해 가장 긴 증가하는 부분 수열 구하기수열의 길이와 수열을 출력문제 풀이 시간 : 1시간문제 성공 여부 : 실패 접근 방법(성공) :이전 수열 중 가장 긴 수열(마지막 값이 현재 인덱스값보다 작은 수열)의 길이(idx)에 대해 그 최솟값을 저장하는 dp 배열 (수열의 길이)각 인덱스 별 자식의 수 저장 배열 (역추적) [10 20 8 30] 이라는 배열이 있다.각각의 인덱스에 대해 이전 수열 중 가장 긴 수열의 길이를 찾아보자 10은 본인보다 작은 수가 없으므로 020은 10이 본인보다 작기에 18은 본인보다 작은 수가 없으므로 030은 20이 본인보다 작기에 2가 된다. 여기서 주목해야 할 부분..

문제 설명 : https://www.acmicpc.net/problem/1663 문제 요약 :XYZ 문자열이란 이전 문자열에 대해 특정한 규칙으로 변환되는 문자열이다.X -> YZY -> ZZ -> X와 같은 규칙으로 변환된다.N번째 문자열의 길이, k번째의 문자, X, Y, Z 각각의 개수를 구하라 문제 풀이 시간 : 1시간문제 성공 여부 : 성공 접근 방법(성공) :dp로 접근 제일 처음에 생각한 방식은 무작정 이전 문자열에 대해 변환을 해주는 것이다.N이 최대 100이기에 크게 늘어나지 않을 것 같았고, 대략적인 계산을 해보았다. XYZ 문자열은 Y와 Z일 경우 각각 Z, X 로 변환되어 문자의 수가 유지된다.하지만, X는 YZ로 변환되기에 2개로 늘어난다. X가 YZ로 변환되어도 결국 Y->Z,..

문제 설명 : https://www.acmicpc.net/problem/2473 문제 요약 :세 개의 용액의 합의 절댓값이 0에 가까운 용액 집합 찾기 문제 풀이 시간 : 2시간문제 성공 여부 : 실패 접근 방법(실패) :2개 용액의 합 리스트(twoSum) 만들기n개의 정렬된 용액 이분탐색세 가지의 용액의 합의 절대값이 최소인 집합 찾기 해당 방법의 최악의 경우는 다음과 같다. 1. twoSum의 개수 : 5000 * 4999 / 2 = 124975002. N 이분탐색 횟수 : log2(5000) = 약 13 두 계산의 합은 약 1.6억이기 때문에 제한시간인 1초 내에 해결이 불가능하였다. 접근 방법(성공) :한 가지 용액을 고정(i)하고 해당 인덱스의 왼쪽(left)과 오른쪽(right) 끝의 ..

문제 설명 : https://www.acmicpc.net/problem/2252 문제 요약 :학생 두 명의 정렬 순서가 M개 주어진다.이를 토대로 올바른 정렬 순서를 만족하는 순서를 출력하라 문제 풀이 시간 : 1시간문제 성공 여부 : 실패 접근 방법(실패) :그리디 하게 접근A, B가 모두 없을 경우, 배열의 끝에 추가A만 있을 경우, B를 A의 바로 뒤에 추가B만 있을 경우, A를 B의 바로 앞에 추가A, B 모두 있을 경우, 대소 비교 후 올바르면 패스, 올바르지 않을 경우 A를 B 바로 앞으로 이동 내가 생각한 로직의 핵심은 5번이었다.3 33 52 32 5와 같은 입력이 주어졌을 때, 5번 조건에서 대소 비교가 올바를 경우 넘어가지 않으면 다음과 같은 반례가 발생한다.3 5 -> 3 52 3 ..

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :최대, 최소 값 삭제, 숫자 삽입 명령 세 가지가 주어진다. 모든 연산 이후 최대와 최솟값을 출력하라. 문제 풀이 시간 : 20분문제 성공 여부 : 성공 접근 방법(성공) :일반 배열에 숫자를 계속 삽입한다.삭제 명령어 직전, 배열을 정렬하고 shift(), pop()으로 최소, 최대 값을 제거한다. 문제를 가만 생각해 보니 출제 의도와는 다른 허점을 발견하였다. (절대 힙을 구현하기 귀찮아서가 아니다.)명령어의 최대 개수는..

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :유저가 들어올 때, 나갈 때의 로그를 출력해야 한다.중간에 닉네임이 변경되면, 변경된 닉네임이 최종적으로 출력되어야 한다.닉네임은 나가서 변경하고 재입장, Change 커맨드를 통해 변경할 수 있다. 문제 풀이 시간 : 20분문제 성공 여부 : 성공 접근 방법(성공) :최종적으로 유저의 uuid에 따른 이름만 알면 되기에, Map으로 이름을 최신화한다.입장과 퇴장 로그만 출력하면 되기에, 해당 로그만 따로 관리한다.위에 글과..

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/142085# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :라운드 별로 enemy[i] 명의 적이 등장한다.아군 병사 n명과 라운드 스킵 횟수 k를 이용하여 최대 클리어 가능 라운드 수를 출력하라 문제 풀이 시간 : 30분문제 성공 여부 : 성공 접근 방법(성공) :이진탐색으로 최대 클리어 가능한 라운드 수 구하기 내가 생각한 문제의 핵심은 다음과 같다. 1. 무적권(k)는 특정 범위(라운드)에서 가장 큰 수부터 사용해야한다.2. 가장 큰 수를 구하는 쉬운 방법은 힙을 사용하거나..

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/17683# 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :라디오에서 특정시간 동안 같은 노래가 반복된다.네오가 기억하고 있는 일부 가사(음)를 이용해 가장 적절한 노래 제목을 찾아라 문제 풀이 시간 : 1시간문제 성공 여부 : 성공 접근 방법(성공) :라디오에서 방영된 총 재생 시간을 분 단위로 계산한다해당 시간동안 들리는 노래 가사(음)를 하나의 문자열(s)로 만든다.m(네오가 기억하고 있는 가사)를 s에 포함되어 있는지를 찾는다.단, #이 포함된 가사(음)은 소문자 등으로 ..

문제 설명 : https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약 :n*n의 체스판에서 n개의 퀸이 서로 공격할 수 없게 배치하는 경우의 수 문제 풀이 시간 : 30분문제 성공 여부 : 성공 접근 방법(성공) :2차원 배열을 만든다(체스판)dfs(백트래킹)을 통해 둘 수 있는 모든 경우의 수를 파악한다.이런 체스판이 있으면 퀸은 열에 최대 하나밖에 둘 수 없다. ( 퀸은 가로, 세로, 대각선으로 이동 가능 ) 따라서 열마다 한 개의 퀸을 두면서 해당 위치에 퀸을 둘 수 있는지를 계산하며 체스..