내가보려고만든 메자노트

문제 보러 가기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 백트래킹에 속해있는 문제로 완전 탐색을 통해 풀이할 수 있다. [ 적절한 탐색 조건 + 탐색을 하는 순서 ]를 찾아 접근하여야 통과할 수 있었던 거 같다. 물론 나는 헤매다가 다른 분들의 접근법을 참고하였다 ^_ㅠ 문제풀이 -가장 적게 색종이를 사용하므로 5X5의 색종이부터 탐색 -해당 색종이 영역이 다 1인지 확인 -> 다 1이면 사용할 수 있다는 의미 -해당 색종이를 사용할 수 있다면 사용하고 다른 색종이에 걸리지 않도록 0..

문제 보러 가기 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 이 문제는 카카오프렌즈들을 세우는 순서의 경우의 수 -> 순열을 구하는 문제였다! 순열을 다 구하면 시간 초과가 날까 고민했지만 그냥 모든 순열을 구해서 풀었다. 하지만 제출 시 틀리다고 나와서 뭐가 문제인지 계속 고민했는데,,, 전역 변수의 경우 main안에서 초기화를 꼭 해줘야 한다... 왜지.. 궁금하다.. 이걸로 삽질하지 말자고 올리는 풀이! -프로그래머스는 다 그런 듯..? 문제풀이 -8명을 세우는 총경우의 수는 8! = 40320 ..

문제보러가기 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이 문제는 누적 합을 응용해 나머지가 0 인 구간의 개수를 구하는 문제이다. 어떻게 풀어야 하나 해서 검색도 하고 고민.. 항상 느끼지만 기본적인 수학 지식이 있으면 좋을 거 같다 ㅎ.. 누적 합 이란 A [0] + A [1] +... A [i]+..+A [j]+...+A [n]의 숫자에서 A [i]부터 A [j]까지의 합을 구하는걸 미리 합 해놓은 S [] 배열로 구하는 문제이다. -> i~j까지의 합..

문제보러가기 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를 기반으로 이루어진다. 문제풀이 ..