티스토리

나는 오늘,
검색하기

블로그 홈

나는 오늘,

jayrightthere.tistory.com/m

#알고리즘 #개발 #프로그래밍#IT개발자#JAVA#C++

구독자
3
방명록 방문하기
공지 코드 관련 참고 사항 모두보기

주요 글 목록

  • [Ubuntu] 윈도우<-> 리눅스 공유 폴더 사용하기 Ubuntu 18.04 LTS 에서 공유폴더를 사용하여 윈도우와 쉽게 폴더를 주고받을 수 있다. 먼저, 윈도우에서 공유폴더로 사용할 폴더를 하나 생성한다. 경로 : C:\Users\owner\shared 그리고 설치한 우분투 가상머신의 설정에서 공유폴더를 선택한다. 머신 폴더를 선택한 후 사이드에 있는 + 버튼을 클릭하여 경로를 설정한다. 확인을 눌러 공유 폴더를 추가해준다. 이제 가상머신에서 마운트를 진행해준다. 장치 - 게스트 확장 CD 이미지 삽입을 누르면 virtualbox 상에서 마운트를 진행한다. 보통 공유 폴더는 /media/sf~ 의 경로와 이름으로 생성이 되는데 root 권한으로도 접근이 불가한 경우가 있다. 권한을 확인해보면 root에게 권한이 부여된 것이 아니라 vboxsf에 권한이 .. 공감수 0 댓글수 0 2020. 7. 8.
  • [Network] UDP UDP(User Datagram Protocol) 트랜스포트 계층의 통신 프로토콜 TCP UDP 신뢰성이 낮은 프로토콜로서, 완전성을 보장하지 않는다. 가상회선을 확립할 필요가 없고, 유연하며 효율적인 데이터 전송에 적용된다. UDP 주요 기능과 특징 비연결성 / 비신뢰성 순서화되지 않는 Datagram 제공 ACK 없음 > 메시지가 올바르게 도착했는지 알 수 없다. 순서제어 없음 > 수신된 메시지의 순서를 보장하지 않는다. 흐름제어 없음 > check sum을 제외한 오류 검출 및 제어 없음 논리적인 가상회선 연결이 필요없음 > 데이터그램 지향의 전송계층용 프로토콜 실시간 응용 및 멀티캐스팅 가능 빠른 요청과 응답으로 실시간 통신에 적합 다수의 지점에 전송 가능 헤더가 단순하다. 헤더의 고정크기는 8바.. 공감수 0 댓글수 0 2020. 6. 8.
  • [OS] IPC 프로세스 간 통신 IPC IPC IPC 설비들 IPC (Interprocess Communication) 리눅스 커널의 구조를 보면 process는 완전히 독립된 실행 객체이다. 서로 독립되어있다는 것은 다른 프로세스의 영향을 받지 않는다는 장점이 있다. 그러나 서로 간의 통신이 어렵다는 문제가 존재한다. 이를 위해서 커널 영역에서 IPC라는 내부 프로세스 간 통신을 제공하고, 프로세스는 커널이 제공하는 IPC 설비를 이용해서 프로세스 간 통신을 한다. IPC설비들 PIPE(익명 PIPE) 파이프로 두 개의 프로세스를 연결하고 하나의 프로세스는 데이터를 Write 다른 하나는 데이터를 Read만 한다. 한쪽 방향으로만 통신이 가능하기 때문에 Half-Duplex(반 이중 통신)이라고 부른다. 송/수신을 .. 공감수 0 댓글수 0 2020. 6. 8.
  • [OS] 스케줄링 종류 목차 비선점 스케줄링 FCFS SJF HRN 우선순위 선점 스케줄링 SRTF 선점 우선순위 스케줄링 라운드로빈 스케줄링 비선점스케줄링 이미 할당된 CPU를 다른 프로세스가 강제로 뺏을 수 없는 정책 프로세스가 자원 할당 받으면, 스스로 반납할 때 까지 사용을 허용한다. 특징 일괄 처리 방식의 스케줄링 응답 시간 예측이 용이 공정한 자원의 할당 단점 중요한 작업을 먼저 수행할 수 없다. FCFS (선입 선처리 스케줄링) First Come First Service 큐에 도착한 순서에 따라 CPU를 할당한다. 호위 효과(convoy effect): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것 SJF (최단 작업 우선 스케줄링) Shortest Job First 버스트 시간( .. 공감수 0 댓글수 0 2020. 5. 27.
  • [OS] 스케줄러 스케줄링 운영체제에서 프로세서(CPU)를 프로그램에게 할당하는 과정 시스템에 여러 개의 실행 가능한 프로세스들이 존재하고, OS는 이런 프로세스 중 하나를 선택해 CPU를 할당한다. 실행 준비 완료 된 프로세스들은 준비 큐에 들어가서 CPU를 할당 받을 때까지 대기한다. 실행 중인 프로세스가 인터럽트를 받았을 경우? 다시 준비 큐에 들어가게 되고, 이후에 다시 실행된다. 이 과정에서 프로세스들은 상태를 변화시키면서 큐 사이를 왔다갔다하는데, OS는 적절한 스케줄링을 통해 큐에서 작업들을 관리해야 한다. 이 작업을 하는 것이 스케줄러 장기 스케줄러 / 단기 스케줄러 - 일괄 처리 시스템 장기 스케줄러 디스크 내의 작업들을 어떤 순서로 메모리에 적재할지 결정한다. 디스크와 같은 저장장치에 작업들을 저장해 놓.. 공감수 0 댓글수 0 2020. 5. 27.
  • [OS] 멀티 스레드 멀티 스레드 하나의 프로세스 내에서 여러 개의 스레드를 이용하여 동시에 처리한다. (병렬 처리) 다수의 스레드는 하나의 데이터 자원을 공유하기 때문에 메모리 효율성이 높다. Q. 멀티 프로세스 대신에 멀티 스레드를 사용하는 이유? 자원의 효율성 증대 프로세스 간의 문맥 교환은 CPU 레지스터 교체, RAM과 CPU 사이의 캐시 메모리 초기화까지 진행된다. 따라서 자원을 공유하는 멀티 스레드는 처리 비용의 감소와 응답 시간이 단축된다. 프로세스를 생성하여 자원을 할당하는 시스템 콜이 줄어든다. (오버헤드 감소) 단점 프로세스 외부에서 스레드 제어가 어렵다. 동기화 문제 하나의 스레드에서 문제가 발생하면 프로세스 전체에 영향을 준다. 스레드 풀 (Thread Pool) 프로세스를 시작할 때 일정한 수의 스레.. 공감수 0 댓글수 0 2020. 5. 26.
  • [OS] 프로세스와 스레드 쓰레드란? 프로세스 실행 단위 하나의 프로세스는 여러 개의 쓰레드로 구성 되어있다. 하나의 프로세스를 구성하는 쓰레드들은 프로세스에 할당된 메모리, 자원 등을 공유한다. 프로세스와 같이 실행, 준비, 대기 등의 실행 상태를 가지며, 실행 상태가 변할 때마다 쓰레드 문맥 교환(context switching)을 수행한다. 각 쓰레드는 자신만의 스택과 레지스터를 가진다. 한 순간에는 하나의 스레드만 실행이 가능하다. (독립적인 수행 단위) 쓰레드의 장점 쓰레드는 프로세스보다 생성 및 종료 시간, 문맥교환 시간이 짧다. 쓰레드는 프로세스의 메모리, 자원 등을 공유하므로, 커널의 도움 없이 상호간의 통신이 가능하다. 쓰레드 동기화 방법의 종류 Mutex Semaphore Monitor 뮤텍스 (Mutex) 쓰레.. 공감수 0 댓글수 0 2020. 5. 26.
  • [SWEA] 1249. 보급로 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 * 다익스트라 알고리즘으로 최단 경로를 구한다. * 이 문제의 경우 "최단 경로"가 답이 되는 TC도 있지만, 조금 돌아가더라도 "복구 시간"이 가장 짧은 것을 정답으로 한다. * 그렇기 때문에 방문 표시를 단순히 좌표로 하면 안된다. (조금 돌아갔을 때 복구 시간이 더 짧을 수도 있는데, 이미 방문 표시가 되어있어서 못 가는 경우가 있다) * 방문을 표시하는 visited 는 3차원으로 설정.. 공감수 0 댓글수 0 2020. 5. 18.
  • [Spring] 스프링 프레임워크로 만드는 게시판2 계층별 - 비즈니스 계층 Service 객체를 만든다. 1. 요구사항을 메소드로 정리해서 Service 인터페이스를 정의하고 2. ServiceImpl.java 에서 구현 객체를 만들어준다. 비즈니스 계층의 역할 컨트롤러와 DAO 사이의 접착제 역할을 한다. 1. 각 회사마다 다른 로직이나 규칙을 데이터베이스에 무관하게 처리할 수 있는 완충 영역 2. 컨트롤러와 같은 외부 호출이 영속 계층에 종속적인 상황을 막아준다. 3. 컨트롤러로 로직이 집중되는 것을 막는다. (트랜잭션 처리, 예외처리 등) 비즈니스 계층은 로직에 필요한 데이터베이스 관련 객체들을 모아서 자신이 원하는 일을 처리하는 용도이다. root-context.xml 수정 service package를 Spring container가 인식할 수.. 공감수 0 댓글수 0 2020. 5. 13.
  • [Spring] 스프링 프레임워크로 만드는 게시판1 게시판은 CRUD를 연습하기에 좋은 구성을 가지고 있다. 게시물의 등록, 수정, 삭제,조회 페이징 처리 검색 처리 등록(create) 구현 목록 1. 등록을 할 수 있는 화면을 구성 (form) 2. 데이터베이스 연결 3. 등록된 결과를 확인. 목록페이지로 이동하므로, 전체 목록 기능 구현 4. 상세페이지 보기 5. 수정 작업 페이지 이동 6. 페이지 삭제 org.coc.controller -> 스프링 MVC의 컨트롤러 패키지 org.coc.dao -> MyBatis의 DAO 패키지 org.coc.domain -> VO가 사용하는 패키지 org.coc.service -> 서비스 인터페이스와 구현 클래스 패키지 resource.mapper -> MyBatis Mapper xml 위치 테이블 생성 creat.. 공감수 1 댓글수 0 2020. 5. 13.
  • [SWEA] 4613. 러시아 국기 같은 깃발 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWQl9TIK8qoDFAXj&categoryId=AWQl9TIK8qoDFAXj&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 * 조합을 사용해서 백트래킹을 하며 모든 경우를 다 해본다. * 첫 행과 마지막 행은 흰색 / 빨간색으로 고정된다. 2행부터 n-1 행까지의 조합을 구한다. * 조합을 구할 때 파란색이 반드시 포함되어야 한다. * W = 1 B = 2 R = 3 으로 치환을 했다. 색을 칠 할 때 이전의 행에 칠해진 색과 .. 공감수 0 댓글수 0 2020. 5. 4.
  • [SWEA] 1824. 혁진이의 프로그램 검증 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx&categoryId=AV4yLUiKDUoDFAUx&categoryType=CODE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 * dfs를 이용해서 탐색을 진행한다. * @를 만나면 flag 를 True로 만들고 탐색을 종료한다. * 갔던 곳을 또 가지 않도록 방문 표시를 한다. 하지만, 프로그램 상 메모리에 있는 값에 따라 다른 처리를 하는 연산이 있기 때문에 visited 배열에 방문했던 당시의 메모리값(buf)을 저장하고, ?.. 공감수 0 댓글수 0 2020. 5. 4.
  • [모의 SW 역량테스트] 차량 정비소 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV6c6bgaIuoDFAXy SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 * 시간 0부터 들어온 고객을 접수 창구에 배정한다. 이 때, 접수 창구가 꽉 차서 배정되지 못한 고객은 대기 배열에 넣는다. (waitA) * USER 완료하면 정비 창구 대기열에 넣는다. 3) inputWaitingB() : 정비 창구 대기열에 잇는 사람들을 정비 창구에 넣는다. *** 정비 창구가 꽉 차서 들어가지 못한 사람들은 wait를 1씩 증가시켜준다. (wait가 클 수록 더.. 공감수 0 댓글수 0 2020. 5. 3.
  • [BOJ] 14226. 이모티콘 * BFS로 완전 탐색한다. * 큐에 모든 연산을 한 결과(now) 와 clipboard에 저장된 값(buffer), 연산 횟수(cnt)를 저장해나가면서 now == s가 되면 그 때의 cnt가 최소값이 된다. * now의 값이 변화되는 연산을 실행할 때 (이모티콘 삭제, 버퍼에 있는 값 붙여넣기) 범위를 제한해야 한다. (제한하지 않으면 오버플로우 발생 가능) * bfs의 기본인 방문 체크를 하면서 탐색한다. #include #include #include #define INF 987654321 using namespace std; //boj 이모티콘 https://www.acmicpc.net/problem/14226 typedef pair pp; typedef pair ipp; bool dp[1001.. 공감수 0 댓글수 0 2020. 5. 3.
  • [BOJ] 1976. 여행 가자 * 서로소 집합(union find)를 이용한다. * 연결되어 있는 도시들은 양방향으로 연결되고, 여행 경로는 중복이 가능하기 때문에(=최단경로가 아님) m개의 도시들이 같은 집합에 속해있는지만 확인하면 된다. #include #include #include #include #define MAXX 3001 using namespace std; // BOJ 여행가자 https://www.acmicpc.net/problem/1976 int n, m; int parent[MAXX]; int find(int a) { if (parent[a] == -1) return a; return find(parent[a]); } void unionFind(int a, int b) { int pa = find(a); int .. 공감수 0 댓글수 0 2020. 4. 30.
  • 이메일 만들기 import collections company = input() input = list(map(str,input().split(', '))); res=[] nameDic={} for value in input: name = list(map(str, value.split())); last = name[len(name)-1].replace('-','') lastfirst = last.lower() + name[0][0].lower() cnt = int(nameDic.get(lastfirst,'0')) finalName=lastfirst if cnt > 0 : finalName = finalName + str(cnt+1) nameDic[lastfirst] = cnt+1 tmp=[] tmp.append(fin.. 공감수 0 댓글수 0 2020. 4. 28.
  • [모의 SW 역량테스트] 수영장 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PpFQaAQMDFAUq SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 * 완탐으로 해결 가능 => 월을 기준으로 모든 조합을 다 구한다. * 먼저 1년은 모든 월을 커버할 수 있기 때문에 최소값으로 1년 요금으로 정한다. * 1일과 1달은 '한' 달을 기준으로 보기 때문에 idx+1 로 월을 하나만 늘려주고, 3달은 idx+3으로 3달 후를 보도록 한다. 1일은 그 달에 수영장을 이용한 횟수만큼 요금을 더해주며 최소값을 구한다. #include #inclu.. 공감수 0 댓글수 0 2020. 4. 28.
  • [모의 SW 역량테스트] 벌꿀채취 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu 불러오는 중입니다... 풀이 * 완전 탐색 * 각 row에서 m만큼 벌통들을 보면서 최대 C이하가 되는 최적의 조합을 구해야 한다. * cost[][] 에는 현재 위치에서 m만큼 봤을 때 채취할 수 있는 벌꿀의 최대 수익을 저장한다. * 전체 맵을 순회하면서 서로 겹치지 않는 두 지점의 최대 수익의 합을 구한다. #include #include #include using namespace std; int n, m, c; int map[11][11]; int cost[11][11]; bool chk[6]; int value = 0; t.. 공감수 0 댓글수 0 2020. 4. 28.
  • [BOJ] 16957. 체스판 위의 공 * 체스칸 위의 적힌 값은 변동이 없기 때문에 공의 위치에 따라 이동할 방향이 정해져있다. * 이 특징을 이용해서, 좌표마다 움직이는 방향을 저장하고 (dir[][]) 해당 위치에 오면 저장된 방향으로 이동하도록 한다. * 공을 이동시킬 때는 해당 좌표에 있는 공을 모두 가지고 이동한다. #include #include #include #define INF 300001 using namespace std; //BOJ https://www.acmicpc.net/problem/16957 int r, c; int map[501][501]; int ball[501][501]; int dir[501][501]; bool visited[501][501]; int dx[9] = {-1, -1, -1, 0, 0, 0,.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 17298. 오큰수 * 스택을 사용한다. * 나중에 들어오는 수가 오큰수가 정해지기 때문에 스택을 이용해서 가장 최근 넣은 값과 (top) 현재 값을 비교한다. 이전 값보다 더 큰 수가 들어오면 => 이전 값 수의 오큰수는 현재 값이다. * 더 큰 수가 없으면 -1이다. #include #include #include #define MAXX 1000001 using namespace std; typedef pair pp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res[MAXX]; int num[MAXX]; stack st; for (int i = 0; i < n; i++) res[i] = -1; for (int i = 0; i .. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 4378. 트ㅏㅊ; * 주어진 문자열을 키보드 상에서 한 칸 씩 왼쪽으로 간 결과로 치환해야 하기 때문에 키보드를 그대로 배열에 저장한다. * 문자열을 탐색하면서 문자가 탐색되면 그 인덱스 -1의 결과를 출력한다. * 인풋은 여러 줄을 나눠서 들어오고, 중간에 공백이 있을 수 있으므로 getline()으로 입력받는다. #include #include using namespace std; //boj https://www.acmicpc.net/problem/4378 int main() { ios_base::sync_with_stdio(0); cin.tie(0); string keyBoard[4] = {"`1234567890-=", "QWERTYUIOP[]\\", "ASDFGHJKL;\'", "ZXCVBNM,./"}; strin.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 9019. DSLR * 경로를 남기고, 역추적한다. * visited[i] = j 는 i가 되기 전의 숫자가 j임을 표시한다. op[i] = i가 되기 위한 연산을 저장한다. * a = 시작점 일 때, visited[a] = -2로 저장한다. (이 표식을 발견하면 역추적을 중지한다.) * a가 b가 되었을 때, 역추적을 하면서 벡터에 사용한 연산들을 저장한다. * a가 b가 아니라면, D ,S, L, R 연산을 진행하면서 만들어진 숫자들을 모두 큐에 넣는다. 중복 탐색을 방지하기 위해 이미 한 번 생성된 숫자는 더 이상 탐색하지 안흔ㄴ다. * 이 문제는 L, R 연산을 효율적으로 작성하는 게 중요하다. deque, string 등은 시간이 초과된다. L : d2 d3 d4 d1 이므로 가장 마지막 숫자를 추출한다. (n =.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 17085. 십자가 2개 놓기 * 십자가를 놓을 수 있는 최대 길이를 chk[][] 에 미리 저장을 해 놓는다. * 십자가는 한 좌표를 중심으로 상 하 좌 우 인접한 칸으로 퍼져나간다. * 이 특성을 이용해서 chk에는 몇 번이나 뻗어나갔는지를 저장한다. * dfs(int cnt, ll res) 에는 2개의 십자가를 놓았으면 최대값을 비교하여 갱신한다. (종료조건) *(0,0) ~ (n,m)까지 검사하면서 chk[][]가 1이상일 때 (== map[][] 가 # 일때) 주변을 검사하면서 십자가가 겹쳐서 생성되지 않는지 검사한다. *무조건 한 십자가가 크다고 정답이 되는 것은 아니기 때문에 십자가의 크기가 chk[][] 의 값보다 작더라도 dfs()를 호출해서 다른 십자가도 놓을 수 있도록 한다. (line 81) * visited는 .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 16939. 2X2X2 큐브 https://www.acmicpc.net/problem/16939 * 큐브를 회전할 때 같이 바뀌는 인덱스들을 rotateIdx[][] 에 저장해둔다. * 한 번만 회전하는 경우 나올 수 있는 경우의 수가 6개 이고 한 번 회전할 때 바뀌는 인덱스는 8개 이므로 6*8 로 생성했다. *큐브의 현재 상태를 저장하는 것이 중요하다. * rotate()에는 큐브를 회전하고 check()를 통해 회전한 결과가 옳은지 확인한다. * deque를 사용해서 정방향으로 돌릴 때는 뒤에 값을 넣어주고, 역방향으로 돌릴 때는 앞에 값을 넣어준다. deque의 결과는 다시 큐에 넣고, check()에서 결과를 확인한다. #include #include #include #include using namespace std; .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 16932. 모양 만들기 * dfs를 이용하여 1로 이루어진 그룹을 라벨링한다. (그룹에 몇 개의 1이 있는지 labelCnt[]에 저장한다) * 현재 좌표의 값이 1이고, 상 하 좌 우 인접한 값이 0인 좌표를 중심으로 탐색을 한다. 인접한 좌표에 0이 있다면 이 값을 1로 바꾸고 다른 그룹들과 합쳐질 수 있다. -> 이를 가능하게 하려면, 0인 좌표의 인접한 칸에 다른 그룹이 있어야 한다. * 만약, 0인 좌표가 다른 그룹과 인접해 있다면 (연합 그룹을 형성하는 1의 개수와 현재 그룹의 개수 +1 )의 최대값이 정답이 된다. * 주의해야 할 점은, 0이 같은 그룹으로 이루어진 1들로 둘러싸여져있을 수 있기 때문에 중복으로 더해주는 것을 방지해야 한다. (set에 그룹의 라벨을 넣어주어서 중복으로 세지 않도록 하였다. ) 1 .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 17822. 원판 돌리기 * rotate에서는 x의 배수인 원판들을 시계/반시계 방향으로 k번 회전한다. * deque를 사용해서 시계방향은 한 원판에서 가장 뒤에 있는 요소를 가장 앞에 삽입한다. (pop_back -> push_front) 반시계방향은 가장 앞에 있는 요소를 가장 뒤에 삽입한다. (pop_front->push_back) * deque에 저장된 값들을 다시 map에 넣는다. * removeNums()에서는 인접한 숫자들을 지운다. 만약, 전체 원판을 통틀어 지울 수가 없다면 평균값에 따라 원판의 값을 조절한다. * 각 좌표에서 상 하 좌 우를 살펴봤을 때 같은 수가 있으면 큐에 넣어준다. 만약, 전체 원판을 봤을 때 큐에 아무런 값도 없다면 지울 값이 없다는 것이다. * *평균값을 double로 구해줘야 한다... 공감수 0 댓글수 0 2020. 4. 19.
  • [BOJ] 16918. 봄버맨 * bombTime[] 폭탄이 설치되는 시간을 저장한다. * 처음 1초 동안 봄버맨은 아무것도 하지 않는다. -> n == 1일 때 입력받은 폭탄을 그대로 출력해야 한다. * 1초 동안 폭탄이 없는 곳에 폭탄을 설치한다. (이때 설치하는 폭탄은 first (처음 폭탄이 터지는 시간) + 2 시간에 터진다. ) * 1초 프로세스 도중에 sec == n이 되면 실행을 멈춘다. * 폭탄을 터트린다. (bomb(터질 폭탄 -> 이 시간에 터질 폭탄만 터트린다)) -> 1초 소요 * 폭탄은 터질 때 주변의 폭탄들을 같이 터트리기 때문에 자신과 같은 숫자를 가진 폭탄은 터트리지 않는다. * 주변의 폭탄을 터트린 후에 현재 터져야 할 폭탄들을 터트려준다. (62 ~ 72 line) #include #include u.. 공감수 0 댓글수 0 2020. 4. 17.
  • [BOJ] 9328. 열쇠 * BFS로 완전 탐색을 한다. * 열쇠 상태를 계속 저장한다. (keystate) * 상근이는 빌딩 밖을 자유럽게 돌아다닐 수 있기 때문에 맵의 바깥쪽은 전부 '.'으로 만들어준다. *(0,0)부터 탐색을 시작한다. - 문을 만나면 지금 가지고 있는 키로 열 수 있는지 확인한다. 열 수 있다면 빈공간('.')으로 만들어준다. - 문서를 만나면 훔칠 수 있는 문서의 개수인 (res)를 1만큼 증가시키고 빈공간('.')으로 만들어준다. - 열쇠를 만나면 keystate를 비트마스킹을 이용하여 값을 변경해주고 빈 공간으로 만들어준다. - 여기서 중요한 것은 열쇠를 만났을 때 지금 까지 방문했던 좌표 중에 이제는 열 수 있는 문이 있을 수도 있기 때문에 visited 배열을 초기화한다. (초기화하는 방법 말고.. 공감수 0 댓글수 0 2020. 4. 16.
  • [BOJ] 14391. 종이조각 * (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. * 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. T T T T 이렇게 방문표시가 되어있다면 이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고. 아닌 부분들은 세로로 직사각형을 만든다. * 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. #include #include #include using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int .. 공감수 0 댓글수 0 2020. 4. 16.
  • [SW Test 샘플문제] 프로세서 연결하기 * dfs 조합을 이용해서 최대한 많은 core들을 연결했을 때 최소 전선의 길이를 구한다. * 맵의 사이드에 있는 코어들은 이미 연결되어있기 때문에 cores에는 그 외의 코어들을 넣는다. * dfs(idx, cnt)에서는 코어들을 조합을 확인하면서 백트래킹한다. * check(x, y, d) : x, y 좌표에 있는 코어가 d방향으로 연결될 수 있으면 T, 아니면 F doConnect(x, y, d) : check() 가 T라면 연결한다. (chk 배열에 방문표시) doDisConnect(x, y, d) : 원상 복귀 (백트래킹) #include #include #include #define INF 987654321 using namespace std; int n; int map[13][13]; bo.. 공감수 0 댓글수 0 2020. 4. 15.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.