오늘의 문제는 트리문제이다. 사실 간단한 트리문제인 줄 알고 접근했다가 "메모리 초과"를 당해버렸다 ㅎㅎ... 1. 출처 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 2. 설계 처음에는 쿼리수가 하나씩 주어지면 그 때마다 서브트리를 탐색하면서 count를 세줬다. 이 때 BFS를 사용했다. Queue를 사용하다보니 메모리 초과가 난 것이다. 큐를 안쓰고 어떻게 풀까? 고민했다. 그래서 모범 답안을 찾아보니 DFS + DP로 푼 개발자 분들이 많았..
BFS 등 알고리즘 공식에 빠져 순수 while for 등 반복문을 활용하는 능력이 떨어진 것 같다. 그냥 구현력이 많이 떨어진다고 느꼈던 이번 문제였다 ㅠㅠ 그래서 다시 기록하며 공부! 1. 출처 https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 2. 설계 문제가 헷갈린다. 확실히 짚고가자면, "각 플레이어마다 갈 수 있는 N칸을 가는 길도 성을 세울 수 있다" 각 플레이어의 턴마다 지을 수 있는 성을 체크하려면 DFS를 생각할 수 있겠지만 ..
1. 출처 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 2. 설계 문제 풀 때는 도저히 생각이 나지 않아서 어려웠는데 풀고 나니 별 것 아닌 문제이다. BFS의 기본 구조만 알면 거기서 2가지 포인트만 추가해주면 되기 때문이다. BFS의 기본 구조는 다음과 같다. public static void BFS(){ Queue q = new LinkedList();//갈 수 있는 경로 q.offer(new Location(1,1)); while(!q.isEmpt..
오늘은 오랜만에 백준 문제를 풀었다. 나이트 투어는 문제 자체는 쉬운데... 독해에서 난항을 겪었다 ㅋㅋㅋ 기술 블로그에 쓰신 분도 별로 없길래 남기고자 한다. 1. 출처 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 2. 설계 1) 체스에서 나이트는 어떻게 움직일까? 사실 나는 체스는 둬본 적도 없고, 관련 문제는 N-QUEEN 밖에 안풀어봐서 나이트가 어떻게 움직이는지 몰랐다. 근데 문제에도 제시가 안되어있어서 당황스러웠다. 체스 나이트는 현 위치에서 (+2, -1) (+2, 1) (-2, -1) (-2, ..
오늘의 공포 문제 순열의 순서이다... 1. 출처 1722번: 순열의 순서 첫째 줄에 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1 ≤ k ≤ N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N www.acmicpc.net 8트 끝에 맞춘 눈물나는 문제...ㅋ 2. 설계 노란색으로 형광색칠한 곳이 1번이면 순열을 보여주고, 2번이면 순서를 보여주면 된다. 그나마 원리를 알면 구현하기 쉬웠던 2번 먼저 설계를 하겠다. 2번 유형 설계 1) 4가지 수로 뽑아낼 수 있는 순열은 몇 개 일까? 1 2 3 4 1 2 4 3 . . . 등등 4자리이기 때문에 4!일 것이다. 이거에 집중해서 2번 유형을 설계해보자..
학교 탐방하기 문제... 어려워서 답보고 이해했다ㅠ 1. 출처 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 2. 설계 오답 설계 처음에는 DFS로 모든 그래프의 갈림길에 대해 검사하고, MIN 값과 MAX 값을 구해주고자 했다. 근데 하나의 위치에 가면 그 위치에서 갈 수 있는 길 중 1개만 선택하게 하는 알고리즘을 짜서 이런 경우가 절대 안나왔다. 한 위치에서 모든 갈래를 모두 선택하는 방법이 절대 안나왔던 것이다. 그래서 생각하다가 시간이 오래걸려 그냥 정답을 봤다. ..
오늘도 1문제 클리어!! 이번에는 답 안보고 내 힘으로 풀어서 더 뿌듯했다 헤헤 이 빙산 문제는 옛날에 내가 풀었던 치즈 문제와 비슷하게 느껴졌다. [BFS] 백준 2638번 치즈 - JAVA 요즘 싸피 우리반 친구들은 어떤 문제를 푸나 궁금해서 그룹에 들어가봤더니 '치즈' 문제를 많이 풀고 있어서 나도 도전했다!!! 이 문제는 10일 전에 풀었던 2636번 골드 4 문제 치즈이다. 오늘 골 tksgk2598.tistory.com 현재에 본가에 있는 나는 동생 컴퓨터를 빌려쓰고 있는데, 여기는 이클립스나 java 컴파일이 될 수 있는 환경이 없어서 아래 컴파일러 사이트를 이용했다. 새 Java 프로그램 만들기 - 마이컴파일러 - myCompiler 실행 코드 코드 저장 기존 코드를 유지하시겠습니까? 에디..
간만에 스터디 DP 문제를 풀어보았습니다. 역시 DP... 익숙치 않다보니 어렵게 느껴졌습니다 ㅠㅠ 기록하며 한 번 더 풀어보는 시간을 갖겠습니다! 1. 출처 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 누가봐도 DP 문제라고 알려주는 시간 제한... 2. 설계 사실 다른 블로그 해석을 봐도 한 번에 와닿지는 않았습니다. 이해하는 데 시간이 걸렸어요. 다들 설계는 2중 배열로 한 것 같은데 왜 1차원 배열로 점화식을 냈지? 의문이었죠... 그리하여 제가 이해한 과정을 기록해봅니다... 1) n개의 동전을 c..
