본문 바로가기

분류 전체보기

 (88)
백준 2615 <오목> DFS를 사용하는 완전 탐색이다. 5목이 아닌 6목 그 이상이 되는 예외 상항만 처리해주면 되기 때문에 생각보다 어려운 문제는 아니었다. 다만 문제를 해결하면서 시간 복잡도를 최소화하는 방법을 찾는데에 집중했던 문제였다. 시간을 줄이기 위해 이문제에서 사용된 방법은 바둑돌이 놓인 지점에서 이렇게 8방향을 탐색하는 것이 아닌 5목이 된다면 출력을 하게될 바둑돌의 좌표는 가장 왼쪽 그리고 가장 위쪽에 있는 좌표이기 때문에 이렇게 4방향만 검사를 해주게 되면 출력할 좌표를 쉽게 구할 수 있고 시간을 간편화 할 수 있다. 총 20*20의 맵이기 때문에 2중 for문을 사용해주었고 그 지점이 흑돌 또는 백 돌일 때 탐색을 실행시켜주었다. 각 돌의 지점에서 시작점을 포함해 5번을 이동하면서 이동한 지점의 돌이 같을..
백준 15961 <회전초밥> 일반적으로 알고 있는 투 포인터 문제이다. 물론 투 포인터라는 개념을 알고 있지 않으면 풀 수 없는 문제이다. 투 포인터라고 생각하게 된 이유는 접시의 수가 3000000으로 300만 개 연속으로 먹는 접시의 수가 3000으로 각각을 시작점으로 두고 3000번간다고 치면 300만*3000 90억이라는 어마어마한 수가 나오기 때문에 당연히 안 될 것이라고 생각했기 때문이다. 문제의 알고리즘을 이해하자면 이렇다 총 30가지 종류의 초밥이 있기때문에 체크를 해줄 배열을 만들고 시작점으로부터 연속해서 뽑을 때까지 체크를 해준다 현재는 4개까지 고를 수 있기 때문에 이렇게 3가지 종류의 초밥을 먹을 수 있게 된다. 이 이후에는 시작점으로부터 한 개씩 줄이고 끝점인 30의 위치부터는 증가시키면서 계속 이런 식으로 ..
백준 3109 <빵집> 이 문제는 DFS 문제임과 동시에 어떻게 하면 갔던 곳을 방문하지 않게 할까? 가 주요한 문제이다. 이 문제를 해결하기위해서는 두 가지 신경 써줘야 하는 부분이 있었다. 길을 연결 하고 나서 돌아갈 때 처리 방법 길을 연결 하지 못했다면 돌아갈 때 처리 방법 첫 번째 방법은 return 값을 boolean형으로 선언해서 true로 리턴하게 하면 된다. 다른 방법은 flag를 한 개 선언해서 이용해주면 된다. 이렇게 처리해 주지 않으면 이렇게 다음 빈 공간으로 이동하기 때문에 원래 값은 1이 되어야 하는데 2가 출력되게 됩니다. 두 번째 방법은 이미 방문했던 곳을 다시 방문할 수 없게 방문처리를 계속하는 것입니다. 그렇지 않으면 이전에 방문했지만 방문 표시를 제거해줬기 때문에 그 지점을 다시 방문하게 되어..
백준 1194 <달이 차오른다,가자> 우선 문제에서 이동 횟수의 최솟값을 구하라고 했기 때문에 BFS를 이용해야 하는 문제이다. 그리고 한가지 더 주의해야 할 점은 각각의 이동 시마다 가지고 있는 키를 알고 있어야 하는 문제이다. 각각의 가지고 있는 키의 정보를 저장하기 위해 key[] 배열을 가지고 있어도 되지만 크기를 줄이기 위해 비트 연산을 사용하도록 하는 문제이다. 비트 연산을 알지 못하면 어려운 문제이다. 전체적인 맵에서 각각의 키를 가지고 있는지 표시하기위해 1
백준 15686 <치킨 배달> 이 문제도 마찬가지로 조합을 구할 수 있냐 하는 문제인 것 같다. 치킨집이 최대 13개이기때문에 최대 13 C m 이 될 것이고 이 값은 1만이 넘지 않는다. 집의 개수는 최대 2 * N 개가 넘지 않으니 최대 100개 이므로 집에서 치킨집까지의 모든 거리를 계산해도 천만? 정도가 될 것이다. 이 문제는 이전 문제와 다르게 접근을 해보았는데 visit배열을 이용해서 방문을 체크해주고 방문한 경우에는 num+1을 해서 재귀를 해주도록 하였다. 이 문제에서 주의해야 할 점은 최대 M개를 고르는 문제라고 하여 그 이하의 경우도 생각해주어야 하는가? 였다. 답은 당연히 No!이다. 우리가 구하는 것은 집에서 가장 가까운 치킨집을 고르는 것이기 때문에 치킨집의 개수는 많을수록 좋다. 그다음은 각각의 집에 대해 가..
비트 연산자를 이용한 순열과 부분집합 비트 연산자의 기본을 이해하기 위한 설명 및 사용법 비트 연산자를 사용하는 이유가 무엇인가? 일반적으로 비트 연산자는 이미 자신이 방문한 곳을 체크해주기 위한 boolean배열을 이용해서 나타내는 곳에 사용한다. 하지만 단순히 비트연산자를 방문한 곳을 체크해주기 위한 용도로 사용된다는 것은 이해가 어렵다. 예를 들어 총 10곳의 방문체크를 해줘야 하는 곳을 만들게 된다면 boolean visit [10]; 이렇게 하면 쉽게 해결될 것이다. 그렇다면 이것을 비트 연산자로 나타내게 되면 0000000000 이렇게 총 10자리가 되어 int형으로 나타나게 될 것이다. 이렇게 하면 int형은 4바이트 boolean은 10바이트 6바이트 밖에 차이가 나지 않는다. 그렇다면 굳이 이 6바이트 차이 때문에 비트 연산..
백준 14889 <스타트와 링크> 일반적인 조합 문제이다 최대 20 C 10 이기 때문에 184756번이고 10명의 팀원을 각각 값을 계산해도 100이므로 184765*10 하고 두 팀이니 x2 해서 400만이 되지 않기 때문에 시간 내에 무사히 통과할 수 있는 문제이다. 삼성 A형 테스트 치고는 접근하는 방향도 생각하기도 쉬웠던 문제이다. 20명의 사람 중 절반을 나누는 조합이 부분이다. find 함수에서는 a팀에 속하지 않은 사람들을 b의 배열에 넣고 각각의 사람들을 기준으로 팀의 능력치를 구하고 난 뒤 두 점수의 최소 차이를 구한다. visit 함수를 이용해서 a팀에 속해있는 인원을 1로 만들어주고 차후에 a팀을 제외한 인원을 b팀에 넣어준 코드이다. 그 후에는 간단하게 각팀의 능력치를 계산해줘서 최소를 대입해주면 끝나는 간단한 문..
백준 17142 <연구소 3> 이전에 풀었던 연구소 1 보다 어려워진 문제이다. https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 이 문제를 풀기 전에 위의 링크의 연구소를 풀지 않았다면 먼저 풀고 이 문제를 풀기를 바란다. 위 문제와 유사하게 바이러스의 개수는 최대 10개이기 때문에 M개가 주어지면 10 C M 조합을 이용하여 확산할 바이러스를 구하고 해당 바이러스를 Queue에 넣고 BFS를 해서 최소 시간을 구하는 문제이다. 이 문제를 풀면서 가장 중요하다고 느꼈던 건 예외사항을 ..
파일 입 출력과 객체 직렬화 입력 bufferedReaer br =new bufferedReaer(new InputStreamReader(new FileInputStream)) FileInputStream à파일의 형태를 byte로 받아 옴 InputStreamReaderà byte 형태를 단어 char로 바꿔서 정리 bufferedReaeràchar형을 인식 char형으로 하는 이유는 우리가 다룰 때 byte 형태보다 char형이 접근이 용이함 BufferInputStream br=new BufferInputStream (new FileInputStream)); BufferInputStreamà byte 형태로 입력을 받음 !! FileInputStream 이후에 BufferInputStream를 사용하는 이유는 버퍼에 저장을 해..
백준 1600 <말이 되고픈 원숭이> 기존의 BFS 방법에서 조금 어려워진 탐색 문제이다. 고려해야 할 점은 BFS탐색을 하면서 말처럼 이동하는 횟수가 K번 이내, 나머지는 원숭이처럼 이동해서 목적지로 이동할 수 있는지 체크를 하는 문제이다. https://skygood95.tistory.com/2 백준 2206 단순하게 생각하고 구현하면 되는 전형적인 BFS, DFS문제!! 벽을 한 번까지 부수고 종점까지 가면 되는 문제 생각했던 방법은 총 2 가지 방문한 배열을 visit [][][] 이렇게 구현해서 3차원 배열을 만 skygood95.tistory.com 이전의 이 문제에서 조금 더 업그레이드 된 문제라고 보면 되겠다. 전체 맵의 범위가 200*200 총 40000번 그리고 k가 최대 20이기 때문에 800000 즉 80만 번 이기 때..

티스토리툴바