모항이코딩한다

풀이방법 사용된 것: 정렬 브루트포스 알고리즘 2022.06.12 주어지는 난쟁이가 9명밖에 안 되므로 브루트포스로 쉽게 풀 수 있는 문제이다. 9명 중 7명을 골라내는 문제이므로, 제외할 2명만 알아내면 된다. 9명 중 2명을 고르는 경우의 수는 72가지이다. 72가지를 모두 해보고, 키의 합이 100이 되는 경우가 발견되면 즉시 화면에 정답을 출력한다. 코드 Java(2022.06.12) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { public static void main(String[] args) ..

풀이방법 사용된 것: 정렬 HashMap TreeSet 2022.06.12 먼저 HashMap hm 을 이용해 각 책들의 판매권수를 센다. 입력으로 들어오는 책 제목들을 순서대로 하나씩 읽으면서, 처음으로 입력된 책 제목이라면 hm에 (책 제목, 1) 을 추가한다. 이전에 입력된 적 있는 책 제목이라면 hm에 (책 제목, hm.get(책 제목)+1) 을 추가한다. 이렇게 하면 마지막에는 각 책 제목에 대하여 (책 제목, 팔린 권수)가 저장되어있게 된다. 그 다음엔 TreeSet answer를 이용하여 정답을 구한다. int형 변수 max를 선언하고 1보다 작은 수로 초기화한다. hm의 KeySet의 각 요소 str에 대하여, hm.get(str)이 max와 같을 경우, answer에 str을 넣는다. h..

풀이방법 사용된 것: 정렬 수학 2022.06.12 먼저, 좋은 구간에 들어갈 수 있는 수들의 범위를 찾는다. 편의를 위해 이 범위에 속하는 수들의 집합을 T라고 하겠다. T의 모습은 N의 값에 따라 다음의 셋 중 한 가지로 결정된다. 첫째, N이 집합 S의 수들 중 하나와 값이 같을 경우, T에 들어갈 수 있는 수는 없다. 이 경우에는 정답이 0이므로 화면에 0을 출력하고 끝내면 된다. 둘째, N이 집합 S의 수들 중 가장 작은 수보다 작을 경우, T에 들어갈 수 있는 수들의 범위는 1부터 (S의 가장 작은 수) - 1 까지 이다. 예를 들어 집합에 6, 9, 12가 있고 N이 2라면 T = {1, 2, 3, 4, 5}이다. 셋째, N이 집합 S의 어떠한 두 수 사이에 낀 수일 경우, T에 들어갈 수 ..

풀이방법 및 문제점 2022.06.10 전체적인 알고리즘은 완성되었다. 그런데 check 함수의 시간복잡도가 문제이다. 여기 때문에 시간초과가 발생한다. check만 상수시간이 걸리도록 바꾸면 해결될 것 같다. ... 구글링을 하다가 아래의 블로그 글을 발견했다. 백준 (BOJ) 16564 히오스 프로게이머 java https://www.acmicpc.net/problem/16564 16564번: 히오스 프로게이머 첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 다음 N개의 줄에는.. verycrazy.tistory.com 분명히 내 코드랑 똑같은 아이디어로 짠 코드인데 이 코드를 백준에 돌려보면 순식간에..

풀이방법 사용된 것: 깊이우선탐색 2022.06.09 3184번 문제와 완전히 똑같은 문제이다. 양이 'o'가 아닌 'k'로 표시된다는 것만 다르다. #3184 : 양 풀이방법 사용된 것: 깊이우선탐색(DFS) 2022.05.25 그래프 탐색을 통해 각 영역에 속한 칸들을 탐색하고 양과 늑대의 마릿수를 세는 문제이다. 나는 깊이우선탐색을 사용하였다. 알고리즘은 다음과 blowupmomo.tistory.com 코드 Java(2022.06.09) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { s..

풀이방법 사용된 것: 이분 탐색 좌표압축 2022.06.08 간단한 코드로 풀리는 문제이지만, 좌표압축의 대표적인 예제이므로 좌표압축과 관련된 기본적인 내용까지 포함하여 자세하게 적었다. 단, 이분 탐색에 대한 설명은 적지 않았다. 이분 탐색에 대한 설명 및 좌표압축에 대한 매우 기본적인 이야기는 아래의 ICPC 강의 정리글에 있다. 관련된 신촌 ICPC 강의 정리글 초급 7회차 이분탐색 & 분할정복 이분탐색과 분할정복 모두 문제를 쪼개어 해결하는 방식임. 쪼갠다는 것은 무엇인가 문제의 크기가 크면 어렵다. 문제를 작은 부분 문제들로 나누어 풀면 쉬워진다. 문제를 쪼개고, 부분 문제들 blowupmomo.tistory.com 오답노트 #2370 : 시장 선거 포스터 풀이방법 및 문제점 2022.06.08..

풀이방법 및 문제점 2022.06.08 (1) 이분탐색을 쓰지 않고 그냥 좌표압축을 시도해보았다. 해시맵을 사용하였다. 역시 시간초과가 발생한다. 답의 값 자체는 맞게 도출되는 것 같다. 2022.06.08 (2) 이분탐색을 이용하여 좌표압축을 하니 해결되었다. 정답 게시글 바로가기 코드 Java(2022.06.08(1)) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) thro..

