알고리즘/BOJ 썸네일형 리스트형 1941번 1941번 - 소문난 칠공주 처음에 단순히 dfs 백트래킹으로 풀려고 했으나, 십자가 중간에 튀어나온 모양은 dfs로 풀기가 어려웠다. 삼성에서 기출문제로 나왔던 문제가 있었는데, 그 문제는 dfs 로 돌리고 남은 모양은 직접구해서 맞추는 문제였다. 하지만 이 문제는 그러한 방식으로 조차 풀 수가 없었다. 그래서 다른 사람들의 코드를 봤다. 로직은 항상 25개 중에서 7개를 뽑는 식이기 때문에 go 함수를 통해서 7개의 수를 뽑는다. 이때 가지치기를 통해서 Y가 4개 이상이면 return 해주는 방식으로 문제를 푼다. 여기서 배운 스킬은 맵을 0 ~ 24까지 숫자로 놓으면 x,y 좌표는 [번호/n][번호%n] 이 된다는 점이었다. 이를 가지고 7개의 수를 뽑는 방식도 쉽게 풀 수 있었다. 그리고 뽑은 7.. 더보기 2023번 2023번 - 신기한 소수 처음에 에라토스테네스의 체를 이용해서 문제를 풀려고 했지만, 오히려 메모리 초과가 발생했다. 그래서 질문 게시판을 보고 힌트를 얻어서, 재귀함수를 통해서 정답을 구했다. 앞에서 부터 숫자를 채워가면서, 그 수가 소수인지 판별하는 함수를 만들어서 확인해줬다. 맨 앞 숫자는 0과 1이 들어가면 안된다는 점을 예외로 체크해줬다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include#include#include#includeusing namespace std;int n; bool checkPrime(int num){ for (int i = 2; i*i 더보기 2661번 2661번 - 좋은 수열 로직은 작은 수를 만들으라고 했기 때문에, 1-2-3 순서로 넣어가면서 넣어지면 바로 다음 단계로 넘어가면 된다. 다음 수를 넣을 때는, 우선 기본적으로 이전의 수는 뛰어넘도록 했다. p!=i 인 구문 그 다음으로 체크 함수를 통해서 문자열이 만들어졌을 때, 문자열 길이를 기준으로 반나눠서 끝에서 부터 한개, 끝에서 두개, 이런식으로 비교를 하도록 만들었다. 이때 substr 함수를 써서 string 을 쉽게 다룰 수 있었다. 평소에 substr 함수는 인자를 한개만 넣어서 사용했는데, 두개 넣을 경우 시작점과 갯수를 넣어주면 된다. 처음에 시작점과 끝점을 넣는 줄 알고 풀다가 오류가 발생했다. 12345678910111213141516171819202122232425262728.. 더보기 1339번 1339번 - 단어 수학 기본적인 로직은 만약 ABC라고 할 경우 , c라는 벡터 배열에 C 1개, B 10개, A 100개 라고 넣어준다. 그리고 이 c 벡터 배열을 sort 하고 가장 많은 값부터 9를 집어넣어서 수를 만들면 최대값이 완성된다. ## substr 사용법을 잊어버려서 다시 공부했다. substr(a)는 a번 자리부터 마지막까지 문자열을 반환하기 때문에, 이 문제에서는 문자열을 처음에 reverse 시켜주고 문제를 푸는데 사용했다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include#include#include#includeusing namesp.. 더보기 6064번 6064번 - 카잉 달력 규칙을 찾아서 풀면 간단하게 풀 수 있는 문제였다. 처음에 나는 규칙을 찾았지만, 같은 규칙을 아주 복잡하게 구해서 문제를 푸는데 어려움을 겪었다. 규칙을 간단하게 말하면, 둘 중 하나의 숫자에 맞춰놓고, 칸을 옮겨가면서 있는지만 확인하면 된다. 이때 MAX값은 두 길이의 최소공배수가 된다. 그래서 최소공배수는 유클리드 호제법을 이용한 최대공약수를 이용해서 풀었다.(유클리드 스펠링이 사실 uclid 가 아님) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include using namespace std; .. 더보기 3055번 3055번 - 탈출 풀기전에 나름 쉬운문제라고 생각했는데, 여러 가지 명시해주지 않은 조건을 간과해서 수정을 여러번 했다. 일단 생각한 로직은 첫번째로 BFS를 통해서 물이 갈 수 있는 최단거리를 저장한다. 이때, D 나 X에는 갈 수 없다. 두번째로, BFS를 통해 비버가 갈 수 있는 최단거리를 저장한다. 이때, X 나 * 에는 갈 수 없다. 또한 비버는 물이 갈 수있는 시간보다 빠를때에만 그 칸으로 이동할 수 있다. 물과 같은 시간이나 그 이상 시간에 오면 물이 범람한다. 물이 갈 수 있는 경로는 초기값은 INF로 설정하고, 비버가 갈 수 있는 경로는 -1로 설정한다. 왜냐하면 물이 갈 수 없는 곳, X를 제외하고는 비버가 무조건 갈 수 있게 하기 위함이다. 또한 물이 여러곳에서 올 경우 , 최소거리.. 더보기 12851번 12851번 - 숨바꼭질2 처음에 나는 탐색하는 모든 정점을 큐에 계속 넣고, 답을 찾고, 답보다 깊은 곳에 도달하면 나와서 출력하도록 했다. 근데 이는 예상대로 너무 많은 정점이 큐에 들어가고, 메모리 초과가 발생했다. 그래서 다른 사람들 풀이를 보니까, 큐에서 pop 될때 방문 체크를 하면 된다고 했다.. 이해가 안갔다.. 왜 그런지는 설명이 없었다. 그래서 계속해서 생각해보다가, pop 될때 방문체크를 하면, 중복해서 큐에 들어갈 수 있고, 높이가 같은 것들은 모두 집어넣을 수있다. 다른 의문점 하나는, 혹시나 이미 체크된 정점에서 정답값이 나올 수 있지 않겠느냐였다. 하지만 이미 체크된 정점에서 나오는 값에서 정답이 나온다면, 무조건 깊이가 깊어지는 것이 분명하다. 예를 들어 1이라는 루트 노드에.. 더보기 9328번 9328번 - 열쇠 푸는데 3~4시간 정도 걸린 것 같다... 마치 BFS와 시뮬레이션 문제를 섞어놓은 듯했다.. 나한테는 일단 기본적인 로직은 , BFS를 계속 돌리면서 찾을 수 있는 열쇠랑, 문서를 다 찾는 것이다. 문제에서 기본맵의 바깥에서 들어오기 때문에, 가장 바깥쪽 테두리만을 검사하고 BFS를 수행하도록 2중 for문을 이용했다. 그럼 문제는 BFS를 몇번 돌리냐 인데, 나는 새로운 열쇠를 발견하면 BFS를 돌리도록 하였고, 찾지 못하면 더 이상 BFS를 돌리지 않았다. 열쇠를 찾느냐 마느냐는 updated 변수를 이용해서 나타냈다. 열쇠는 중복되지 않도록 map 을 이용해서 구현하였다. 그리고 열쇠를 찾거나, 열쇠를 통해서 문을 열수 있거나, 문서를 찾으면, 그 지역을 그냥 통과할 수 있는 .. 더보기 이전 1 ··· 12 13 14 15 16 17 18 ··· 40 다음