문베디드 인생

1. dp를 1차원배열 1개로 풀이 4352ms queen의 위치를 저장한 배열 1개로 중복 열, 중복 대각선을 수식으로 계산하여 skip 현재까지 구한 queen 위치를 일일이 비교하므로 모든 경우의 수에서 최대 16번의 비교가 추가로 필요 https://chanhuiseok.github.io/posts/baek-1/ 2. dp를 1차월배열 3개로 풀이 1652ms 현재까지 놓인 열번호, 우상대각선, 좌상대각선 관리 배열로 관리 현재 놓으려는 열 번호를 해시값으로 하여 배열에 접근하여 중복된 값이 있는지 확인하기 때문에 1번 풀이에서 현재까지의 queen 위치를 비교하는 방식보다 메모리는 더 쓰지만 속도는 빨라짐 https://3dpit.tistory.com/2

문제: 백준 1620번 나는야 포켓몬 마스터 이다솜 C와 C++에서 제공하는 입출력 구분 C C++ 헤더 stdio.h iostream / cstdio 입력 scanf cin / scanf 출력 printf cout / printf 기본적으로 C++ 코드에서는 C에서 사용하는 함수들을 가져다 쓸 수 있다. 그래서 #include 를 사용해도 된다. 만약 C++ 표준으로 사용한다면 #include 를 사용한다. 이번에는 문자열을 입력받아 처리하는 문제이다. 문자열 처리 편리를 위해 string 클래스를 사용하여 입력받는 코드를 짰는데 string 클래스는 cin 을 사용해서 입력받아야 하기 때문에 다른 변수는 scanf로 입력받고 문자열만 cin으로 받았다. 결과는 시간초과 cin 이 문제였기 때문에 아래..

세상에는 정말 똑똑하고 훌륭한 사람이 많다. 자신들이 가진 지식을 무료로 체계적으로 이렇게 뿌려주다니..^^ 감사합니다~ https://blog.encrypted.gg/922?category=773649 [실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I 안녕하세요, 바킹독입니다. 이번 단원에서는 기초 코드 작성 요령을 익혀보려고 합니다. 목차를 보셨으면 알겠지만 기초 코드 작성 요령이 두 강으로 나눠져있는데 앞으로 코드를 잘 짜기 위해 blog.encrypted.gg https://bloodstrawberry.tistory.com/47 삼성 B형 링크 개념 설명 메모리 풀 Memory Pool 메모리 풀 vs malloc 속도 비교 링크드 리스트 Linked List 해시 테이블 Hash Tabl..

문제출처 https://bloodstrawberry.tistory.com/47 map BOJ 18139 : Rush Hour Puzzle =====Unsolved===== deque BOJ 10866 : 덱 vector BOJ 1707 : 이분 그래프 => 풀긴 풀었으나 bfs 가 아닌 dfs 풀이도 공부 필요 =====Solved 06/11/22===== BOJ 1764 : 듣보잡 (+ sort) =====Solved 06/12/22===== BOJ 7785 : 회사에 있는 사람 (+ sort, 정렬 기준 변경) BOJ 7785 : 회사에 있는 사람 (+ erase) =====Solved 06/13/22===== map BOJ 18139 : Rush Hour Puzzle BOJ 7785 : 회사에 있는..

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다. 우리는 그럴때 이렇게 말한다. 범위? 무슨 범위? 틀리기 쉬운 범위는 다음과 같다. 1) for, while 과 같은 반복문 횟수, 반복문 시작, 종료 위치 C/C++에서 사용하는 배열은 0부터 시작한다. 그런데 보통 알고리즘 문제에서 주어지는 번호가 1번부터 시작한다. 입력받을때는 배열의 1번부터 N번까지 입력을 받는데 반복문을 돌릴때 0번부터 N-1 까지 접근하는 경우가 많다. 아래 예시를 보자 1 2 for(int i = 0; i

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다. 우리는 그럴때 이렇게 말한다. 변수 범위가 뭐가 문제냐고? 알고리즘 문제 풀다보면 입력 값의 범위는 1≤N≤100 이다. 같은애들이 많다. 그러면 그 값을 입력받아서 저장할 변수의 범위는 어떻게 잡아야할까? 1 2 3 4 5 int visited[101]; node head[101]; //컴퓨터 최대 100대 node last[101]; cs 위 코드 처럼 최대가 100이라면 무조건 키워서 잡는다. 혹은 입력받을때 인덱스처리를 -1 해주면 되겠지만 본인이 알고리즘 초보라면 인덱스를 신경쓰기 보다는 저장공간만 키워주면 굉장히 깔끔해진다. 문제는 여기 해설은 여기 전체코드는 여기 참고로 내 코드와 해설 코드는 다르다.

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다. 우리는 그럴때 이렇게 말한다. 이번엔 초기화가 문제이다. 당신의 초기화 코드는 매번 실행할때마다 적절하게 초기화를 하고 있는지 확인하자 반복해서 수행되는 함수에서 처음 호출될때만 초기화가 제대로 되고 이후에는 제대로 안되고 있을 가능성이 있다! 예시 케이스만 돌리는 경우에 케이스 수가 적어 문제가 발생 안하기 때문에 놓칠수도 있다. 반복해서 처리하는 함수를 작성했을 경우에 제대로 초기화가 되었는지 확인이 필요하다. 내가 이번에 도전한 문제는 숫자야구게임 문제이다. 자세한 설명은 문제 링크에서 찾아보자. 참고한 풀이는 풀이 링크에서 찾아보자. 이번 문제를 풀면서 dfs와 메모리풀을 활용해 경우의 수를 만들어주는 부분이 있었는데 처음 테스트 케이스..

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다. 우리는 그럴때 이렇게 말한다. 우선 아래 코드를 보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int main() { /* 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1, 000), 간선의 개수 M(1 ≤ M ≤ 10, 000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. */ scanf("%d%d%d", &N, &M, &V); for (int i = 0; i

알고리즘 문제를 풀다보면 아무리 코드를 봐도 맞는데 틀린다. 우리는 그럴때 이렇게 말한다. 백준 20056번 마법사 상어와 파이어볼 문제를 풀며 틀렸던 내용입니다. 기본적인 문제에 대한 설명과 해설은 레퍼런스에서 참고합니다. 이 글을 쓴 이유는 좌표처리 하며 생긴 생각의 오류를 남기기 위해서입니다. 마법사 상어가 쏜 파이어볼은 주어진 좌표체계에서 상하좌우 사방대각선으로 0에서 8까지의 방향으로 아래의 그림과 같이 움직입니다. 행을 y축 열을 x축이라고 생각했을때 각 방향으로의 좌표 변화는 다음과 같이 표현할 수 있습니다. 1 2 dx = { 0, 1, 1, 1, 0, -1, -1, -1 }; dy = { 1, 1, 0, -1, -1, -1, 0, 1 }; cs 그런데 문제가 발생합니다. 디버깅을 해보니 ..

좌표를 입력받아 사분면 위치를 출력하는 간단한 문제 입력받은 숫자의 case를 구분하는 if문을 작성하여 풀고, 숏코딩을 보니 수식을 만들어서 쓴 사람들이 있었다. 처음 10초정도 수식으로 할수 있지 않을까 생각은 들었으나 그냥 빨리 풀고 넘어가자고 생각했는데 이걸 또 줄여서 수식으로 만들어서 시간과 코드 양을 줄이는 사람들이 있네 똑띠들...^^ 사분면 위치를 구하는 식은 다음과 같다. 좌표 (x, y) 를 입력받은 경우, 이때 x와 y는 0으로 입력되지 않는다. 1+2*(y