Junior-Developer

1일 1커밋! 1일 1 백준!

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr -풀이- 먼저 a의 길이를 보았을때 ,O(N*N)은 불통과할게 뻔해보이므로 O(NlogN) 이나 O(N)으로 풀 수 있는 방법이 있는지 생각해보았다. 그러자 전체 개수에서 안되는 개수를 빼면 되는데, 안되는 경우를 생각해보니 해당 i번째 인덱스 원소 기준 좌측의 최솟값보다 크고, 우측의 최솟값보다 크면 안된다. 문제에서 주어진 "인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만 할 수 있습니다" 를 마지막에 적용을 시킨다고 해보자. i번째 인덱스의 값을 5라..

2021. 3. 26.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr -풀이- 최소 비용으로 모든 섬이 서로 통행가능하도록 만드는것은 최소신장트리 알고리즘을 사용해주면 된다. 최소신장트리 알고리즘을 사용하기 위해선, 1. 먼저 각 도로(간선)들을 비용을 기준으로 오름차순 정렬을 해준뒤, 2. 작은 간선부터 차례대로 검사해가며, 두 정점이 같은 그룹에 속하지 않는다면, 같은그룹으로 묶어주면서, 그 간선을 최소신장트리의 간선으로 채택을 해주면 된다. 3. 이미 같은 그룹이라면, 앞에서 더 적은 비용으로 갈 수 있는 간선을 선택했으므로 무시해주면 ..

2021. 3. 21.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/12900 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr -풀이- dp로 풀면 된다. dp[i]=j 는 가로의 길이가 i일때, 놓을 수 있는 경우의 수를 j라고 하자 그럼 점화식은 dp[i]=dp[i-1]+dp[i-2]가 된다. 위의 그림처럼 i=4일땐, i가 3인 경우에 세로로 세운 작대기를 붙인 경우와, i가 2인 경우에 가로로 2개를 쌓은 경우의 수를 더해주면 된다. 따라서 dp[i]=dp[i-1]+dp[i-2]가..

2021. 3. 21.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이) dp문제이다. 1.puddle에 있는 위치좌표들을 maze배열에 체크를 해둔다.( 주의해야 할 점은 puddles도 m,n순서이므로 신경써주자) 2.dp배열을 max+1만큼 할당을 해준다. 3.dp[1][1](시작점)은 1로 해둔다. 왜냐하면 초반 초기화를 하지 않기위해서이다. 4.물웅덩이가 있는 좌표라면, 해당 좌표까지 가는 최단경로는 없으므로, 해당dp[..

2021. 3. 6.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이) 일반적인 dp문제이다. 삼각형을 2차원 배열로 설정하기 까다로우니 좌측으로 몰았다 v vv vvv vvvv vvvvv 이런식으로 좌측으로 몰아서 인덱싱을 하니 간편했다. dp[i][j]= i번째 높이(위에서 부터 0,1,2,....)에서 j번째 위치까지 오는데 걸리는 최대 합이다 따라서 dp[i][j]는 바로 위의 dp[i-1][j]과 dp[i-1][j-1]두개중 큰것과 자기 자신의 값을 더해주면 되는데 각 줄의 처음은 dp[i-1][j]만 고..

2021. 3. 3.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/12906 코딩테스트 연습 - 같은 숫자는 싫어 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 programmers.co.kr 문제풀이) 이 문제는 c++에서 주어지는 메소드를 얼마나 잘 활용하나 문제인것 같다. unique(st,end) => [st,end) 범위의 연속된 값을 뒤로 빼준뒤, 쓰레기값들의 위치를 반환해준다. ex) 1,1,3,3,0,1,1 -> 1,3,0,1,1,1 // 4번째 인덱스 반환 ※algorithm헤더파일을 include해야된다.※ erase(s..

2020. 11. 24.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/68935 코딩테스트 연습 - 3진법 뒤집기 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수 programmers.co.kr 문제풀이) 이진수를 구하듯이 같은방법으로 3진수를 구해준다. 3진수 구하는 방법 1.n을 3으로 나눠준 값을 temp에 저장한다. -> n을 3으로 나눠준다 (n>0일때까지) 2.temp를 리버스시킨다. 하지만 문제에서 3진법 앞뒤반전을 하라했으니, 우리는 1번까지만 시행해주고, 3진수를 10진수로 변환시켜주면된다. #includ..

2020. 11. 24.

문제풀이/프로그래머스

programmers.co.kr/learn/courses/30/lessons/12903 코딩테스트 연습 - 가운데 글자 가져오기 단어 s의 가운데 글자를 반환하는 함수, solution을 만들어 보세요. 단어의 길이가 짝수라면 가운데 두글자를 반환하면 됩니다. 재한사항 s는 길이가 1 이상, 100이하인 스트링입니다. 입출력 예 s ret programmers.co.kr 문제풀이) 이문제는 string클래스의 메소드를 얼마나 잘 활용하느냐를 판별하는 문제다. 일단 길이를 얻는 s.length()함수를 이용해서 길이를 구해주고, 길이가 짝수일때, 홀수일때로 나눠서 값을 구하면된다. 짝수일때는 가운데 두글자를 추출해내야 하는데 substr을 이용하고, 홀수일때는 한개만 추출하면되므로 at을 이용한다. ※su..

2020. 11. 24.