문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 같은 그래프를 DFS와 BFS로 출력하는 문제. 깊이우선탐색과 너비우선탐색의 기본을 다질 수 있는 문제다. 전략 01. Node 클래스 그래프의 노드 데이터들을 담을 Node 클래스를 생성한 뒤에 DFS와 BFS를 수행하는 방법. Node 클래스에는 정점 번호 데이터, 해당 노드와 연결된 노드, 방문 여부에 대한 정보가 들어가면 된다. 그럼 해당 노드를 ..

문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1부터 N까지의 사람이 원을 그리고 앉아 있을 때 K번째 사람을 순서대로 뽑는 문제 전략 01. LinkedList 처음 생각한 풀이는 사람이 순서대로 앉아 있기 때문에 Singly Linked List로 풀 수 있지 않을까였다. 인덱스를 K만큼 증가시켜가며 뽑은 뒤 범위는 넘는다면 N로 나눈 나머지를 다시 인덱스로 함으로서 범위 내에서 계속 돌도록 유지할 수 있다. 결과적으로는 원을 그리고 있기 때문에 Circular Linked List나 다른 방법이 더 쉬운 방법이었지만..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 DFS(Depth-First Search) 문제다. 상하좌우로 인접한 1인 셀들은 배추흰지렁이가 모두 왕래할 수 있으므로 1개로 쳐야한다. 전략 01. DFS 땅을 순회하면서 값이 1이고, 아직 방문하지 않은 땅을 발견한다면 그 지점부터 상하좌우를 확인해 주변의 땅 중 1이면서 아직 방문하지 않은 땅들을 재귀적으로 모두 방문처리한다. 이때 카운트를 1 올려주면 한 덩어리인 땅을 하나로 칠 수 있..

문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 일반적인 팩토리얼 구현 및 String 파싱 문제지만 N의 범위가 500까지다. 수가 매우 커질 수 있기 때문에 자료형에 대한 고려가 필요하다. 전략 01. 일반적인 풀이 N에 해당하는 팩토리얼을 구한 뒤 10으로 나눈 나머지가 0이 아닐 때까지 카운트하기 풀이 Java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.math.BigInte..

문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 값을 최소로 만들기 위해 괄호를 어떻게 쳐야 되는지 구하는 문제. 빼기(-)를 기준으로 수들을 나눈 뒤 각각 더해서 빼주면 되는 문제다. 전략 01. 파싱 계산식을 뭐 어떻게 하라. 이런 문제는 보통 파싱만 잘해도 풀린다. 괄호를 쳐서 최소값을 구해야 하므로 - 로 묶을 수 있는 묶음을 최대한 크게 해야 한다. 따라서 -에서 다음 -가 나올 때까지의 모든 수를 묶어서 괄호를 치면 그 수..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 커서를 L, D, B, P 명령어를 통해 이동하거나 커서 왼쪽에 문자를 삭제하고 추가하고 최종 결과를 출력하는 문제 전략 01. 리스트 import sys string = list(sys.stdin.readline().rstrip()) M = int(sys.stdin.readline().rstrip()) cursor = len(string) for _ in range(M): ins = sys...

문제 https://school.programmers.co.kr/learn/courses/30/lessons/77486 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 칫솔을 판매하는 다단계 업체에서 위쪽으로 10%씩 떼어줘야 할 때, 각 사람이 가질 돈을 구하는 문제 칫솔 하나당 100원이며, 10%를 떼어주는 금액이 1원 미만이면 떼어주지 않아도 된다. seller, amount의 묶음, 즉 판매량에 seller가 중복해서 들어있을 수 있다. 하지만 seller의 판매 금액을 합쳐서 한번에 계산하면 안된다. 따로따로 계산했을 때 10%가 1원 미만이 되..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 각 무인도의 식량 합계를 리스트로 나타내는 문제 이차원 배열을 읽어야 하며, 어느 점들이 어떤 무인도에 속한 점인지를 파악할 수 있어야 한다 전략 01. DFS X가 아닌 어떤 한 무인도의 점을 찾았다면 그 주변의 모든 이어지는 점을 연달아 찾아서 더해주면 한 무인도의 전체 식량 개수가 된다. 따라서 DFS로 풀되 재귀로 풀면 될 것 같다. 풀이 import sys sys.setrecurs..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/12899 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 어떤 10진수 n을 1, 2, 4로만 구성된 수로 바꾸는 문제 기본적으로 1, 2, 4로 이루어진 3진법이지만 0과 3이 없다는 것에 중점을 둬야 한다. 전략 01. 규칙찾기 전략이라기보다 기본적인 3진법에서는 1, 2, 10, 11, 12, 20, 21, 22, 100, 101, 102, ... 이런 식으로 증가해 간다면 124나라에서는 1, 2, 4, 11, 12, 14, 21, 22, ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/133502 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 차례로 쌓이는 재료의 순서가 1, 2, 3, 1일 경우 햄버거를 만들고 카운트 하는 문제 햄버거를 만들고 나서 남아있는 재료들과 새로 쌓이는 재료가 다시 햄버거가 될 수도 있다. 전략 01. 스택, 클래스 스택에 재료들이 올바른 순서대로 배열되어 있을 때 스택의 내부에서 알아서 판단하게끔 하고 싶었다. Burger클래스를 만들고 원래 재료의 순서와 다른 재료가 들어오면 새로운 Burger인..