본문 바로가기

분류 전체보기

 (88)
백준 2563 <색종이> 색종이의 수가 100이하이고 흰색도화지 크기가 100이기때문에 완전탐색으로도 가능한 문제이다. 그렇지 않다면 인덱스 트리를 이용해서 풀어야하는 문제이다. 이 문제의 시간 복잡도를 계산한다면 최대 색종이의 수*도화지의 크기*색종이의 크기 이므로 100000 10만이 될것이다. 이러한 문제는 시간복잡도를 게산하면서 풀면 더욱 도움이 될것이다. 문제 해결순서 boolean형 visit 2차원 배열에 각각의 색종이 시작점으로 부터 10크기만큼 체크해준다 겹치는 부분이면 어차피 true기때문에 신경 안써줘도 됨 마지막에 전체 도화지 크기에 몇개의 true가 있는지 확인 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java...
백준 2578 <빙고> 간단한 시뮬레이션 문제이다. 문제의 해결방법 철수의 게임판에서 사회자가 부른 수를 찾아 visit처리를 한다. 철수의 판에 빙고가 몇 개 완성되었는지 확인한다. 3이 넘으면 출력한다. 철수의 게임판에서 사회자가 부른 수를 찾기위해 사회자가 부른 수와 몇 번 불렀는지 정보를 넘겨준다. find 함수 안에서 철수의 판에서 호출한 번호를 visit 처리를 한다. 가로 세로 검사를 하는 소스이다. 대각선을 검사하는 소스이다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenize..
백준 2605 <줄 세우기> 이 문제는 ArrayList 즉 정렬을 얼마나 알고 있냐 하는 문제였다. 학생의 수가 100 이하이기 때문에 ArrayList 삽입으로도 해결할 수 있는 문제였다. 이 문제의 핵심은 ArrayList .add(index, element); 를 이용해서 index번째에 elenets를 추가하는 간단한 문제이다. 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main{ static ArrayList a; static int num[],n; ..
백준 2309 <일곱 난쟁이> 총 9명의 난쟁이 중에 7명을 선택 하는 조합 문제이다. 간단하게 조합을 알고 있다면 금방 해결할 수 있는 문제이다. 문제 해결 순서 난쟁이들을 키순서대로 정렬 9명의 난쟁이로 7명의 난쟁이를 선택한다. 난쟁이의 키가 100이 된다면 return 또한 7명의 난쟁이를 선택하는 경우 == 전체의 난쟁이 중 2명을 빼는 경우이기 때문에 반대로도 해결이 가능하다. 전체 코드 더보기 import java.io.IOException; import java.util.Arrays; import java.util.Scanner; public class Main{ static int num[], result[]; static boolean flag = true; static StringBuilder s = new Str..
백준 14466 <소가 길을 건너간 이유 6> 문제를 이해하는데 시간이 오래 걸렸던 문제 기본적으로 이렇게 소와 다리가 위치하고 있다. 주황색 소에서 하늘색 소로 가는 경우는 다리를 이용하지 않고 이렇게 이동할 수 있다. 그러나 주황색 소에서 초록색 소를 가려면 무조건 다리를 건너야 한다 파란색 소에서 초록색 소도 마찬가지이다. 이렇게 되면 다리를 건너야 하는 소들은 총 2쌍이다. 그러므로 이 문제는 각각의 소에서 다리를 이용하지 않고 다른 소들을 방문 할 수 있냐? 하는 문제이다. 결과적으로 쌍을 구하는 것이기 때문에 자기보다 뒤에 있는 소들만 계산해주고 앞에 있는 소들은 계산할 필요가 없다. 문제 풀이 각각의 소에서 BFS를 해서 다리를 이용하지 않은 완전 탐색을 한다. 자신보다 이후에 위치한 소들이 방문 되지 않았다면 count를 증가시킨다. ..
백준 16235번 <나무 재테크> 최악의 시뮬레이션.... 시간 초과가 무엇인지를 제대로 보여주는 시뮬레이션이었다... 이문제를 풀면서 느낀 건 시간!! 시간!! 시간이다.. 이 문제의 핵심은 시뮬레이션대로 어떻게 시간을 줄여줄 건인가 였다. 문제 풀이 모든 나무들을 live라는 queue에 넣어주고 나이가 작은 순으로 collections.sort 해준다. 4 계절대로 흐름을 구성한다. 봄 --> live큐에서 꺼내서 양분을 먹을 수 있으면 나이를 먹고 live에 다시 넣어주고 안되면 die queue에 넣어준다. 여름 --> die 큐에서 꺼내서 양분으로 준다. 가을(가장 까다로움) --> 작은 순으로 다시 live에 넣어줘야 하기 때문에 p라는 큐를 만든다. *live에서 꺼낸 큐를 p에 넣고 5로 나눠진다면 8방향 중 가능한 곳의..
백준 17780 <새로운 게임> 내가 접한 시뮬레이션 중에 가장 어려운 축에 속하는 시뮬레이션 문제... 실제로 시험 칠 때도 마찬가지였지만 다시 봐도 헷갈리는 문제! 문제 풀이 순서 1000번을 진행하면서 각각의 말이 아래 지점인지 확인! 아래의 말일 경우에 파란색(범위가 벗어날 경우) , 빨간색, 흰색 경우를 고려해준다. 파란색일 경우 현재위치에서 방향을 바꿔 이동한다. --> 이 경우!! 이동 한 지점이 무조건 흰색이거나 파랑이 아니다!! 빨강일 경우도 있다! 빨강일 경우 순서를 뒤집어 준다! 흰색일 경우 모든말 그대로 움직인다. 현재 위치의 말의 수가 4개 이상이면 return~ 이 문제의 경우 시뮬레이션 문제를 많이 풀어봤었다면 생각할 수도 있는 문제였다. 각각의 말의 정보를 저장하기위한 miniun class를 따로 선언해줬..
백준 6087 <레이저 통신> 우선순위 큐를 사용해봤다면 생각보다 어렵지 않았던 문제 우선순위 큐를 사용하여 거울을 작게 설치한 것부터 큐에서 꺼낼 수 있도록 한다! 문제 주의사항! 90도로 회전하거나 직선으로 가는 총 3가지 경우만 생각해준다.--> 즉 뒤로 반사되는 경우는 없음! 문제 해결 순서 시작점을 정해서 우선순위 큐에 넣어준다. 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가시켜주지 않는다. 큐에서 꺼낸 점이 종료점이면 result에 count값을 넣고 return 한다 현재의 좌표와 거울을 세운 갯수와 이전의 방향을 나타내기 위한 변수를 who라는 클래스에 선언! BFS를 돌면서 90도로 회전하게 되면 count를 1 증가시켜주고 직선으로 가게 되면 증가 X 이 부분에서 특이한 점이 있다면 중..
백준 2174 <로봇 시뮬레이션> 가장 기본적인 시뮬레이션.. 골드 5여서 쉽게 문제 읽다가는 틀렸습니다! 뜨는 그런 문제.. 문제는 간단하다 각자의 위치에서 명령대로 수행하다 벽을 만나거나 다른 로봇과 부딪히면 종료하는 문제! 이문제에서 주의해야 할 점은 !! 맵과 방향!! 이렇게 뒤집어서 보게되면 N이 동쪽을 가리키게 되고 일반적으로 생각했던 방향과 다르게 된다는 점!! 기존에는 dir [][] = {{ -1 , 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; 이렇게 동 서 남 북이었다면 dir [][] = {{ 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } }; 이렇게 구성을 하는 것이다. 물론 첫 번째처럼 하려면 N이 방향 1이라고 줘도 되긴 한다! 나머지는 간단하다. 로봇의 위치와 방향..
백준 11000 <강의실 배정> 알고리즘 중 내가 어렵다고 생각한 그리디 부분의 문제이다. 이 문제에서 생각할 것은 얼마나 많은 수업이 겹치냐!이다. 그리디로 밖에 풀 수 없는 이유는 S와 T의 범위가 10의 9승으로 모든 N개 범위가 0부터 10의 9승이라면 10의 9승 곱하기 20만= 즉 엄청난 숫자가 되므로 당연히 X 다른 방법으로 N을 종료 시간 순으로 정렬해서 계속 비교해주게 된다면 N의 제곱! 20만의 제곱으로 시간을 마찬가지 로 터지게 된다. X 이 문제가 다른 문제에 비해 까다로웠던 이유는! 두 가지 단계를 거쳐 판단해야 했기 때문이다. 이 문제의 순서는 두 단계이다. 시작시간으로 정렬 우선순위 큐를 사용하여 종료시간이 짧은 순으로 나올 수 있게 한다!! 여기서 2번의 우선순위 큐를 사용한다고 생각을 하게 되는 것이 가장..

티스토리툴바