코테

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 풀이 bfs 기반 빡(?)구현 문제이다. bfs로 계속 탐색을 하면서 현재 물고기 크기에서 먹을 수 있는 물고기를 모두 찾아본다. 단 탐색시에 자신보다 큰 물고기를 지나갈 수 없고, 같은 크기의 물고기는 지나는 가되 먹을 물고기에 추가하지는 않는다. 그렇게 현 상황에서 먹을 수 있는 모든 물고기를 저장해둔 배열을 다중 조건으로 정렬해줘야한다. 1. 크기 2. 크기가 같다면 열 오름차순..

문제 https://www.acmicpc.net/status?user_id=whipbaek&problem_id=1197&from_mine=1 채점 현황 www.acmicpc.net 풀이 제목 그대로 최소스패닝트리(MST)를 만드는 문제다. MST를 만드는 방법으로는 크루스칼과 프림 알고리즘 두개가 있는데 나는 크루스칼을 활용하여 풀었다. 크루스칼은 edge들의 비용순으로 오름차순 한 후에, 하나씩 연결해보는 알고리즘이다. 연결하다가 사이클이 발견되면 그 edge는 뛰어넘고 다음 edge를 확인해보는 식으로 반복된다. 이 때 사이클을 감지하기 위하여 union find 알고리즘을 활용한다. 연결하려는 두 노드의 루트노드가 같다면 사이클이 존재한다는 것이다. 사이클이 발생하지 않을경우에만 비용값을 더해주고 ..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 dp 방식으로 생각해보면 '내가 위치한 계단을 어떻게 오느냐' 에 초점을 맞춰보면 된다. 내가 i번째 계단에 있다면 나는 1. i-1 번째 계단에서 왔거나 2. i-2 번째 계단에서 왔을것이다. 단 i-1번째 계단에서 왔다면, i-2번째계단을 밞고오진 않았을 것이다. (그렇게 되면 3개 연속 계단을 밞으니) 따라서 i-3 번째에서 왔을것이고 이를 활용하여 점화식을 세울 수 있다. D[i] = max..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/17687 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 풀기 위해서는 진법 변환에 대한 기초 지식이 있어야한다. 간단한 예로 로직을 살펴보면 7을 2진수로 나타내보자. 7 / 2 = 3 ... 1 3 / 2 = 1 ... 1 1 / 2 = 0 ... 1 0 / 2 = 0 ... 0 (... 은 나머지를 나타낸다.) 10진수 7을 2진수로 나타내면 1110 이다. n진수로 나타내고 싶을때, 나머지들을 취하면 해당 진법으로 변환시킬 수 ..

문제 https://www.acmicpc.net/problem/18353 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 가장 긴 감소하는 부분 수열이랑 문제가 완전히 똑같다. (가장 긴 증가하는 부분 수열의 반대로 https://whiporithm.tistory.com/11 ) n에서 가장 긴 감소하는 부분 수열의 길이를 빼주면 정답이다. 코드 n = int(input()) d = [1] * n wars = list(map(int, input().split())) for i in range(n..

문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 풀이 해당 문제는 뒤에서부터 접근하여 최댓값을 갱신하는 방식으로 풀 수 있다. D[i] = i번째 날부터 마지막 날까지 낼 수 있는 최대 이익이라고 정한다. 이후 뒤에서부터 (지금 날짜 + 오늘 일하면 걸리는 날짜)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/72412 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 문제를 보고서 Dictionary를 사용해야할 거 같았다. 1. 우선 주어진 프로그래밍 언어, 직군 등을 조합하고 모든 부분집합을 Key로 만들어주고 초기화해준다. 2. 이후에 info 리스트를 순회하면서 모든 부분집합을 만들고, 해당하는 Key에 점수를 넣어준다. 3. 마지막에는 query 리스트를 순회하면서 해당 조건에 맞는 Key를 찾고, value (점수들이 들어가있는 list)..

문제 https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열과 비슷한 문제이다. 단 차이점은, 증가하는 부분 수열중 합이 가장 큰 값을 반환해야하는 것이다. 이 문제 또한 특정 인덱스에서 앞을 순회하면서, 1) 나보다 값이 작다면 2) 갱신되는 값이 더 크다면 갱신해준다. 라는 플로우를 따르면 된다. 식으로 나타내면 D[i] = max(D[i], D[j] +..

문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 풀이 이 문제에서 n의 제한은 1000이다. 따라서 O(n^2) 풀이가 가능한것을 인지하고 있자. 증가하는 수열이므로, 특정 인덱스 앞의 요소들을 하나씩 다 살펴본다. 1) 이후 만약 값이 나보다 작고 2) 해당 값에 저장된 수열 + 1 (현재 인덱스까지 포함하면 + 1 이니까 ) , 현재 수열의 길이를 비교해서 ..

문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 2 x n 타일링 문제와 거의 유사하다. (풀이 링크 : https://whiporithm.tistory.com/6 ) 차이점이라고는 2 * 2 타일이 하나 더 들어온 것. 따라서 = 타일이 ㅁ 타일이 될 수 있다. 그렇기에 경우의 수를 2배로 설정해주면 답이 나온다. 코드 n = int(input()) d = [0] * 1001 d[1] = 1 d[2] = 3 for i in range(3, 1001): d[i] ..