알고리즘 썸네일형 리스트형 4698. 테네스의 특별한 소수 4698. 테네스의 특별한 소수 에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 소수 문제. main 함수가 실행하고 난 뒤에 곧바로 에라토스테네스의 체를 이용하여 모든 소수를 구할 수 있다. (이때 1은 따로 처리를 해줘야 한다) 그리고 구해진 소수 중에서 주어진 범위안의 수를 찾고, 그 수가 D라는 숫자를 포함하는지를 검사하면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include#include#define MAX 1000001using namespace std; bool isPrime[MAX]; void era(){ for (int i = 2; .. 더보기 4740. 밍이의 블록게임 4740. 밍이의 블록게임 시간을 꽤나 써버린 문제이다. 기본적으로 시뮬레이션 문제에, 블록 최대 크기를 구하는 부분에서는 DFS문제를 이용했다. U,L,R,D 이 네가지 경우로 케이스를 나누어서 문제를 풀었다. U 같은 경우에는 일단 check() 함수를 통해서 배열의 맨 상단의 한줄이 비어있는지 확인하는데 사용했다. 만약 비어있다면 새로운 줄을 추가 할 수 있다는 것이고, 그렇지 않다면 새로운 줄을 추가할 수 없다. 처음에 이 부분에서 실수한 점은 맨 처음에는 can_add 라는 변수를 쓰지 않고 check() 함수를 두번 호출했는데, 그럴경우 처음 호출에서는 true 가 나왔음에도 두번째 check() 함수에서는 MOVE_UP() 함수를 통해서 밑에 한줄을 추가해서 두번째 check() 함수에서는 .. 더보기 4615. 재미있는 오셀로 게임 4615. 재미있는 오셀로 게임 시뮬레이션 문제. 입력받은 값을 바탕으로 reset_map 함수를 실행시킨다. 함수 속에서는 8가지 방향을 탐색하면서 while 문 2개를 실행시키게 된다. 첫번째 while 문에서는 한쪽 방향으로 움직이면서 시작값과 같은 값(흑,백) 을 가지는 값을 찾을 때까지 진행한다. 만약 같은 값을 찾는다면 그 path 의 모든 색깔을 바꿔야 하기 때문에 다시 while문을 통해서 모든 값을 바꿔준다. 같은 값을 찾지 못한다면, 바꿔줄 필요가 없다. 처음에 첫번째 while 문에서 && map[nx][ny]!=0) 에 이 부분을 빠뜨렸는데, 이 부분을 빠뜨리면 처음에 맵을 0으로 초기화 했기 때문에 빈공간도 모두 흑이나 백으로 바꾸게 되는 문제점이 생긴다. 1234567891011.. 더보기 4751. 다솔이의 다이아몬드 장식 4751. 다솔이의 다이아몬드 장식 각 라인마다 다섯글자를 반복하도록 하였다. 단 마지막 글자의 경우에는 배열의 한칸씩 당겨서 map 변수에 저장하도록 하였다. 그리고 출력할 때는 map 에 0값을 집어넣고 0이 나올때까지 출력하면서 모두가 출력되도록 하면 끝 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116#include#inc.. 더보기 5427번 5427번 - 불 BFS 문제 두가지 요인을 같이 BFS를 통해서 움직여줘야 한다. 큐에 움직이는 사람과 번지는 불을 같이 넣으면서 함께 이동시켜줘야 한다. 그래서 나는 일단 사람을 이동시키고 불을 이동시키는 방법으로 BFS를 구현해주었다. 큐는 FIFO 이라는 점을 이용하여 일단 사람의 위치를 큐에 먼저 넣어주고, 그 다음에 불의 위치를 큐에 넣어주었다. 그리고 while 문 안을 돌면서, 큐에서 꺼낸 값이 사람의 위치인가 불의 위치인가를 파악했다. 사람의 위치라면, for문을 돌면서 상하좌우에 사람을 이동시킨다. 단 사람은 ' . ' 이라는 빈 공간으로만 움직일 수 있다. 그리고 만약 사람의 위치일때 map의 가장자리에 존재한다면 탈출 할 수 있다는 뜻이므로 cango를 true로 만들고 while .. 더보기 1331번 1331번 - 나이트 투어 시뮬레이션 문제. 주어진 순서대로 나이트가 움직여야 하기 때문에, 입력을 받으면서 map 변수에 0번부터 35번까지 순서를 입력해주었다. 그 후에 0~35번까지 for문을 돌면서 , 각 각의 나이트가 움직일 수 있는 8가지 방향을 체크했다. 시작점인 0번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 1번 칸이 존재하면 움직인다. 1번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 2번 칸이 존재하면 움직이다. . . . 마지막 35번째 나이트가 8가지 방향을 돌면서, 다음으로 이동해야할 0번째 시작점이 존재하면 움직인다. 이런식으로 문제를 풀어나가면서 만약 탐색해서 다음 칸을 찾지 못하면 INVALID 가 된다. 하지만 마지막까지 다 탐색할 수 있다면 VALID.. 더보기 1952번 1952번 - 달팽이2 간단한 시뮬레이션인 줄 알았는데, 은근히 뭔가 안돼서 계속 고쳤다. 일단 처음에 메인 함수의 while 문에서 코드를 간결하게 하려고 해보았지만, x+dx[dir] 이 사용되는 곳에 따라 바뀌어야 하기 때문에 if 문에서 x+dx[dir], y+dy[dir] 부분과 if문 벗어나서 그 부분이 다르기 때문에 한번 다시 써줘야했다...최적화 안됨 그리고 범위가 벗어나는 경우를 처음에는 무조건 돌면서 가운데로 들어오기 때문에 map[x+1][y], map[x-1][y], map[x][y-1], map[x][y+1] 이 모두 1이 되는 지점에서 break를 걸어주면 된다고 생각했다. 하지만 생각해보니 1,1 , 3,1 처럼 방향 변화가 전혀 없을 수 있는 map 이 존재했기 때문에 그런걸.. 더보기 6378번 6378번 - 디지털 루트 정답률에 비해서 생각보다 쉬운 문제였다. 문제의 핵심은 1000자리의 숫자는 정수형 변수로 표현할 수 없기 때문에 문자열로 표현한다는 점인 것 같다. 따라서 string 객체로 해당하는 문자를 받아들이고, 그 문자를 한 문자씩 읽어들이면서 값을 계산하는 과정을 반복하면 된다. getNum 함수에서 for문을 돌면서 각 자리의 수를 더해서 ret 라는 정수 배열에 넣어준다. 그리고 ret 라는 값이 10 이상이면 다시 ret 값을 string 으로 바꾸고 재귀함수를 구현한다. 만약 ret 값이 원하는 한자리 수 값이 되면 리턴하면서 출력한다. ###to_string : 헤더 파일에 있는 int 형 변수를 string으로 변환시켜주는 함수 12345678910111213141516.. 더보기 이전 1 2 3 4 5 6 7 8 ··· 46 다음