풀이방법 사용된 것: 분할정복 재귀 2022.06.04 재귀적으로 정의된 분할정복 함수 solve를 사용하였다. solve는 한 변의 길이가 $2^n$인 정사각형 모양의 특정 영역을 맡아서, 자신이 맡은 영역의 한 변의 길이가 2라면, 그 영역에 들어있는 4개의 수 중 두 번째로 큰 값을 리턴한다. 반대로 자신이 맡은 영역의 한 변의 길이가 2보다 크다면, 영역을 동일한 4개 구역으로 쪼개어 그 4개 구역에 대한 재귀를 수행하여 결과값 4개를 받아온다. 그 후 그 결과값 4개 중 두 번째로 큰 값을 리턴한다. 코드 Java(2022.06.04) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReade..

풀이방법 사용된 것: 브루트포스 알고리즘 사칙연산 2022.06.01 머리 쓰거나 똑똑하게 푸려고 하면 오히려 어렵다. 주먹구구식으로 하니 쉽게 풀렸다. 빈칸의 위치가 어디인지 찾아둔다. 빈칸을 제외한 모든 수에 대하여, 1 또는 3의 알맞은 가중치를 곱하여 모조리 더한다. 마지막 자리의 체크기호도 같이 더한다. 이렇게 싹 더해준 값을 sum이라 하겠다. (아래 코드에서는 빈칸 위치 찾기와 덧셈을 동시에 했다) 빈칸이 가중치 1의 위치라면 다음과 같이 풀면 된다. 0부터 9까지의 정수 i에 대하여 반복문을 돌리며, ( sum+i ) % 10 == 0 을 만족하는 수가 발견되면 그 수를 정답으로 취한다. 반대로 빈칸이 가중치 3의 위치라면 다음과 같이 풀면 된다. 0부터 9까지의 정수 i에 대하여 반복문을..

풀이방법 사용된 것: 깊이우선탐색(DFS) 너비우선탐색(BFS) 스택(Stack) 큐(Queue) 2022.06.01 기본적인 DFS와 BFS를 둘 다 사용해보는 스탠다드 문제이다. 스택을 이용해 DFS를 해주고, 큐를 이용해 BFS를 해주었다. 단, 방문할 수 있는 노드가 여러 개 있을 때엔 노드의 번호의 크기가 작은 것부터 방문한다는 점에 주의해야 한다. 이 때문에 스택에는 자식노드들을 내림차순으로 넣어주고, 큐에는 오름차순으로 넣어주었다. 인접 리스트의 내용물의 정렬은 TreeSet의 자동 오름차순 정렬과 desceningSet 기능을 이용하여 해결했다. 코드 Java(2022.06.01) import java.io.BufferedReader; import java.io.IOException; im..