algorithm

프로그래머스 - 자물쇠와 열쇠

programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 문제 자물쇠에는 홈이 파여 있고 열쇠 또한 홈과 돌기 부분이 있다. 열쇠는 회전과 이동이 가능하며 열쇠의 돌기 부분을 자물쇠의 홈 부분에 딱 맞게 채우면 자물쇠가 열리게 되는 구조다. 자물쇠 영역을 벗어난 부분에 있는 열쇠의 홈과 돌기는 자물쇠를 여는 데 영향을 주지 않지만, 자물쇠 영역 내에서는 열쇠의 돌기 부분과 자물쇠의 홈 부분이 정확히 일치해야 하며 열쇠의 돌기와 자물쇠의 돌기가 만나서는 안된다. 또한 자물쇠의 모든 ..

DFS/BFS

그래프에 대한 설명 참고 DFS DFS는 Depth-First-Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 일반적으로 인접한 노드 중에서 방문하지 않은 노드가 여러 개 있으면 번호가 낮은 순서부터 처리한다. (이건 문제에 따라 다르게 적용시킬 수 있다.) DFS는 스택을 이용하는 알고리즘이기 때문에 실..

프로그래머스 - 무지의 먹방 라이브

programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음식은 그대로 두고, 다음 음식을 섭취한다. 다음 음식이란, 아직 남은 음식 중 다음으로 섭취해야 할 가장 가까운 번호의 음..

볼링공 고르기

문제 두 사람은 서로 무게가 다른 볼링공을 고르려고 한다. 볼링공은 총 N개가 있으며 각 볼링공마다 무게가 적혀 있고, 공의 번호는 1번부터 순서대로 부여된다. 또한 같은 무게의 공이 여러 개 있을 수 있지만, 서로 다른 공으로 간주한다. 볼링공의 무게는 1부터 M까지의 자연수 형태로 존재한다. N개의 공의 무게가 각각 주어질 때, 두 사람이 볼링공을 고르는 경우의 수를 구하라. 입력 첫 째줄 -> 볼링공의 개수 N(1 ~ 1000), 공의 최대 무게 M(1 ~ 10) 둘 째줄 -> 각 볼링공의 무게 K (1 ~ M) 출력 두 사람이 볼링공을 고르는 경우의 수 풀이 1. 각 무게 별로 볼링공의 수가 몇 개인지 count하는 배열을 만든다. ex) 볼링공 5개의 무게가 각각 [1 3 2 3 2]로 주어졌을..

만들 수 없는 금액

문제 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구한다. 입력 첫째 줄 -> N : 동전의 개수 (1 ~ 1,000) 둘째 줄 -> 동전의 화페 단위, N 개의 자연수 (1,000,000 이하) 출력 주어진 동전들로 만들 수 없는 양의 정수 금액 중 최솟값 풀이 1. 먼저 data를 정렬한다. 2. 처음에 금액 1을 만들 수 있는지 확인하기 위해 target=1로 설정한다. 3. 현재 data이 target을 만들 수 있으면 (data값target: break target+=x print(target)

백준 1439 - 뒤집기

www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. 예를 들어 S=0001100 일 때, 전체를 뒤집으면 1110011이 된다. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111..

구현

코딩 테스트에서 구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 보통 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다. 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열은 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 (순열과 조합을 찾는 경우 등) -> 많은 연습이 필요한 분야이다.(프로그래밍 언어의 문법을 정확히 알고 있어야 한다.) 대표적으로 완전 탐색과 시뮬레이션 유형을 '구현' 유형으로 많이 사용한다. 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 -> 보통 데이터의 개수가 100만개 이하일 때 완전 탐색을 사용하면 적..

그리디

그리디 알고리즘 : 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디 알고리즘은 다른 유형과 달리 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 최단 경로 알고리즘의 경우 플로이드 워셜, 다익스트라 알고리즘과 같은 특정 알고리즘을 미리 알고 있거나 팀 노트를 통해 준비해야 풀 수 있다. 그러나 그리디 알고리즘의 유형의 문제는 매우 다양하기 때문에 암기한다고 해서 항상 잘 풀 수 있는 알고리즘 유형이 아니다. 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다. +) 그리디는 보통 작은 값 혹은 큰 값부터 처리하는 경우가 많기 때문에 정렬 알고리즘과도 연관이 있다. 예제) 거스름돈 Q. 당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈..