CS/Algorithm
[백준(파이썬/Python)] 1261_알고스팟
https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net BFS와 우선순위큐(heapq)를 동시에 활용해서 푸는 문제입니다. 현재까지 부순 벽의 수를 count라는 변수에 저장하고, 상하좌우로 이동을 하며 벽이면 count+1, 벽이 아니면 count값을 그대로 우선순위 큐에 넣어주면 됩니다. 일반적인 bfs와는 다르게 우선순위 큐를 이용해야 하는 이유는 벽을 깨는 횟수를 "최소한"으로 하기 위해서인데, 다음 방문할 곳 중에서 벽이..
CS/Algorithm
[프로그래머스(파이썬/Python)] 상호 평가
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 올 해 네이버 공채 코딩테스트에서 봤던 문제랑 똑같은 문제입니다. 프로그래머스에 네이버 문제도 오픈되는 것 같네요. 본론으로 들어가서, 이 문제는 당시 코딩테스트에서 1번 문제로 나왔을만큼 어렵지 않은 문제입니다. 다만, 이 문제에서 가장 중요한 포인트는 "문제를 잘 읽어야 한다"는 점입니다. 알고리즘..
CS/Algorithm
[백준(파이썬/Python)] 10830_행렬 제곱
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 거듭제곱의 연산 수가 100,000,000,000까지 갈 수 있기 때문에 일일이 계산하는 것은 불가능한 문제입니다. 따라서 분할 정복 개념을 바탕으로 거듭제곱근으로 나눠나가는 아이디어를 떠올려야 합니다. 예를 들어 A^100 = A^50 * A^50이고, A^5 = A^2 * A^2 * A처럼 차수를 2의 제곱근으로 떨어뜨릴 수 있는 것이죠. 한편, 행렬의 곱셈 연산은 multyplyMatrix(m1, m..
CS/Algorithm
[백준(파이썬/Python)] 5639_이진 검색 트리
https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 이 문제는 시간초과 때문에 고통받았던 문제입니다. 아래는 기존의 풀이이고 이렇게 하면 (전위순회를 통해 트리를 생성하는 시간) + (후위순회를 하는 시간(덤으로 재귀까지))때문에 시간초과가 발생합니다. 기본적인 트리 순회는 스택이나 재귀를 이용해서 하면 되지만 이 문제에서는 효율적인 탐색을 요구한 것이죠. // 시간초과 import sys sys.setrecursionlimit(10 ..
CS/Algorithm
[백준(파이썬/Python)] 1062_가르침
https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 이 문제에서 'a','n','t','i','c'는 반드시 가르쳐야 하고, 모든 단어의 맨 처음 네 글자가 'anta', 'tica'라는 조건은 아마 시간 복잡도를 맞추기 위한 설정이거나 약간의 구현(?)을 유도하기 위한 것 같습니다. 하지만 기본적으로 단어의 개수나 알파벳의 수가 크지 않기 때문에 완전 탐색을 해야겠다는 생각을 할 수 있었고, 다만 조금이나마 효율적인 완전탐색을 하기 위한 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 점프와 순간 이동
https://programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr Greedy하게 접근하면 쉽게 풀 수 있는 문제입니다. 아래 풀이의 주석에서 설명한 것처럼 (짝수번 째 칸 * 2)한 지점까지의 에너지 소모량은 0이고, 홀수 칸에서 짝수칸을 가기 위해서는 +1을 점프해주면 되기 때문에 이를 역으로 구현해주었습니다. ps. 처음에는 DP라고 생각해서 풀었는데, 정답은 맞지만 n이 1억 이하의 범위라서 DP..
CS/Algorithm
[백준(파이썬/Python)] 2638_치즈
https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 이 문제의 핵심은 내부 치즈인가 아닌가를 어떤 방식으로 판단할 것인가입니다. 처음 문제에 접근했을 때는"모든 지점에 대하여 내부 치즈인가를 BFS 탐색을 하였고, 만약 가장자리에 도착할 수 있으면 내부 치즈가 아니다"라고 생각했습니다. 하지만 그렇게 되면 모든 위치마다 일일이 체크를 해줘야 하기 때문에, 시간복잡도에서 불리할 수밖에 없습니다. 이를 해결하기 위해서는 반대로 "가장 자리..
CS/Algorithm
[백준(파이썬/Python)] 2096_내려가기
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 풀이 자체는 어렵지 않은데 문제의 메모리 제한이 상당히 타이트합니다. - 현재 계단에서 점수의 최대, 최소는 그 전 계단까지의 최대 최소에만 영향을 받기 때문에 모든 계단의 점수값을 미리 배열로 만들어두면 메모리 초과가 발생합니다. - 따라서, 계속해서 각 시점에서 인풋값을 읽고 최적해를 갱신해나가는 방향으로 문제를 풀어야합니다. 문제 풀이의 DP 로직은 첫번째, 두번째, 세번째 계단에 있을 때를 따로 생각..
CS/Algorithm
[프로그래머스(파이썬/Python)] 가장 긴 팰린드롬
https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 아래 코드에서 설명한 두 개의 주석이 핵심입니다. 1. 팰린드롬 문자열인지 확인할 때는 포인터 두 개를 두고(투 포인터) 왼쪽 끝과 오른쪽 끝이 일치하는지 확인하면 됩니다. left < right까지 문자열이 일치한다면 팰린드롬이죠(스터디를 하다가 str == str[::-1]로 팰린드롬을 확인할 수 있다는 ..
CS/Algorithm
[백준(파이썬/Python)] 1967_트리의 지름
https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 백준 1167번 트리의 지름 문제와 완벽하게 동일해서 해당 문제에 대한 풀이를 참고하면 될 것 같습니다. [백준(파이썬/Python)] 1167_트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개..
