티스토리

알고리즘 부수기

검색하기

블로그 홈

알고리즘 부수기

algwang.tistory.com/m

알광(Algwang) 님의 블로그입니다.

구독자: 3

방명록 방문하기

주요 글 목록

1264. 이미지 유사도 검사(D6) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18Q_MqIvUCFAZN D6이라 겁먹을 수 있지만 간단한 LCS 문제이다. 123456789101112131415161718192021222324252627282930#include#include#include using namespace std; int main(void) { int T; cin >> T; for (int test_case = 1; test_case > len; string X; string Y; cin >> X >> Y; for (int i = 1; i 공감수 0 댓글수 1 2019. 5. 3.
17136. 색종이 붙이기 문제링크 : https://www.acmicpc.net/problem/17136 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394#include using namespace std; int arr[10][10];bool visited[10][10];int result = 25;bool finishFlag = false;int min(int a, int b) { if (a > b) return b; else return a;}int che.. 공감수 0 댓글수 0 2019. 4. 12.
ps하다가 런타임에러가 나는 경우 ! (계속 업데이트) 1.배열에 할당된 크기를 넘어서 접근했을 때 2.전역 배열의 크기가 메모리 제한을 초과할 때 3.지역 배열의 크기가 스택 크기 제한을 넘어갈 때 4.0으로 나눌 때 5.라이브러리에서 예외를 발생시켰을 때 6.재귀 호출이 너무 깊어질 때 7.이미 해제된 메모리를 또 참조할 때 8.사이즈가 0인 벡터를 참조할 때 9.빈 문자열을 stoi 할 때 공감수 0 댓글수 0 2019. 4. 2.
stl vector / list / queue 속도 비교 링크 : https://blog.naver.com/omg92/60148996317 stl vector, list, queue 속도 비교 #include #include #include #include using ... blog.naver.com 문득 vector와 queue의 속도 차이가 궁금해져서 관련 자료를 찾아봤다. 벡터는 런타임에 크기가 변경될 수 있는 배열과 같은 자료구조이다. 따라서 배열과 유사하게 사용할 수 있다. 인덱스 구조를 사용하기 때문에 임의 접근이 가능하고 탐색이 빠르다는 장점이 있다. 하지만 인덱스 구조를 유지하기 위해서 임의의 위치에 있는 원소의 삽입 및 삭제가 어렵다는 단점이 있다 ! 100,000칸 짜리 배열에서 맨 앞 칸을 빼고 나머지 99,999칸을 앞으로 당기는 것과 비.. 공감수 1 댓글수 0 2019. 4. 1.
17071. 숨바꼭질 5 문제링크 : https://www.acmicpc.net/problem/17071 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include #include using namespace std;bool visited[2][500001] = { false }; // 홀수번째 짝수번째 따로(진동 가능)int main(void) { int startC; int startB; cin >> startB >> startC; queue myQ; myQ.push(startB); visited[0][startB] = true; int turn = 1; if (startC == startB).. 공감수 0 댓글수 4 2019. 3. 26.
7193. 승현이의 수학공부(D3) 문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWksRkI6AR0DFAVE - 소스 코드 - 123456789101112131415161718192021222324import java.util.Scanner; // 0보다 크거나 같은 모든 k에 대해// n^(k) % (n-1) ≡ 1을 만족한다.// 이것만 알면 쉽게 풀 수 있는 문제 !! public class Solution7193 { public static void main(String[] args) { Scanner scan=new Scanner(System.in); int T=scan.nextInt(); for(int test_case=1.. 공감수 0 댓글수 0 2019. 3. 6.
7569. 토마토 문제링크 : https://www.acmicpc.net/problem/7569 - 소스 코드 - 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class Main { static int map[][][]; static Queue myQ; static int dx[] = { 0, 0, .. 공감수 0 댓글수 0 2019. 3. 6.
1868. 파핑파핑 지뢰찾기(D4) 문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE - 소스 코드 - 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384import java.util.Scanner; public class Solution1868 { static int num; static int d.. 공감수 0 댓글수 0 2019. 3. 6.
1861. 정사각형 방(D4) 문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc&categoryId=AV5LtJYKDzsDFAXc&categoryType=CODE 사실 이 문제는 Testcase가 약해서 사용한 방법대로 시작점을 정하지 않고 맵의 모든 점을 시작점으로 해도 시간 내에 정상적으로 동작하지만 1 2 3 4 5 6 12 11 10 9 8 7 13 14 15 16 17 18 24 23 22 21 20 19 25 26 27 28 29 30 36 35 34 33 32 31 만약 맵이 위와 같은 모양이라면 최대 200 * 200 사이즈에서 시간초과가 나게 된다. 1에서 dfs를 통해 36까지 확인하게 .. 공감수 0 댓글수 0 2019. 3. 6.
16987. 계란으로 계란치기 문제링크 : https://www.acmicpc.net/problem/16987 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475import java.util.Scanner; // 16986 인싸들의 가위바위보 문제와 마찬가지로 dfs를 통한 완전탐색으로 해결했다.// 처음 문제를 접했을 때 이걸 어떻게 해결하지 했다가 N이 최대 8이라는 것을 보고 바로 접근! public class Main { static int N; static int eggCount=0; static class Egg{ int w.. 공감수 0 댓글수 2 2019. 3. 2.
16986. 인싸들의 가위바위보 문제링크 : https://www.acmicpc.net/problem/16986 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123import java.util.Scanner; // 손가락 가지수가 최대 9개입니다.// 즉, 지우가 낼 수 있는 가지수가 9개 뿐이므로 아무리 많아도 9!개의 가지.. 공감수 0 댓글수 0 2019. 3. 2.
6960. 자영이의 퍼스트 솔브(D6) 문제링크 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWjlJGwK3lMDFAVT 잘 모르는 개념의 문제를 푸는 중이라 풀이를 올릴만한 문제를 못찾아서 오랜만에 올리는 글 ! - 소스 코드 -12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include#include#include #define pii pair using namespace std;//comparator 함수 정의 bool comp(pii a,pi.. 공감수 0 댓글수 0 2019. 2. 26.
구글 크롬(Chrome) 단축키 정리 Ctrl + W : 탭 닫기+ E : 주소창으로 구글 검색+ R : 새로고침+ T : 새 탭+ U : 페이지 소스 보기+ O : 열기+ P : 인쇄 + A : 전체 선택+ S : 저장+ D : 북마크+ F : 검색 (방문 기록 같은 특정 페이지에서는 G와 다른 기능)+ G : 페이지 내에서 검색+ H : 방문 기록+ J : 다운로드 목록+ K : 주소창으로 구글 검색+ L : 주소창 선택 + N : 새 창에서 새 탭 + Tab : 다음 탭으로 이동+ Pgdn : 다음 탭으로 이동+ Pgup : 이전 탭으로 이동+ Home : 페이지 맨 위로 이동+ End : 페이지 맨 아래로 이동+ + : 확대+ - : 축소 공감수 0 댓글수 0 2019. 2. 8.
삼성전자 SW 역량테스트 B형(Professional) 합격 및 후기 사실 1월 말에 합격 통보를 받았지만 연휴, 귀차니즘 등등으로 이제 글을 쓰.. 드디어 3번만에 B형 합격 !! 지난(2018년) 7~8월부터 최대한 stl을 안쓰고 문제를 해결하는 연습을 나름 했지만 2번의 도전 모두 결과는 좋지 않았다. 그래서 다시 처음부터 여러 자료를 찾아보다가 박트리님의 블로그에 올라온 글(https://baactree.tistory.com/53)을 보면서 최적화를 위해 필수 배경지식과 기법들이 있다는 것을 알게 되고 공부하며 사용해보고 알고리즘 스터디(스터디는 https://open.kakao.com/o/g0fl7MN에서 갓분들과 만들어서 진행)를 하면서 같은 문제라도 여러 사람의 풀이를 보고 시간복잡도를 계속 따지며 줄이는 시도를 했던 것이 가장 큰 도움이 되었다. 다시 박트.. 공감수 13 댓글수 33 2019. 2. 7.
1322. X와 K 문제링크 : https://www.acmicpc.net/problem/1322 - 소스 코드 - 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849/* * 시간복잡도 : O(logN) [ N은 K입니다. ] * 공간복잡도 : O(logN) [arrayList] * * x+?가 x|?이기 위해서는 x의 비트가 0인 부분들로 구성되어야 합니다. * ex) x=101(2) ?=10(2) * 그래서 1부터 2씩 곱하면서 x의 해당 비트가 0일 경우 * ArrayList에 그 비트가 나타내는 수치를 저장했습니다. * 2^(arr.size)를 해준 이유는 이진수에서는 해당 자리가 0,1인 경우의 수 2가지가.. 공감수 1 댓글수 0 2019. 1. 31.
15711. 환상의 짝꿍 문제링크 : https://www.acmicpc.net/problem/15711 테스트케이스 수(1 공감수 0 댓글수 2 2019. 1. 30.
1124. 언더프라임 문제링크 : https://www.acmicpc.net/problem/1124 두 자연수 A,B (2>A>>B; bool check[100002]; fill_n(check,100002,true); check[1]=false; // 1과 0은 소수가 아님 ! check[0]=false; int arr[100002]={0}; int result=0; for(int i=2;i 공감수 0 댓글수 0 2019. 1. 29.
2018. 수들의 합 5 문제링크 : https://www.acmicpc.net/problem/2018 정수 N(1 연속된 수의 합이라는 점에서 등차수열을 이용했다. 5+6+7+8은 1+2+3+4+5+6+7+8에서 1+2+3+4를 뺀 값이라는 점이다. 즉, 1~8까지의 등차수열에서 1~4까지의 등차수열을 뺀 값이다. 그래서 n이라는 수를 받아서 n/2 +1까지를 탐색하며 해당 수(i)까지의 등차수열의 합이 원래의 수(N)보다 크거나 같은지를 확인한다. 그리고 크거나 같을 경우 N과의 차이를 구한다. 이렇게 구해진 N이 1~A(자연수) 까지의 등차수열의 합으로 만들 수 있는 숫자라면 i까지의 등차수열에서 A까지의 등차수열을 뺀 값이 N이라는 것을 알 수 있다. N의 최대값이 10^7이므로 더했을 때 int의 범위를 넘.. 공감수 0 댓글수 0 2019. 1. 28.
2004. 조합 0의 개수 문제링크 : https://www.acmicpc.net/problem/2004 정수 n,m (0>a>>b; int c=a-b; int tempA,tempB,tempC; tempA=a; tempB=b; tempC=c; ll aCount1=0; ll bCount1=0; ll cCount1=0; // 2의 배수 ll aCount2=0; ll bCount2=0; ll cCount2=0; // 5의 배수 while(tempA>=2){ tempA/=2; aCount1+=tempA; } while(tempB>=2){ tempB/=2; bCount1+=tempB; } while(tempC>=2){ tempC/=2; cCount1+=tempC; } while(a>=5){ a/=5; aCount2+=a; } .. 공감수 0 댓글수 0 2019. 1. 28.
2870. 수학숙제 문제링크 : https://www.acmicpc.net/problem/2870 줄의 개수 (1 파싱 연습을 위한 간단한 문제이다. 여기서 중요한 것은 어떻게 숫자를 뽑아낼 것인가 / 뽑아낸 숫자를 어떻게 정렬할 것인가이다. 먼저 숫자를 뽑아내는 것은 라인별로 입력을 받아서 숫자를 쌓고 있음을 의미하는 bool 변수 flag를 만든다. 숫자를 만날 경우 flag를 true로 하고 temp(string)에 숫자를 쌓는다. 그리고 문자를 만날 경우 flag를 false로 바꿔주며 숫자가 끝났음을 표시하고 만들어진 문자열(숫자)의 앞에 0을 제거해준다. (문자열의 길이를 통해 0 하나만 있을 경우 예외처리) 문자를 만나지 않았지만 라인이 끝났을 경우는 flag를 통해 확인할 수 있다. 다음으로 정렬.. 공감수 0 댓글수 0 2019. 1. 25.
C++에서 String 출력하기 1. cout 사용시 cout 공감수 0 댓글수 0 2019. 1. 25.
1907. 모래성 쌓기 (D5) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PNx_KACIDFAUq&categoryId=AV5PNx_KACIDFAUq&categoryType=CODE 맵의 세로 길이 H, 가로 길이 W (1 모 기업 테스트 기출과 비슷한 문제..읍읍 파도가 1번 칠 때마다 맵의 상태가 변한다. 전체를 탐색할 경우 1,000 * 1,000 * 파도횟수 만큼의 시간이 걸릴 수 있다. 즉, 상태 변화가 일어나지 않을 때까지 전체를 계속해서 탐색하며 변화시키면 풀 수 없다는 뜻 ! 최적화가 필요한 문제이다. 그렇다면, 맵 전체를 탐색하지 않고 상태를 변화시킬 수 있는 방법이 뭐가 있을까? 더이상 .. 공감수 0 댓글수 0 2019. 1. 25.
1431.시리얼 번호 문제링크 : https://www.acmicpc.net/problem/1431 기타의 개수 N( 시리얼 번호를 주어진 조건에 따라 정렬하여 결과를 출력 주어진 조건에 따라 정렬을 해야 하므로 가장 중요한 것은 조건이다. 위 내용이 그 조건이고 주어진 조건을 그대로 따라가면 되는 간단한 문제이다. 비교의 우선순위가 1 > 2 > 3이기 때문에 따라서 먼저 1번 조건을 확인한다. A와 B의 길이가 다를 때, 짧은 것이 먼저 온다. 즉, strlen을 사용해서 비교를 하라는 조건이다. 다음으로 길이가 같을 때 자리수의 합(숫자인 것만)을 비교한다. 이 과정은 매번 비교할 때마다 자리수의 합을 구하면 상당히 긴 시간이 걸릴 수 있는 과정이다. 그래서 문자열을 입력받으면서 입력받은 문자열.. 공감수 0 댓글수 0 2019. 1. 24.
1309.동물원 문제링크 : https://www.acmicpc.net/problem/1309 우리의 크기 N(1N; for(int i=2;i 공감수 0 댓글수 0 2019. 1. 22.
11060. 점프 점프 문제링크 : https://www.acmicpc.net/problem/11060 칸 수(1>n; for(int i=0;i 공감수 0 댓글수 0 2019. 1. 18.
5521. 상원이의 생일파티 (D5) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE 상원이의 같은 반 친구 수 (2T; for(int test_case=1;test_case>N>>M; for(int i=0;i 공감수 0 댓글수 0 2019. 1. 17.
10164. 격자상의 경로 문제링크 : https://www.acmicpc.net/problem/10164 N(세로 사이즈, 우선 경로의 수는 int 범위 안에서 수행 가능하지만 "15 * 15밖에 안되네 그냥 int로 하자"라고 생각하면 안된다. 나중에 해보면 알겠지만 입력으로 "15 15 0"이 들어올 경우가 최다 경로인데 40,116,600개가 나온다. 18 * 18이상은 int 범위가 넘어가게 된다. [ 사이즈만 보고 방심하면 히든 케이스에서 터져버린다. 다른 문제 풀 때도 주의해야할 점 ] 이제 풀이로 들어가보면 아이디어 자체는 간단하다. 중학교 때 수학에서 배운 방법을 사용하는 것이다. 이 맵에서 1번부터 8번을 거쳐 15번까지 가는 최단경로의 수는 (1번부터 8번까지 가는 최단경로의 수) * (8번부터 1.. 공감수 0 댓글수 0 2019. 1. 17.
6697. 이현이의 괄호 문자열 (D5) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWdXrXraFloDFAWn&categoryId=AWdXrXraFloDFAWn&categoryType=CODE A ( 원하는 이동 횟수 ) [ 1 문제가 이해가 안돼서 테스트케이스를 보고 분석을 했다. )( 는 1번만에 ()라는 올바른 문자열을 만들 수 있다. )())((는 4번만에 ()()()라는 올바른 문자열을 만들 수 있다. 문제 설명에서 문자열 T가 올바른 문자열이면 ( T ) 도 올바른 문자열이다. 라고 되어있지만 1) )))(((을 ()()()로 만드는 데는 3+2+1 = 6 번이 필요하다. 2) )))(((을 ((()))로.. 공감수 0 댓글수 0 2019. 1. 16.
6782. 현주가 좋아하는 제곱근 놀이 (D5) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemSolver.do?contestProbId=AWgqsAlKr9sDFAW0 정수 N (1 D5라서 겁먹고 시작했는데 단순한 문제였다. 문제가 어렵다기 보다는 테스트 케이스가 10,000개에 수의 범위가 10^12기 때문에 어떤 방법으로 시간을 줄여서 풀 것인지가 중요한 문제이다. 따로 줄이는 과정을 생각해보지도 않았고 while문 돌렸는데 풀려서.. 다른 사람들이 어떤 방법으로 시도를 했고 시간초과로 고민을 하는지는 잘 모르겠다. -------------------------------------------------------------------------------------.. 공감수 0 댓글수 0 2019. 1. 16.
3131. 100만 이하의 모든 소수 (D3) 문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6mRsasV8DFAWS&categoryId=AV_6mRsasV8DFAWS&categoryType=CODE 없음 100만 이하의 모든 소수 출력하기 "에라토노스의 체"라는 이론을 사용할 것이다. https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 간단하게 설명하면 우선 100만 이하의 2의 배수를 모두 지운다. 다음으로 3의 배수를 모두 지운다. 진행 중 지워.. 공감수 0 댓글수 0 2019. 1. 15.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.