알고리즘

문제 https://www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이러 www.acmicpc.net 풀이 완전탐색 + Multisource BFS 문제이다. 여러개의 시작점을 모두 구한 후에, BFS를 모두 실행해본다음, 빈칸에 바이러스를 다 퍼트리는 경우, 최솟값을 구하면 된다. 빈칸에 모두 퍼졌는지는 초기에 빈칸의 개수를 구하고, BFS 실행 로직에 빈칸만큼 바이러스가 퍼진지 확인했다. 문제를 풀면서 이슈가 좀 있었는데 1. 시간초과 처음 완전탐색을 위해서 itertools.permutatio..

문제 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 나는 현재 위치 기준으로, 다음 변하는 값이 큰 값인지, 작은 값인지에 따라 분기를 나누었다. (만약 한 칸 차이가 아니라면 무조건 안되므로 바로 False!) 큰 경우를 살펴보면 예로, 배열은 [2,2,3,3] l은 2 라고 해보자. 2의 개수를 계속 카운트 하다가, 3이 나오면 경사로는 2에 설치해야한다. 따라서 2의 개수가 l개 이상인지 판단하면 된다. 만약 경사로를 설치할 수 있다면 현재값을 3으로 이..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 후보키 개념이 애매모호해서, 그것부터 정리하고 문제풀이를 시작했다. 문제의 핵심은 유일성보다는 최소성을 어떻게 판별할것인가, 였던거 같다. 최소성을 판별하기 위해서는 부분집합을 활용하면 된다. 만약 속성이 '학번' , '이름', '학년' 이라고 가정해보자. 이 때 '학번' 하나만으로도 후보키가 될 경우, '학번' 이 특정 집합의 부분집합이 되는 순간 최소성을 위반한다. '학번' ..

문제 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 삼성 기출답게 시뮬레이션, 빡구현 문제다. 주사위의 절대적인 위치를 배열로 정해둔다. (난 문제에서 나온 숫자와 위치를 매칭했다.) 이후 동, 서, 남, 북 이동시에 갱신되는 로직을 각각 작성하면 된다. (이건 실제로 주사위 한 번 굴려보거나 그림 그려보면 된다.) 그리고 이동한 칸의 값을 보고 복사여부를 따져주면 된다...

문제 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/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)..