siino's 개발톡

https://school.programmers.co.kr/learn/courses/30/lessons/150367 문제 해결 전략 주어진 수를 이진수로 변환하기 만들어진 이진수를 "포화이진수"로 만들기 만들어진 포화 이진수를 탐색하며 부모 노드, 자식 노드를 기록하기 부모 노드의 값이 0이면서 자식 노드의 값이 1이라면 표현 가능한 이진트리가 아님!! 문제에서 가장 중요한 포인트는, 포화 이진수를 만드는 것과 각 노드들의 자식노드를 기록하는 것 입니다. 문제를 잘 분석해보면, 포화 이진수로 표현하기 위해서는 해당 "이진수의 길이" = "2의 거듭제곱 - 1"임을 알 수 있습니다. 따라서 해결 전략 1에서 나온 이진수의 길이보다 큰 2의 거듭제곱을 찾고 그 값에 1을 뺀 길이 만큼 이진 수 앞에 '0'을..

https://school.programmers.co.kr/learn/courses/30/lessons/42579 문제를 간략히 설명하자면 genres[]와 plays[] 배열이 주어지고, 해당 장르가 플레이된 횟수(내림차순)으로 정렬 한 후에 각 장르에서 많이 플레이 된 곡 top2를 뽑아내면 되는 문제입니다. 제가 풀이한 방법은 각 장르의 플레이 된 횟수를 기록할 Map genreCount 와 각 장르별 곡의 정보를 저장할 Map를 선언하여 문제를 해결했습니다. 여기서 말하는 곡의 정보는 (music id, 플레이된 횟수)를 기록합니다. Map과 관련된 내장 함수 computeIfAbsent(), merge(), getOrDefault()를 활용하여 조금 더 깔끔하게 코드를 작성할 수 있었습니다. i..

https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명: 여러 직사각형들이 놓여져 있을 때 겹쳐지는 부분을 제외하고 각 변들을 탐색해서 BFS를 수행하는 문제입니다. 제가 생각했던 풀이는 아래와 같습니다. 1. 격자에 각 직사각형들을 색칠한다. (테두리: 1, 내부 -1) 2. 직사각형을 색칠할 때 이미 내부(-1)로 색칠되어 있다면 건너뛴다. 3. 주어진 시작점에서 시작해 색칠된 직사각형들의 1값을 bfs탐색을 통해 주어진 item 좌표로..

요즘은 코틀린에 관심이 생겨 코틀린으로도 쉬운문제 위주로 차근차근 풀려고 노력중입니다 :) 우선 문제는 아래 링크에 첨부하겠습니다. https://school.programmers.co.kr/learn/courses/30/lessons/178871 처음 문제를 해결하기 위해 생각했던건, calling에 들어있는 사람들의 이름을 indexOf함수로 해당 index를 찾아 그 앞 index와 자리를 바꾸도록 생각했습니다. 하지만 문제 조건에 의해 players의 길이는 최대 5만, calling의 길이는 최대 100만이기 때문에 calling의 모든 요소에 대해 indexOf를 수행한다면, 100만 * 5만 = 500억 만큼의 연산을 하게 됩니다. 따라서 보다 효율적인 방법을 생각하였고 Map을 통해 해결할..

https://school.programmers.co.kr/learn/courses/30/lessons/160585 [문제해결 전략] 1. 백트래킹을 통해 혼자서 틱택토를 진행한다. 2. 게임 종료 조건이 되거나 주어진 board판과 동일한 모양이라면 종료. 게임 종료 조건은 빙고게임과 같이 한 줄이 O또는 X로 채워지는 것입니다. 게임은 턴제의 게임으로 O,X가 번갈아가며 진행하기 때문에 매개변수로 turn값을 주어 현재 누구의 턴인지 확인할 수 있도록 합니다. class Solution { char[][] myBoard; String[] _board; int answer = 0; public int solution(String[] board) { myBoard = new char[3][3]; _boa..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 힌트는 제약사항에서 확인할 수 있습니다. 결국 기다리는 사람은 최대 10억명이므로 각각의 대기자에 대해서 문제를 해결할 순 없습니다. 결국 심사관 관점에서 문제를 풀어야함을 알 수 있고 문제가 결국 가장 효율적으로 심사하는 시간의 최솟값을 구하는 문제라는 것에 주목한다면, 최적화문제를 결정문제로 바꾸는 Parametric Search를 생각해볼 수 있습니다. 심사관이 심사하는데 걸린 소요시..

https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 애니팡과 비슷한 게임이라고 생각할 수 있습니다. 풀이의 핵심은 두가지로 나눌 수 있습니다. 1. 인접한 2x2 사각형의 모든 블록의 종류가 같은지 파악하여 터질 블록을 판단 2. 블록을 터뜨린 후, 터뜨린 블록 윗 블록들에 대해 아래로 내리기 문제를 풀면서 c++에는 있는 tuple이나 pair자료구조에 대해 java는 왜없는지..조금 안타까웠습니다. 좌표에 대해 int[] 배열로 S..

https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 주어진 명령어가 주어졌을 때, 명령어대로 진행한 후에 처음 가본 길의 개수를 구하는 문제입니다. 처음가본 "길"에 집중하여 문제를 풀어야 합니다. 단지 노드를 방문했다고 해서 해당노드를 방문처리하고 끝내서는 안됩니다. 길에 초점을 맞춰서 (x1,y1) -> (x2, y2)의 노드로 진행하였다면 방문했던 길을 저장하는 HashSet에 (x1, y1, x2, y2)를 저장하는 방식으로 구현했습니다. ..

더보기 시간 복잡도를 줄여야하는 문제 아이디어를 찾아서 해결 해야하는 문제 꼭 손으로 그려보면서 규칙성을 찾기 문제를 보고 처음에는 각 차례에서 밑장빼기를 하는 경우를 재귀로 구현하여 풀어보면 어떨지 생각했다. 하지만 주어진 N의 범위는 10만. 따라서 모든 경우의 수를 재귀로 구현하면 시간복잡도는 O(N^2)이 된다. (N개 중 밑장빼기를 할 index 찾기 * 원소 순회하면서 누적합 계산) O(N) * O(N) 따라서 시간복잡도를 줄여야 했고, 다른 방법을 생각하게 되었다. 이렇게 아이디어를 필요로 하는 문제들을 푸는 과정은 직접 손으로 그려라!! 밑장 빼기 하는 숫자는 맨 마지막 원소이므로 고정. 밑장 빼기를 하면 맨 마지막 원소를 다른 index에 삽입하여 홀수번째/짝수번째 index를 나눠서 누..

https://www.acmicpc.net/problem/9251 [9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net](https://www.acmicpc.net/problem/9251) 문제해결과정 최장 공통 부분 수열 2개의 문자열이 주어지고 두 문자열의 공통 부분 문자열 중, 가장 긴 것의 길이를 구하는 문제. 각 문자열의 i번째, j번째 문자를 포함을 시키거나 포함하지 않는 공통 부분 문자열의 길이를 구한다. 유명한 dp문제이다. dp테이블은 dp[i][j] ..