모항이코딩한다

풀이방법 사용된 것: 백트래킹(backtracking) Deque 2023.01.17 숫자를 순서대로 하나 고르는 것을 한 번의 단계로 본다. 사전순 순서에 맞추어 숫자를 하나하나 고르면서, 백트래킹을 통해 모든 수열을 찾는다. 코드 Java(2023.01.17) import java.util.Deque; import java.util.LinkedList; import java.util.Scanner; public class Main { static StringBuilder sb; static boolean[] visited; public static void main(String[] args) { // TODO Auto-generated method stub sb = new StringBuilder()..

풀이방법 및 문제점 2023.01.17 (1) 시간초과가 발생했다. 논리적 풀이 방식이 틀리지는 않은 것 같다. 모든 예제가 올바르게 해결되고, 하나하나 짚어보았을 때 논리적으로 오류가 있는 부분이 없어보인다. 시간초과가 발생한 것은 출력 수 하나마다 새 스택을 하나씩 만들어 푸는 방법을 택해서인 것 같다. 사용하는 스택의 개수를 줄이고, 무엇보다도 add()와 pop()의 수행 횟수를 최대한 줄여야 할 것 같다. 하나의 스택만 사용해서 푸는 방법이 있을까? 사용한 풀이방법은 다음과 같다. 1. 입력값은 1차원 정수 배열 original에 순서대로 저장한다. 2. 반복문에서, 0부터 N-1까지의 i에 대하여 다음과 같은 과정을 수행한다. stack을 새로 하나 만든다. boolean 값 check를 선언..

풀이방법 사용된 것: 브루트포스(Brute Force) 2021.12.08 N을 1부터 N까지의 수로 모두 순서대로 나누어보면서, 나머지가 0인 숫자가 발견되면 그 숫자를 기록해두면 된다. 코드 C++(2021.12.08) #define _CRT_SECURE_NO_WARNINGS #include int main() { int arr[100] = {0}; int n, k; scanf("%d", &n); scanf("%d", &k); int index = 0; for (int i = 1; i

풀이방법 사용된 것: Stack 2023.01.10 주어진 중위 표기식을 앞에서부터 한 글자씩 훑으면서, 이번 글자의 종류가 무엇인지에 따라 아래와 같은 작업을 수행해주면 문제를 풀 수 있다. 1. 이번 글자가 피연산자인 경우 이번 글자를 즉시 화면에 출력한다. 2. 이번 글자가 왼쪽 괄호인 경우 스택에 '('를 넣어준다. 3. 이번 글자가 오른쪽 괄호인 경우 스택의 top에 '(' 가 올라올 때까지 계속해서 pop()을 하여 하나씩 화면에 출력한다. 스택의 top에 '('가 올라왔다면 그 '('는 화면에 출력하지 않고 pop()만 해준다. 4. 이번 글자가 + 혹은 -인 경우 현재 스택이 비어있지 않다면, 스택이 비거나 top에 '('가 올라올 때까지 계속해서 pop()을 하여 하나씩 화면에 출력한다...

풀이방법 사용된 것: 백트래킹 2022.11.29 오답노트 #10971 : 외판원 순회 2 풀이방법 및 문제점 2022.11.23 이번 문제도 작은 실수로 인해 틀렸던 문제이다. 백트래킹 문제를 풀 때 절대 잊으면 안 되는 사항이기 때문에 오답노트에 적어두려 한다. 재귀를 통해 각 도시를 방 blowupmomo.tistory.com 재귀를 통해 각 도시를 방문하다가, 모든 도시를 빠짐없이 방문한 것이 확인되면 출발지로 다시 돌아가는 비용을 현재까지 쌓인 비용에 더한 뒤 이번 여정의 최종 비용으로 결정한다. 단, 마지막으로 방문한 도시에서 출발지로 돌아가는 길이 없다면 이번 여정은 무효로 처리하고 정답에 반영하지 않는다. 그 다음 모든 최종 비용 값 중 최솟값을 화면에 출력하여 문제를 해결한다. 코드 Ja..

풀이방법 및 문제점 2022.11.23 이번 문제도 작은 실수로 인해 틀렸던 문제이다. 백트래킹 문제를 풀 때 절대 잊으면 안 되는 부분이기 때문에 오답노트에 적어두려 한다. 재귀를 통해 각 도시를 방문하다가, 모든 도시를 빠짐없이 방문한 것이 확인되면 출발지로 다시 돌아가는 비용을 현재까지 쌓인 비용에 더한 뒤 이번 여정의 최종 비용으로 결정하기로 하였다. 단, 마지막으로 방문한 도시에서 출발지로 돌아가는 길이 없다면 이번 여정은 무효로 처리하고 정답에 반영하지 않는다. 그 다음 모든 최종 비용 값 중 최솟값을 화면에 출력하여 문제를 해결한다. 이러한 풀이 방식은 잘 짠 것이었다. 단, 백트래킹 문제를 풀 때 꼭 기억해야 하는 사항 하나를 깜빡하여 틀렸었다. 백트래킹이란, 갔던 길을 되돌아오기를 반복하..

풀이방법 사용된 것: 브루트포스 2022.11.22 오답노트 #4436 : 엘프의 검 풀이방법 및 문제점 2022.11.22 사용한 방법은 다음과 같다. 0부터 9까지의 숫자가 담겨있는 해시셋을 선언한다. 수열에 특정 숫자가 나타날 때마다 그 숫자를 해시셋에서 remove()한다. 해시셋이 텅 blowupmomo.tistory.com 0부터 9까지의 숫자가 저장된 HashSet을 선언한다. 각 숫자가 등장할 때마다 HashSet에서 그 숫자를 remove()한다. HashSet이 텅 비는 순간 현재의 k를 출력한다. 형변환의 번거로움을 줄이기 위해 각 숫자는 Character형으로 다루었다. 그리고 곱하기를 하다 보면 숫자가 점점 커지므로, 곱한 값은 반드시 충분히 큰 정수형 데이터로 선언해주어야 한다...

풀이방법 및 문제점 2022.11.22 사용한 방법은 다음과 같다. 0부터 9까지의 숫자가 담겨있는 해시셋을 선언한다. 수열에 특정 숫자가 나타날 때마다 그 숫자를 해시셋에서 remove()한다. 해시셋이 텅 비게 되면 그 시점의 k를 출력한다. 형변환의 번거로움을 줄이기 위해 각 숫자는 int나 long이 아닌 Character형으로 하였다. 완벽한 풀이법이라고 생각했는데 33퍼센트에서 자꾸 틀렸습니다를 받는다. 무엇이 문제지...? 친구가 한 것처럼 boolean 배열이 모두 true가 되었을 때 정답을 확정하는 코드도 짜보았는데, 똑같이 33퍼센트에서 틀렸습니다를 받았다. 이걸 보니 풀이법 자체가 문제가 아닌 것 같다. 친구가 했을 때 정답 처리를 받은 코드를 내 식으로 짜보니 오답 처리가 되었기 ..

풀이방법 사용된 것: 정렬 브루트포스 Comparator Overriding 2022.11.17 콘도 X가 후보가 될 수 있는 조건은 다음과 같다. X보다 바닷가에 더 가까운 콘도들은 모두 X보다 숙박비가 더 비싸다. X보다 숙박비가 더 싼 콘도들은 모두 X보다 바닷가에서 더 멀다. 거리 순으로 정렬한 후에 1번 조건을 체크하고, 가격 순으로 정렬한 후에 2번 조건을 체크한 후, 두 번의 체크 과정에서 한 번도 탈락하지 않은 콘도들의 개수를 세면 된다. 다음과 같은 방법으로 구현하였다. 1. Condo 클래스 정의 각각의 콘도는 Condo 객체로 저장된다. Condo 객체는 다음의 3가지 필드를 가진다. 바닷가로부터의 거리 d, 숙박비 c, 후보가 될 자격을 나타내는 boolean 타입 변수 check ..

풀이방법 사용된 것: 시뮬레이션 Queue 2022.11.14 문제에서 말해주는 상황을 그대로 시뮬레이션하기만 하면 되는 단순한 문제이다. 최대 움직임 수가 50번밖에 안 되므로 시간초과 걱정이 없기 때문이다. 기본적인 풀이 과정은 다음과 같다. 1. 킹의 최초 위치와 돌의 최초 위치를 읽어온다. 2. 모든 움직임 명령을 읽어와 순서대로 큐에 저장해둔다. 3. 큐에 넣은 명령들을 다음과 같은 과정을 따라 수행한다. - 이번 명령에 따라 킹을 이동하였을 때에 킹이 판 밖으로 나가는지 판별한다. 만약 킹이 나가게 된다면 아무것도 옮기지 않고 이번 명령을 종료한다. - 킹이 판 밖으로 나가지 않는다면, 킹이 옮겨갈 위치에 돌이 있는지 판별한다. 만약 그 위치에 돌이 없다면 킹만 옮기고 이번 명령을 종료한다. ..