민규의 흔적

2024년 6월 9일문제 링크 : 백준 2638번 - 치즈 문제  N×M의 모눈종이 위에 아주 얇은 치즈가 과 같이 표시되어 있다. 단, N 은 세로 격자의 수이고, M 은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자(작 은 정사각형 모양)의 4변 중에서 적어도 2변 이상이 실내온도의 공기와 접촉한 것은 정확히 한시간만에 녹아 없어져 버린다. 따라서 아래 모양과 같은 치즈(회색으로 표시된 부분)라면 C로 표시된 모든 치즈 격자는 한 시간 후에 사라진다. 와 같이 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므 로 이 공간에 접촉한 치즈 격자는 녹지 ..

2024년 6월 8일문제 링크 : 프로그래머스 - 타겟 넘버 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 n개의 수가 주어지면, n개의 " + " 혹은 " - " 연산자를 적절히 섞어 사용해 target과 일치하는 경우가 총 몇 가지 인지 구하는 문제이다. 연산자는 2종류 이므로, n이 최대 20일 때 최악의 경우의 수는 2^20 = 1,048,576로 완전탐색해도 되겠다 싶었다. n이 5일 때를 생각해보면 다음과 같이 모든 경우의 수를 생각할 수 있다.  실제 트리처럼 구현하지는 않았지만, 어떻게 풀까 고민하다 그림을 그려보고 백트래킹으로 접..

2024년 6월 8일문제 링크 : 프로그래머스 - 괄호 변환 [2020 KAKAO BLIND RECRUITMENT] 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 카카오 다운 복잡한 구현 문제이다. 이런 문제는 알고리즘적 접근보다는, 문제를 정확히 이해하고 키워드를 뽑아낸 후 문제가 요하는 바를 빠짐 없이 체크해야 한다. 균형잡힌 괄호 문자열, 올바른 괄호 문자열 균형잡힌 괄호 문자열이란, 특정 괄호 문자열의 구성 요소 "(" 와 ")"의 개수가 일치하는 문자열을 뜻한다. " (()) " , " ())( ", " )( " 모두 균형잡힌 괄호 문자열..

2024년 6월 7일문제 링크 : 백준 1504번 - 특정한 최단 경로  문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.입력첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) ..

2024년 6월 7일문제 링크 : 프로그래머스 - 줄 서는 방법 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 n이 주어졌을 때, 1 ~ n 까지 모든 수의 조합을 오름차순 정렬하여, k번째 조합을 찾는 문제이다. n에 대한 모든 경우의 수를 구해 k번째 조합을 구하면 큰일난다.n의 최대값은 20이며 시간복잡도는 O(n!), 가능한 조합의 수는 20!로 이는 2,432,902,008,176,640,000 ~= 10^19인 아주 큰 수다. 시간복잡도 말도 안된다.. 이 문제를 해결하기 위해서는 해당 큰 문제를 작은 문제로 쪼갤 수 있는지 접근해보아..

2024년 6월 7일문제 링크 : 프로그래머스 - 스킬트리 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  문제 접근 스킬을 배우는 순서가 CBD라면, C를 배워야 B를 배우고 B를 배워야 D를 배울 수 있다. 딕셔너리를 선언하여 스킬을 key, 배우는 순서를 value로 지정하였다.이게 가능한 이유는 스킬이 중복되지 않기 때문.  검증해보는 스킬트리를 앞에서부터 탐색하며 딕셔너리의 배우는 순서와 비교해본다.아직 배울 수 있는 순서가 아닌데 스킬을 배우려고 한다면 가차 없이 탐색을 종료하고, 스킬트리의 맨 마지막 스킬까지 탐색하여 유효함이 검증된다면 가능한 ..

2024년 6월 7일문제 링크 : 프로그래머스 - 2개 이하로 다른 비트 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 접근 주어진 10진수 x와 x보다 큰 모든 수들 중, 2진수로 변환했을 때 비트가 1~2개 다른 수 중 가장 작은 수를 구하는 문제이다. 예를 들어, x가 4일 때, 이를 2진수로 바꾸면 100⑵이며, x보다 큰 수는  5, 6, 7 ... 등등 많지만각각 2진수로 변환하면 101⑵, 110⑵, 111⑵ ... 와 같다. 이러한 x보다 큰 수들 중, 2진수로 변환했을 때 x의 2진수 변환 수보다 비트가 2개 이하로 다른 수 중 가장 작..

2024년 5월 28일문제 링크 : 백준 18352번 - 특정 거리의 도시 찾기  문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.  이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다.  2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.입력첫째 줄에 도시의 개..