https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 💡IDEA 최대 N개의 종류의 알파벳을 가진 연속된 문자열의 길이 최댓값을 찾는 투 포인터 문제 왼쪽 포인터를 기준으로 오른쪽 포인터를 옮기며 해당 문자열 내 몇 종류의 알파벳을 가졌는지 세어주어야 한다. 다른 것보다 시간 초과가 많이 일어나서 경우를 생각해 제외할 수 있는 부분은 모두 제외시켰다. 1. N==1 이거나 입력 문자열의 길이가 1인 경우 → 정답: 1 2. 입력 문자열이 이미 N개의 종류 알..
https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 동적계획법을 사용하는 문제이다. 📌CODE def solution(triangle): answer = 0 dp = triangle.copy() for i in range(1, len(triangle)): for j in range(0, i+1): if j == 0: dp[i][j] += triangle[i-1][j] continue if j == i: dp[i][j] += triangl..
https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 풀면 풀 수록 라이언이 불쌍해지는 완전 탐색 문제이다. 오랜만에 알고리즘 문제를 풀었더니 완전 감이 다 떨어졌다. dfs나 완전 탐색인건 알겠는데 어떤 것부터 건드려야할지 잘 모르겠다. 결국 질문하기에서 좀좀따리 힌트 얻어가며 문제를 풀었다. 가장 도움이 되었던 것은 combination_with_replace 함수, 즉 중복조합을 사용한다는 점이었다. 0..
https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 힙(Heap)을 사용해서 풀었다. 힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한다. 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다. 힙 특징 : A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소 관계가 성립한..
https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 스택, 큐를 사용하여 풀었다. 먼저 작업의 진도가 작업의 속도만큼 진행되었을 때 몇 일 만에 개발이 완료되는지 q에 저장하고자 했다. 처음에는 while문으로 100이 될때까지 일수를 세어주었는데, 정답 확인 후에 이 부분은 시간을 줄이기 위해서 math의 ceil(올림)함수를 사용했다. 그다음 q에 저장된 수를 popleft 해가면서 현재값보다 큰 값이 나오기 전까지 개발된 기능만 배..
https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡IDEA 스택을 사용하는 문제이다. 스택의 자료구조를 배울 때 연습해보는 가장 기본적인 문제인데 새삼스럽게 풀어보자니 조금 버벅거렸지만 그래도 잘 풀어낸 것 같다. 문자열의 앞에서부터 하나씩 확인하면서 스택에 넣고 빼는 작업을 한다. 여는 괄호('(')인 경우에는 스택에 넣어주고, 닫는 괄호(')')인 경우에는 스택의 top에 있는 것이 여는 괄호일 때 까지 빼준다. 그리고 그 여는 괄호까지 빼..
https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 💡IDEA 트리, DFS를 사용하는 문제이다. 처음엔 큐를 사용하여 삭제한 노드에 연결된 모든 노드들을 -1로 갱신하여 지워주는 방법으로 풀었으나 99%에서 실패가 떴다. 찾아보니 0번 노드만 남은 경우에도 결과값이 1이여야 하는데, 0으로 출력되고 있었다. 이것을 해결하기 위해 여러 방법으로 수정했으나 도무지 알 수가 없어서 DFS를 사용했다. 삭제한 노드에 연결된 모든 노드들의 부모 노드..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 💡IDEA 조건에 맞게 구현하는 문제이다. 큐를 사용해서 뱀의 몸을 구현하고, 주어지는 방향에 맞게 위치를 틀어준다. 방향은 좌우로 움직이는 것을 고려하여 dir 배열을 사용하여 인덱스 값으로 방향을 조절했다. 가장 먼저 0행 0열부터 뱀이 오른쪽 방향으로 움직인다. 갈 수 있는 곳이라면 뱀의 몸에 추가해주고, 시간을 카운트한다. 만약 해당 위치에 사과가 있다면 사과가 없어지고 꼬리는 유지한다. 하지만 ..
https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 💡IDEA 동적 계획법을 사용하는 문제이다. 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 구해야 하는데, 조건은 해당 번호의 사람이 본인 번호 자리에 앉거나, 앉지 않거나 두 경우가 존재한다. 가짓수는 몇 번의 반복을 통해서 규칙을 찾을 수 있다. N = 1 N = 2 N = 3 N = 4 N = 5 경우 1 12 21 123 213 132 1234 2134 1324 1243 2143 12..
https://www.acmicpc.net/problem/2529 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net 💡IDEA DFS, 백트래킹을 사용하는 문제이다. 숫자를 직접 하나씩 부등호에 따라 넣어주는 식의 브루트 포스가 가능하다. 백트래킹으로 0~9 숫자를 포함하고 포함하지 않고를 결정하며 부등호를 만족하는 수를 찾으면 된다. 레벨(깊이)가 0이거나 방문하지 않았고 두 수(들어가는 숫자 중 마지막 수, 현재 인덱스 값)를 부등호로 비교했을 때 정상적인 경우에 백트래킹을 수행한다. 현재 인덱스 값을 포함한 값으로 재..
