Algorithm/Algorithm Problem

백준 7682 틱택토(구현)

7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 이겼을때가 아니라 "최종" 상태를 판단하는 것 게임 진행하다가 나타날 수 있는 중간상태도 모두 invalid 이다 따라서 남은 point_cnt가 핵심이 되야한다 if point_cnt 없을때(모든칸이 꽉찼고 X먼저 두니까 x가 1 많아야함) if x_cnt = 5, o_cnt = 4 if X빙고 && O빙고 false else if !X빙고 && O빙고 false true else false else point_cnt 없을때(게임중간에 누군가 이겨서 멈췄다는..

백준 1094 막대기(구현, 비트마스킹)

1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 매우 간단한 문제이지만 배울점이 많았던 문제다 가지고 있는 막대를 반으로 계속 나누면서 남은 애들이랑 이어붙여서 요구하는 막대의 길이를 구하는건데 1. 문제에 나와있는대로 그대로 구현하기 1. 가지고 있는 막대를 이등분 한다 2. 이등분한 막대 중 하나를 빼고 나머지 stack에 있는 애들을 모두 더한다 3. if sum >= X : 이등분한거 버린다(아무것도 안한다) if sum < X : 버리지 않는다(다시 stack에 넣는다) package pratic..

백준 14722 우유도시(DP)

14722번: 우유 도시 영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 매우 까다로운 영학이는 자신만의 우유를 마시는 규칙이 있다. 맨 처음에는 딸기우유를 한 팩 마신다. 딸기우유를 한 팩 마신 후 www.acmicpc.net 더보기 BFS + dp table 이용(메모리초과) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Queue; import java.util.StringTokenizer; /* * 동,남쪽으로만 이동하기 때문에 전의 값을 계..

백준 2931 가스관(구현, 시뮬레이션)

2931번: 가스관 www.acmicpc.net SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com SWEA 탈주범 검거랑 비슷한 그림을 띄고 있지만 전혀 다른 문제다 출발지, 목적지를 잇는 완전한 길이 있었는데 그 중 하나를 없앴다는 것이다. 그것에 대한 정보를 구하는 문제 대체 어디를 없앴는지 과연 어떻게 알 수 있을까? 1. 출발지, 목적지에서 bfs를 출발하여 빈칸을 만날 때 이 빈칸들을 list에 저장하여 후보들을 정해놓고 2개의 list를 하나씩 비교해봤을 때 똑같은 부분이 바로 그 지점! 2. 빈칸에 대해 파이프를 바꿔야하니까 빈칸을 모두 살펴본다 빈칸에 대해 상하좌우를 돌리면서 다른 파이프가 연결되어..

백준 9376 탈옥 (다익스트라, 0-1 BFS) - 아직 푸는중...

9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제를 잘못이해한게 죄수가 탈옥을 하기 위한 최소의 경로를 찾는게 아니라 문을 최대한 적게 열고 나가야하는점이다. 즉 bfs로 최소 거리를 구한다해도 그 경로가 문을 많이 열었다면 정답이 아니다. 그럼 문을 최소로 여는 경로는 대체 뭐가 있을까? 1. dfs를 쫙 돌리면서 탈옥을 할 때 가장 문을 적게 열었던 경로를 기억하면 되지 않을까? 그 경로를 2번째 죄수가 탈옥할 때 어떤 문을 열어둘지 정하는거지. 근데 여기서 1번째 죄수의 경로를 기준으로 할 필요가 있을까? 2번째..

백준 2631 줄세우기(LIS, DP)

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 대표적인 LIS 문제이다. 처음 문제를 봤을 때 총 3가지로 생각 할 수 있었는데 1. 완전탐색 모든 경우를 다 본다음에 그 중에서 가장 작은 녀석을 고르는 것 2. 그리디 오름차순으로 정렬하는 것이기 때문에 뒤에서 탐색해서 현재 값보다 큰 값을 만난다면 그 숫자를 이동시키는 로직 ==> 최소의 조건이 나오지 않음 3. LIS : 최장 부분 증가 수열 정렬을 최소로 하려고 하면 처음 주어진 배열에 대해서 증가를 보이는 애들은 그대로 놔두고 아닌 애들을 이동하는게 가장 ..