내가보려고만든 메자노트

문제보러가기 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제는 그래프 탐색 문제로 주어진 노드가 한 팀이 되는지 -> 사이클이 이뤄지는지 확인하는 문제였다. dfs를 통해 풀이하였다. 문제풀이 처음에는 단순히 1번이 선택한 사람이 2번이면 1->2 이동후 2번이 선택한 사람 순으로 탐색을 진행하였다. 탐색을 진행하다가 start 한 1번이 다시 나오게 되면 사이클이 이뤄지므로 해당하는 사람들이 한 팀이고 이를 카운트 변수인 cnt에 담아 인원수를 판별하였는데 아래와 같은 경우의 반례가 존재했다. 이런 그래..

문제보러가기 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 그 유명한 N-Queen 문제로 체스판에 퀸을 서로 공격할 수 없게 놓는 방법이 몇 가지가 있는지를 구하는 문제이다. 분명히 학교 다닐 때 배웠던 거 같은데,, 까먹지 말도록 기록! 문제풀이 -같은 열(row)에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다. -같은 행(col)에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다. -해당 위치의 대각선에 다른 퀸이 있으면 해당하는 곳은 놓을 수 없다. -board [row]=col 배열을 통해 해당 row에..

팰린드롬 문제를 접하고 비슷한 문제들의 다양한 풀이 방법을 모아보았다. 단순히 팰린드롬인지 확인하는 문제가 아닌 문자열의 부분문자열이 팰린드롬인지, 그중 가장 긴 길이는 얼마인지 찾는 문제를 풀어보았다. 그냥 탐색이 아니라 알고리즘 적용해서 푸는건 아예 모르겠어서 여기저기 찾아보고 manacher알고리즘을 알게 되었다! 팰린드롬(Palindrome)이란? abcba 처럼 양쪽이 대칭이 되는 문자열을 의미한다. 한 글자의 a 두 글자의 aa 역시 팰린드롬이다. 프로그래머스-가장 긴 팰린드롬 이 문제는 주어진 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 찾는 문제이다. 문자열 최대길이가 2500 이므로 넉넉하게 각 인덱스마다 탐색으로 진행하면 되겠다. public class LongestPalindr..

문제보러가기 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 이 문제는 투 포인터 알고리즘을 접해봤다면 이 알고리즘을 써야겠구나 라고 바로 알 수 있다. 신경 써줘야 할 점은 중복이 가능한 문자열이라는 점! 문제풀이 - 왼쪽 시작 포인터 s와 오른쪽 끝 포인터 e를 이동해가면서 최대 길이를 찾는다 - 알파벳의 종류의 수를 체크하기 위해 Map을 이용한다 - Map의 size()가 주어진 종류의 수 보다 크다면 s++하고 해당 문자열을 key로 갖는 value를 -1 해준다. 만약, -1 했을 때 value==0이라면 m..

문제보러가기 이 문제의 경우 그래프 탐색 유형에 속해 있으며 bfs, dfs, 플로이드와샬등 다양한 풀이 방법으로 해결이 가능하다고 한다. 처음 문제를 접했을 때는 금방 풀릴 거 같았지만 생각보다 어렵게 느꼈고 다른 분들의 풀이 방법을 참고하여 해결하였다. 플로이드 와샬이라는 방법을 몰랐기 때문에 공부하였고 이 알고리즘으로 풀이를 하였다. -플로이드 와샬 기본문제 (백준 11404- 플로이드) 플로이드 와샬 이란? 다익스트라 알고리즘과 같이 정점-정점 간의 최단거리를 구하는 알고리즘이다. 차이점으로는 다익스트라는 하나의 고정된 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이고, 플로이드 와샬은 모든 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이다. 또한 dp를 기반으로 이루어진다. 문제풀이 ..

문제보러가기 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 이 문제는 기존 bfs처럼 영역을 나눠서 영역의 개수, 영역의 최대 넓이 , 벽을 하나 제거한 후의 영역의 최대 넓이를 구하는 여러 문제가 합쳐져 있는 복합적인(?) 문제였다. 여기서 까다롭게 봐야 할 점은 벽을 제시할 때 0~15의 값으로 주어지며 이를 bit로 변환하여 사용해야 한다는 점이었다. 문제풀이 - bfs로 구한 영역을 증가하는 groupCnt를 키값으로 묶어 아래 그림처럼 group [][]에 저장해준다. -bfs로 영역을 구할 ..

문제보러가기 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 이문제는 당시에 난이도 상에 포함되었던 문제라고 한다. 막상 풀이를 보게 되면 별거 없는 거 같지만, 어떻게 구현해서 풀어야겠다는 감이 잘 오지 않을 수 있다! 나의 경우는 문제 이해부터가 오래 걸렸던 거 같다 ㅎ.. 문제풀이 - 크루들의 도착시간인 timetable을 int로 변환하여 오름차순으로 정렬하기 위해 PriorityQueue에 저장한다. - 첫차 출발시간인 09:00시부터 t분 간격으로 ..

문제보러가기 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 이문제는 전형적인 탐색 문제로 연결된 영역이 몇 개가 있는지 구하는 문제였다. 다른 점이라면 위, 아래, 오른쪽, 왼쪽이 아닌 대각선 포함 8방향으로 탐색해야 한다는 점. 문제풀이 -map [][]에 입력받은 값을 저장해준다. -map을 이중 for문으로 탐색하면서 1일 경우(섬일 경우) 그리고 방문하지 않았을 경우에 bfs()를 수행한다. -4방향이 아닌 대각선 포함 8방향으로 체크해주면서 연결된 섬의 개수를 체크한다. 사실 이문제는 "메모리..