![]()
문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 문제 설명 문제 초반에는 단순하게 dfs를 진행해서 최대로 갈 수 있는 칸 수를 기록하면서 진행했다. 골드 3치고 문제가 너무 쉽다고 생각했는데, 34% 정도에서 시간초과가 발생했다. 생각해 보면 당연하다. 최대 배열 크기가 500이고, 500x500을 계속해서 무식하게 탐색하면 시간초과가 나는 건데 왜 이 생각을 못했을까. 그렇다면 수정해야 될 것은 탐색을 하는 범위라고 생각했다..
![]()
문제 https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 풀이 대륙간의 연결하는데 필요한 최소한의 비용으로 다리를 건설하는 것이 목표이다. 그렇다면 첫 번째로 대륙을 구별해야 할 것이다. A대륙에서 B대륙으로 다리를 놓기 위해서는 A대륙과 B대륙을 구별해줘야 한다. 다음과 같이 대륙을 구별해 줬다. 어떻게 구별했냐?? 배열이 1인 경우 bfs를 진행하고, 땅을 밟는 경우 라벨링을 해줬다. 그러다가 bfs가 중지되면 라벨을 +1 하고, 다시 땅을 만..
![]()
문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 설명 일반적인 그래프 탐색문제랑 비슷한 부분이 많다. 조금 다른 점은 벽의 개수를 3개로 제한되어 있다는 점이다. 반드시 3개를 세워서 탐색을 진행한다는 점 말고는 동일하다. 그렇다면 벽 3개를 어디다 배치할지를 결정하면 쉽게 풀 수 있다. 조금 더 효율적인 방법이 있는지는 모르겠지만, 나는 빈칸의 개수를 배열에 저장해서 빈칸의개수빈칸의 개수 * 빈칸의 개수 -1 * 빈칸의 개수 -2 만큼 반복문을..
![]()
📕문제 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 🔎문제설명 bfs 문제에서 조금 변형이 있는 문제입니다. 스위치를 켜면 해당 방으로 이동할 수 있는 것이 아닌, 스위치를 켜고 스위치로 이동가능한지 여부를 판단해야 하는 문제입니다. 다른 bfs문제처럼 바로바로 큐에 넣는 것이 아닌 여부를 판단하고 큐에 넣어야 하기에 헷갈릴 여지가 있다고 생각합니다. 주의할 점은 (1,1)은 원래 불이 ..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/17677 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 설명 두 문자열을 2개로 끊어서 집합을 생성한 후 교집합과 합집합을 구해서 유사도를 구하는 문제이다. 문제의 주요 특징은 다음과 같다. 문자열을 2개씩 끊어서 하나의 원소로 만든다. "알파벳"만 원소로 만들 수 있다. 숫자, 공백, 특수문자가 포함된 경우 버린다. 알파벳은 대 소문자의 차이를 무시한다. 원소의 중복을 허용한다. 원소의 중복..? 말이 조금 어려운데 예시를 들면 쉽게..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 풀이 문자열을 이용한 구현 문제입니다. 문제가 굉장히 길지만, 요약하자면 주어진 문자열을 N개 단위로 잘라서, 가장 짧은 문자열로 만들 자입니다. 그러면 각 N개마다 자른 문자열의 길이를 비교하면 되는 문제입니다. 여기서 중요한 점은 문자열의 길이가 N이라면, N/2까지만 검사합니다. 만약 N/2를 넘어서 자르게 된다면 당연히 압축이 안 되겠죠?? 그래서 저는 1개~N/2개까지 잘랐..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/42890 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 풀이 해당 문제를 풀 기전에 유일성과 최소성을 설명하고자 합니다. 💡유일성? 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다. 위 테이블에서 칼람을 유일하게 식별할 수 있다면, 그 칼럼은 유일성이 있다고 합니다. 학번을 보면 모든 값들이 다 다른 것을 알 수 있습니다. 따라서 해당 테이블에서 학번을 통해서 유일하게 식별할 수 있습니다. 이러한 칼럼 학번은 유일성을 만족한다..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 풀이 우선 문제 이해하는데 조금 오래 걸렸습니다. 제가 이해한 내용을 설명하자면, 변수 n, t, m이 있습니다. n은 운행하는 버스의 수, t= 배차 간격, m= 탑승할 수 있는 인원의 수입니다. timetable은 이제 기다리는 크루원들의 도착시간입니다. 그림이 이상하더라도 양해 부탁합니다.. ㅎ 🙏 위 그림은 입출력예제 1번입니다. 여기서 가장 기본이 되는 정보는 09:00에 ..
![]()
📕문제 https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 풀이 양수 a가 될 수 있는 조건은 2가지 있습니다. 철수가 가진 카드들을 전부 나눌 수 있고, 영희가 가진 모든 카드를 나눌 수 없어야 합니다. 영희가 가진 카드들을 전부 나눌 수 있고, 철수가 가진 모든 카드를 나눌 수 없어야 합니다. 그렇다면 a의 후보는 철수가 가진 약수이거나, 영희가 가진 약수여야 합니다. 이때 각 약수들은 상대방들의 약수가 되어서는 안 됩니다. 풀이 방식..
